Editorial for DMOPC '20 Contest 4 P2 - Beautiful Grids

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.

Author: Riolku

Define an odd row as a row with an odd sum, and an odd column is a column with odd sum.

For 10%, note that we need only output any valid sequence. Although many sequences can work, the simplest is to simply output K, followed by the cells containing 1 as specified in the input.

For 20%, we need only output the correct answer A. If we count the number of odd columns C and odd rows R, our answer is \max(C, R). We will discover why later.

Subtask 1

Let us consider only the odd rows and odd columns. Note that any flip we perform flips the parity of the relevant row and column. We can iterate through the odd rows, and choose an arbitrary odd column to flip at the same time. However, what if there are no more odd columns? Then we can simply flip an arbitrary column. We can prove that R - C is always even, so that our end result will be beautiful. Such a proof is left as an exercise to the reader.

Note that we may have some odd columns left over as well, which we can process by flipping an arbitrary row.

Time Complexity: \mathcal O(NM)

Subtask 2

We can optimize the solution to \mathcal O(K) with a map. Implementation details are left as an exercise to the reader.

Time Complexity: \mathcal O(K)


There are no comments at the moment.