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)

Subtask 2

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

Time Complexity: \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)

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)

Comments


  • 17
    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}. Do the same for the columns: call that S_{col}.
    If we consider the rows alone, then the answer will be NS_{row}. Likewise for the columns, we'd get 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}.

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