Editorial for CCC '21 S2 - Modern Art - DMOJ: Modern Online Judge

Editorial for CCC '21 S2 - Modern Art

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: Plasmatic

Subtask 1

There is only one cell, so only the number of operations matters.

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

Subtask 2

Keep track of the cells using a 1D array, and simulate each operation.

Time Complexity: $\mathcal{O}(NK)$ ~\mathcal{O}(NK)~

Subtask 3

The solution is the same as the previous subtask, except a 2D array must be used instead.

Time Complexity: $\mathcal{O}(K \times \max(N,M)+NM)$ ~\mathcal{O}(K \times \max(N,M)+NM)~

Subtask 4

One way to solve the problem is to realize that the colour of a square is dependent on the parity of the number of operations performed on its row and column. We can keep track of the counts using two frequency arrays, and then loop over each cell in the grid to check its colour.

Time Complexity: $\mathcal{O}(NM+K)$ ~\mathcal{O}(NM+K)~

Comments

15

jgcodes2020_alt commented on Oct. 7, 2021, 3:52 p.m. ← edited →

There is also an even faster solution (not mine by the way):

If we know the parity of each row and column, it's possible to determine the number of cells like so:

First, we sum the parities of each row: we'll call it $S_{row}$ ~S_{row}~. Do the same for the columns: call that $S_{col}$ ~S_{col}~.
If we consider the rows alone, then the answer will be $NS_{row}$ ~NS_{row}~. Likewise for the columns, we'd get $MS_{col}$ ~MS_{col}~.

We still need to consider the cells where our rows and columns intersect. Since we would've counted them twice with the first two products, we subtract $2S_{col}S_{row}$ ~2S_{col}S_{row}~.

Time complexity: $\mathcal{O}(N+M+K)$ ~\mathcal{O}(N+M+K)~