PE2 (AY23/24)

Problems

Questions:

86KB

pe2-2324-s1.pdf

pdf

Questios

Official Answers:

140KB

pe2-2324-s1-with-comments.pdf

pdf

Official Answers

1. Prime

A give-away question.

2. Common

Another give-away question using Counting Sort*.

3. Reversi*

This is an interesting problem which tests yourself about your ability to break a problem into small parts. The rule is easy to understannd, but the genius point in the question is the way how it is implememnted.

Firstly, since we have 8 directions, the method we use to count the flips in each direction should be the same except that how we transit to the next cell may be different. To use this pattern, we can define a fixed length 2-dimensional array. (Genius point 1)

long count_flips(char **board, long r, long c)
{
  if (board[r][c] != '.')
  {
    return -1;
  }
  long dir[8][2] = {{1, -1}, {1, 1}, {-1, 1}, {-1, -1}, {0, -1}, {0, 1}, {1, 0}, {-1, 0}};
  long total = 0;
  for (long i = 0; i < 8; i += 1)
  {
    total += count_flips_in_one_dir(board, r, c, dir[i][0], dir[i][1]);
  }
  return total;
}

Now, we need to implement our count_flips_in_one_dir(). This is done by flipping all the zeros in that direction within range. And at last, we check whether the cell we stopped at is one or not. If it is, we return count-1 (-1 is for the last cell which is one, this doesn't need to be flipped). If not, means we cannot flip any zero in this direction, thus we return 0. (Genius point 2)

long count_flips_in_one_dir(char **board, long r, long c, long r_step, long c_step)
{
  long count = 0;
  do {
    r += r_step;
    c += c_step;
    count += 1;
  } while (in_range(r, c) && board[r][c] == ZERO);
  if (in_range(r, c) && board[r][c] == ONE)
  {
    return count - 1;
  }
  return 0;
}

The same idea can be used in the actual flipping of the cell.

void flip_in_one_dir(char **board, long r, long c, long r_step, long c_step)
{
  do {
    board[r][c] = ONE;
    r += r_step;
    c += c_step;
  } while (in_range(r, c) && board[r][c] == ZERO);
}

void flip(char **board, long r, long c)
{ 
  long dir[8][2] = {{1, -1}, {1, 1}, {-1, 1}, {-1, -1}, {0, -1}, {0, 1}, {1, 0}, {-1, 0}};
  board[r][c] = ONE;
  for (long i = 0; i < 8; i += 1)
  {
    if (count_flips_in_one_dir(board, r, c, dir[i][0], dir[i][1]) != 0)
    {
      flip_in_one_dir(board, r, c, dir[i][0], dir[i][1]);
    }
  }
}

Then, in our main() function, we just need to memorize the position with maximum count flips. And then use that position to actually flip the cells accordingly.

long max = -1;
long max_r = 0;
long max_c = 0;
for (long i = 0; i < 8; i += 1)
{
  for (long j = 0; j < 8; j += 1)
  {
    long count = count_flips(board, i, j);
    if (count > max)
    {
      max = count;
      max_r = i;
      max_c = j;
    }
  }
}
cs1010_println_long(max);
flip(board, max_r, max_c);

4. Mode*

This is another question (the previous one is 4. Box*) that is the variant of Binary Search, which means that the variation of Binary Search is very important).

The idea is pretty similar and the implementation you can just use the one in 4. Box*. The only thing I want to discuss is how to reach the time complexity $O(logM*logN)$. Use Binary Search on each rows takes $O(logN)$ and on each column takes $O(logM)$. So, the idea is that we do binary search , then use the binary seach to to compare the score.

The loop version of finding the position of the last "#"

Or similarly speaking, output the number of "#" in a string

Basically, it utilizes the fact that our input is a string, so if we reach the edge case when all the characters in the string is "#", now histogram[r][mid+1] will be \0. And when we exit the loop, it will output the last position.

size_t score(char **histogram, size_t r, size_t m)
{
  size_t i = 0;
  size_t j = m - 1;
  while (i < j)
  {
    size_t mid = (i + j) / 2;
    if (histogram[r][mid] == '#' && histogram[r][mid+1] == '#')
    {
      i = mid+1;
    }
    else
    {
      j = mid;
    }
  }
  return i+1;
}

Modification of 4. Box*, a recursive version

The modification just adds the row index constraint.

size_t search_row(char **histogram, size_t start, size_t end, size_t row)
{
  if (end == start)
  {
    return start;
  }
  size_t mid = (start + end) / 2;
  if (histogram[row][mid] == '#')
  {
    return search_row(histogram, mid + 1, end, row);
  }
  return search_row(histogram, start, mid, row);
}

5. Matchmake*

This is a variation of Permutations, it tests the backtracking idea.

The comments has provided good enough explanation. And one thing to note in the generate() function below is that in Line 14, we will only try to pair the people behind curr with curr because since we start from 0, so means we have already found the possibility for the pair before curr.

void generate(char **match, long n, long dine_with[], long curr, bool *visited)
{
  if (curr == n)
  {
    print(dine_with, n, visited);
    return;
  }
  if (dine_with[curr] != UNMATCH)
  {
    generate(match, n, dine_with, curr + 1, visited);
  }
  else
  {
    for (long i = curr + 1; i < n; i += 1)
    {
      if (dine_with[i] == UNMATCH && is_interested(match, curr, i))
      {
        dine_with[curr] = i;
        dine_with[i] = curr;
        generate(match, n, dine_with, curr+1, visited);
        dine_with[i] = UNMATCH;
        dine_with[curr] = UNMATCH;
      }
    }
    dine_with[curr] = curr;
    generate(match, n, dine_with, curr + 1, visited);
    dine_with[curr] = UNMATCH;
  }
}

But the print() part is still a bit tricky since we need to print all the pairs first, then print the individual.

Tips

1. Include the variation of Binary Search in PE2 Review, and study it further. This is quite important. Maybe need to include Tut 08 - Searching and Sorting into PE2 Review also.

2. Include the common functions from C Standard Libaray into PE2 Review, like isupper() and islower() from <ctype.h>.

3. Know how to define and initialize a fixed length 2-dimensional array in C from 3. Reversi*. Include in the PE2 Review.