Editorial for DMOPC '20 Contest 5 P4 - Slacking Off


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

For the first subtask, we can iterate through all \mathcal O \left((NM)^2\right) sub-rectangles and check if each one is ugly. We can do each check in \mathcal O(N+M) for a total time complexity of \mathcal O \left((NM)^2(N+M)\right).

Time complexity: \mathcal O \left((NM)^2(N+M)\right)

For the second subtask, we can still iterate through all possible sub-rectangles, but use an \mathcal O(1) hash to check if their first and last rows and first and last columns are identical. This reduces our total complexity to \mathcal O \left((NM)^2\right).

Time complexity: \mathcal O \left((NM)^2\right)

For the final subtask, we ask the question: given two rows r_1 and r_2, how many ugly rectangles have first row r_1 and last row r_2?

Let's focus on the area of the screen between r_1 and r_2. Notice that there are certain "chunks" of the screen where r_1 and r_2's pixels are identical. For example:

Then, observe that a rectangle with first row r_1 and last row r_2 is ugly if and only if:

  • its first and last columns are identical, and
  • its first and last columns are within the same "chunk" (otherwise, the first and last rows of the rectangle would not be identical).

Hence, we want to know the total number of pairs of identical columns that are in the same chunk. We can calculate this number in \mathcal O(M) or \mathcal O(M \log M) by sweeping over the columns from left to right, adding their hashes to a set as we go along, and processing and clearing the set when we reach the end of a chunk. Repeating this for all pairs (r_1, r_2), we get a total time complexity of \mathcal O \left(N^2 M\right) (with a possible extra log factor).

Finally, notice that \min(N, M) cannot be larger than \sqrt{NM}. Thus, if we choose N to be the smaller of the two, our time complexity becomes \mathcal O \left(NM \sqrt{NM} \right).

Time complexity: \mathcal O \left(NM \sqrt{NM} \right) or \mathcal O \left(NM \sqrt{NM} \log(NM) \right)


Comments

There are no comments at the moment.