PE2 (AY21/22)

Problems

Questions:

120KB

pe2-2122-s1.pdf

pdf

Questions

Official Answers:

140KB

pe2-2122-s1-with-comments.pdf

pdf

Official Answers

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:

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;
}

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.

In this problem, the end is not inclusive!

5. Path*

This question is very likely to Ex5 Q6 Social. 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.