Problem of February '21

Again, I’m with you and here is the problem of February 2021.

I selected MinMaxGame, as it’s game and games are always interesting. Also, Div. 2 level 3 problem is always challenging for a majority of coders.

There is an array and two players are playing a game. Nam goes first and in each move, he selects two consecutive numbers and removes the larger one. Then, Quang goes and he selects two consecutive numbers and removes the smaller one. Nam wants to maximize the remaining number and Quang is against him. Find the remaining number of they play optimally.

Consider the array consists of only 0 and 1. We want to know if Nam can defeat Quang and make the last number equal to 1 or if Quang will manage to make the last number equal to 0.

So Nam wants to remove 0s and Quang wants to remove 1s. If there are two consecutive 0s, Nam for sure will remove one of them. Otherwise, every move of him results in removing a 1. Similarly, if there are two consecutive 1s, Nam for sure will remove one of them. Otherwise, every move of him results in removing a 0.

Let t0 be the total number of zeros. Let t1 be the total number of ones. Let b0 be the number of blocks of zeros (block is set of several consecutive zeros which can’t be expanded) and let b1 similarly.

At the first, every move of Nam results in t0–, similarly every move of Quang will result in t1–. After some time, one of them, say Nam, runs out of consecutive 0s. Quang can manage such that never again some two consecutive 0s appear. So after that, they’ll both remove 1s till Quang runs out of consecutive 1s too. Then we have something like 01010101… . There are three cases: if the number of 1s > the number of 0s, Nam wins. If the number of 0s > the number of 1s, Quang wins. Otherwise, whoever started this phase of the game (i. e. when the array is something like 01010101…) loses.

In the latter case, to find who starts the final phase, we know that totally t0 - b0 + t1 - b1 moves happened. If this number is even, then Nam will start the final phase and lose. Otherwise, Quang is the loser.

So, now, we can find the answer if the array contains only 0s and 1s. How to solve the main problem? The answer is simple, binary search.

Run binary search on the answer, to check if the answer is greater than or equal to x, replace each number more than or equal to x with 1, replace others with 0.

My code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool check(vector < int > & a, int x) {
  int b[2] = {}, extra[2] = {};
  int last = -1;
  for (auto element: a) {
    element = element >= x;
    if (element != last)
      b[element]++;
    extra[element]++;
    last = element;
  }
  extra[0] -= b[0];
  extra[1] -= b[1];
  if (b[0] != b[1])
    return b[1] > b[0];
  return (max(extra[0], extra[1]) - min(extra[0], extra[1])) % 2;
}

int lastNumber(vector < int > a) {
  int low = 1, high = maxn;
  while (high - low > 1) {
    int mid = (low + high) / 2;
    (check(a, mid) ? low : high) = mid;
  }
  return low;
}