# PE2 (AY23/24) ## Problems Questions: {% file src="/files/A0KP4dAnGPN3Ve0OQ1Qy" %} Questios {% endfile %} Official Answers: {% file src="/files/nIko5R22Yqvp4MKTAQHz" %} Official Answers {% endfile %} ### 1. Prime A give-away question. ### 2. Common Another give-away question using [Lec 09 - Searching and Sorting](/cs1010-notes/lec-tut-lab-exes/lecture/lec-09-searching-and-sorting.md#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)** {% code lineNumbers="true" %} ```c 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; } ``` {% endcode %} 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**) {% code lineNumbers="true" %} ```c 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; } ``` {% endcode %} The same idea can be used in the actual flipping of the cell. ```c 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. {% code lineNumbers="true" %} ```c 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); ``` {% endcode %} ### 4. Mode\* > This is another question (the previous one is [/pages/GSCTvFNm3bGgxGOoqNzp#id-4.-box](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pages/GSCTvFNm3bGgxGOoqNzp#id-4.-box "mention")) 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 [/pages/GSCTvFNm3bGgxGOoqNzp#id-4.-box](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pages/GSCTvFNm3bGgxGOoqNzp#id-4.-box "mention"). 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 [on the col](#user-content-fn-1)[^1], then use the binary seach to [on the row](#user-content-fn-2)[^2] 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. {% code lineNumbers="true" %} ```c 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; } ``` {% endcode %} #### Modification of [/pages/GSCTvFNm3bGgxGOoqNzp#id-4.-box](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pages/GSCTvFNm3bGgxGOoqNzp#id-4.-box "mention"), a recursive version The modification just adds the row index constraint. {% code lineNumbers="true" %} ```c 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); } ``` {% endcode %} ### 5. Matchmake\* > This is a variation of [Lec 10 - More Recursion](/cs1010-notes/lec-tut-lab-exes/lecture/lec-10-more-recursion.md#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](/cs1010-notes/past-year-exam/pe2-review.md), and study it further. This is quite important. Maybe need to include [Tut 08 - Searching and Sorting](/cs1010-notes/lec-tut-lab-exes/tutorial/tut-08-searching-and-sorting.md) into [PE2 Review](/cs1010-notes/past-year-exam/pe2-review.md) also. 2. Include the common functions from C Standard Libaray into [PE2 Review](/cs1010-notes/past-year-exam/pe2-review.md), like `isupper()` and `islower()` from ``. 3. Know how to define and initialize a fixed length 2-dimensional array in C from [#id-3.-reversi](#id-3.-reversi "mention"). Include in the [PE2 Review](/cs1010-notes/past-year-exam/pe2-review.md). [^1]: "On the col" here means to get the row index [^2]: "On the row" here means to get the column index that is the last "#" --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pe2-ay23-24.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.