Editorial for Yet Another Contest 4 P4 - Even The Odds

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Josh, RandomLB

Observation 1:

Only the parities of each cell matters - we can treat every cell as containing 0 or 1 coins.

Proof

Since we are only considered with addition modulo $2$ ~2~, it suffices to consider values modulo $2$ ~2~.

Observation 2:

If $g_{x, y} = 1$ ~g_{x, y} = 1~, then the parity of each cell in the chosen subgrid is flipped. Otherwise, nothing happens.

Subtask 1

If every cell is even, then every subgrid must also have an even sum. So, we can simply flip the entire grid and make an arbitrary cut.

Time complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Subtask 2

For this subtask, we may simply brute force over all possible subgrids for the special move and all possible cuts that Josh and Nils could make.

Time complexity: $\mathcal{O}(N^3M^3)$ ~\mathcal{O}(N^3M^3)~

Subtask 3

This subtask was intended to reward slower implementations of the full solution that utilize various observations.

Time complexity: $\mathcal{O}(N^2M^2)$ ~\mathcal{O}(N^2M^2)~

Subtask 4

The full solution involves careful casework. One such solution is presented here.

First, let's make some observations.

Observation 3:

If any row or column of the grid has an odd sum, then Nils wins.

Proof

WLOG assume that there exists a row with an odd sum. Nils can cut the grid just after the first row with an odd sum. If this is row $N$ ~N~, then Nils can instead cut between rows $N-1$ ~N-1~ and $N$ ~N~. No matter what cut Josh makes, there exists either one or two subgrids which include this row with an odd sum. Furthermore, all other rows which are part of these subgrids have an even sum. Hence the overall sum of the one or two subgrids is odd, which is not allowed since all subgrids should have an even sum. Hence Nils wins.

Observation 4:

If the set of rows with odd sums is non-empty and non-contiguous, then Nils wins. Furthermore, the set of rows which are part of the flipped subgrid must be equal to the set of rows with odd sums. The same applies for columns.

Proof

Consider the case where the set of rows is non-empty and non-continuous. All of these rows must be included in the flipped subgrid or else they will remain with an odd sum, and Josh will lose according to observation $3$ ~3~. But then there must be a row with an even sum which lies between two elements of the set, which must also get flipped; it will end up with an odd sum. Thus Josh loses in either case.

Now, consider the case where the set of rows with odd sums forms a contiguous range of rows. Then all of the rows in the set must be flipped, and none of the rows outside the set can be flipped or else they will result in having an odd sum. Hence the bounding rows of the flipped subarray must coincide with the interval of rows of the set.

Let's call a row with an odd sum an odd row, and a row with an even sum an even row. Similarly, let's call a column with an odd sum an odd column, and a column with an even sum an even column.

WLOG, let's assume that Josh will make a horizontal cut. We note that if odd columns exist both on the top and bottom subgrids, they must share the same contiguous range. Otherwise, we will be forced to flip an even column. An example of an invalid case is shown below.

$\text{[math]}$

Now, we need to do a large amount of casework. For each possible subgrid to be flipped, we must also check for an odd number within that subgrid. This can be done using a 2-D prefix sum array.

Case 1: Even number of odd columns in both subgrids, no odd rows in any subgrid

Here, the columns that we will choose for the subgrid to be flipped are fixed. We should try to maximize the number of rows to be flipped to maximize the chances of finding an odd number within the subgrid. Keeping in mind that both subgrids need an odd number of rows to be flipped, we will choose either row $1$ ~1~ or row $2$ ~2~ as one boundary and row $N$ ~N~ or row $N-1$ ~N-1~ as the other, depending on the total number of rows in the subgrids.

Case 2: Even number of odd columns in one subgrid, no odd rows in any subgrid

This case is similar to the previous, except that we are only going to flip the cells within the subgrid with an even number of odd columns. Like the previous case, the columns that we need to flip are fixed. If there are an odd number of rows in the subgrid, we can flip all of the rows in the subgrid. Otherwise, we should leave out the topmost or bottommost row in the subgrid.

Case 3: No odd rows or odd columns in any subgrid

No flips are necessary, so we can find any even number in the grid and choose any subgrid containing that number. If grid consists only of odd numbers, we can simply flip the entire grid as we have done in subtask 1.

Case 4: Odd number of odd rows in both subgrids, odd number of odd columns in both subgrids

The rows and columns that we need to flip are fixed.

Case 5: Odd number of odd rows and odd number of odd columns in one subgrid, no odd rows nor odd columns in the other subgrid

The rows and columns that we need to flip are fixed.

Case 6: Odd number of odd rows and odd number of odd columns in one subgrid, even number of odd rows and no odd columns in the other subgrid

The rows and columns that we need to flip are fixed.

Case 7: Even number of odd rows in both subgrids, no odd columns in any subgrid

This case is a rotation of case 1. The rows that we will choose for the subgrid to be flipped are fixed, and we should try to maximize the number of columns to be flipped while satisfying the condition that both subgrids need an odd number of columns to be flipped.

Case 8: Even number of odd rows in one subgrid, no odd columns in any subgrid

This case is a rotation of case 2. The columns that we need to flip are fixed. If there are an odd number of columns in the subgrid, we can flip all of the columns in the subgrid. Otherwise, we should leave out the leftmost or rightmost column in the subgrid.

We can now try cutting each row until we find a valid solution. There are a few ways to efficiently keep track of the parity of the sums of rows and columns, such as using a 2-D prefix XOR array. Finally, we can rotate the grid to handle vertical cuts. Note that extremely careful implementation is required to handle the large number of possible cases.

Time complexity: $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~

Alternative Solution

Observation 5:

If all rows and columns have even sums, it is always optimal for Nils to cut the grid such that four subgrids are created.

Proof

WLOG Josh cuts along the rows. If Nils also cuts along the rows, then since each row has an even sum, all of the created subgrids will have even sums, making Josh win. So Nils should always cut along the columns. The opposite is true if Josh cuts along the columns.

Observation 6:

If all rows and columns have even sums and Nils cuts in the opposite direction to Josh, then all subgrids are even if and only if the top left subgrid has an even sum.

Proof

This can be easily shown, as the condition that every row and column has an even sum implies that any two adjacent subgrids also have an even sum.

Observation 7:

Let $p_{i, j}$ ~p_{i, j}~ be the xor of all cells in the subgrid from $(1, 1)$ ~(1, 1)~ to $(i, j)$ ~(i, j)~. That is, $p$ ~p~ is the 2-D prefix xor grid of $g$ ~g~. Josh wins if and only if all rows and columns are even, and there exists a row or column of $p$ ~p~ containing only zeroes, other than the last row or column of $p$ ~p~.

Proof

From observation $3$ ~3~, for Josh to win, all rows and columns must have even sums. WLOG Josh cuts between rows $x$ ~x~ and $x+1$ ~x+1~. In order for Josh to win, he needs to guarantee that all subgrids from $(1, 1)$ ~(1, 1)~ to $(x, y)$ ~(x, y)~ where $1 \le y \le M$ ~1 \le y \le M~ have even sum; otherwise, Nils would be able to make a cut such that a top-left subgrid with an odd sum is created. Note that the subgrid from $(1, 1)$ ~(1, 1)~ to $(x, y)$ ~(x, y)~ has an even sum if and only if $p_{x, y}$ ~p_{x, y}~ is $0$ ~0~. Hence, Josh requires row $x$ ~x~ of $p$ ~p~ to only contain zeroes. The case where Josh cuts along columns is symmetrical.

With these observations in mind, we can mostly ignore $g$ ~g~ and focus on turning a row or column of $p$ ~p~ to only contain zeroes. We can't fully ignore $g$ ~g~, as we must check that the subarray we have chosen contains a cell with a value of $1$ ~1~, in order to flip the parities of all cells in a subgrid. Don't forget about the case when a cell with a value of $0$ ~0~ is chosen - we must also check that such a cell exists in the chosen subgrid of $g$ ~g~.

We can iterate through all rows and columns of $p$ ~p~, (other than the last row or column), and try to set it to only contain zeroes. Performing the special move can affect the row or column in two different ways:

Nothing happens.
The parity of every other value in some subarray is flipped. The parities of values in the suffix following the subarray might also all be flipped, depending on the length of the relevant subarray.

The behaviour of the special move on a row or column depends on the positioning of the chosen subgrid relative to the row or column and the dimensions of the chosen subgrid. Remember that the chosen subgrid may be constrained by the existence of rows or columns with odd sums.

This solution requires several cases, many of which are similar to the other full solution. These cases will be omitted from this editorial for brevity and are left as an exercise for the reader.

Time complexity: $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~

Comments

There are no comments at the moment.