# PE2 (AY21/22)

## Problems

Questions:

{% file src="https://3351151415-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FKipySCGxC8NC1UpA24DS%2Fuploads%2FAa9IrYJSu5yHIxJZHNjW%2Fpe2-2122-s1.pdf?alt=media&token=a906d3f4-ddea-46d4-a39d-94537c75da8d" %}
Questions
{% endfile %}

Official Answers:

{% file src="https://3351151415-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FKipySCGxC8NC1UpA24DS%2Fuploads%2Fu0RFIqfKSrCI6lkozPd6%2Fpe2-2122-s1-with-comments.pdf?alt=media&token=986e35f0-0545-473f-9b73-85f908617b6f" %}
Official Answers
{% endfile %}

### 1. Ease

This is a give-away question.

### 2. Max

This is also a give away question, the main part is to think about the logic of `is_larger()` clearly. My solution is below:

{% code lineNumbers="true" %}
```c
bool is_larger(char *s1, char *s2) {
  if (s1[0] == '-' && s2[0] != '-')
  {
    return false;
  }
  if (s1[0] != '-' && s2[0] == '-')
  {
    return true;
  }
  long len_s1 = (long)strlen(s1);
  long len_s2 = (long)strlen(s2);
  if (s1[0] == '-' && s2[0] == '-')
  {
    if (len_s1 > len_s2)
    {
      return false;
    }
    if (len_s1 < len_s2)
    {
      return true;
    }
    for (long i = 1; i < len_s1; i += 1)
    {
      if (s1[i] < s2[i])
      {
        return true;
      }
      if (s1[i] > s2[i])
      {
        return false;
      }
    }
    return false;
  }
  if (len_s1 > len_s2)
  {
    return true;
  }
  if (len_s1 < len_s2)
  {
    return false;
  }
  for (long i = 0; i < len_s1; i += 1)
  { 
    if (s1[i] > s2[i])
    {
      return true;
    }
    if (s1[i] < s2[i])
    {
      return false;
    }
  }
  return false;
}
```
{% endcode %}

### 3. Cycle

> This question utilises the idea of building a frequency table/counting sort

Okay, I think this question is not that interesting, that's because the most important information in this question is not given clearly. That is 148 is **the largest number** that is a "cycle", so this means our largest cycle number is 148, which should be the largest index of our frequency table.

### 4. Box\*

> This problem is a variation of binary search.

The tricky point is to deal with the edge/boundary cases. The change point is that:

1. If mid is '#', we change our search range to (mid+1, end)
2. If mid is '.' we change our search range to (start, mid)

And our base case is when our search range is 1 (`start==end`), we return `start`, which is either the first position of `.` or the position of the edge.

{% hint style="info" %}
In this problem, the `end` is not inclusive!
{% endhint %}

### 5. Path\*

This question is very likely to [#ex5-q6-social](../../pe1-review#ex5-q6-social "mention"). The idea are very similar, the only thing that serves as a game changer is that you need an array `visited` to mark whether a person has appeared in your path or not.

## Tips

1. The `strlen()` from C standard lib `<string.h>` will return **the number of characters in a string** (excluding the terminating `'\0'`).
2. Whenever you see the Time complexity is $$O(logN)$$, try to think of **binary search**.
