Editorial for TLE '16 Contest 3 P5 - LAN Party

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

In this editorial, let $N = \max(R,C)$ $N = max (R, C)$ .

Subtask 1

It is sufficient to check every possible square after every removal, then print the answer. There are $\mathcal{O}(N^2)$ $O (N^{2})$ corners to choose from, and $\mathcal{O}(N)$ $O (N)$ possible square sizes. Each square takes $\mathcal{O}(N^2)$ $O (N^{2})$ time to check. Therefore, a removal takes $\mathcal{O}(N^5)$ $O (N^{5})$ time to process.

Time Complexity: $\mathcal{O}(MN^5)$ $O (M N^{5})$ , which can be $\mathcal{O}(N^7)$ $O (N^{7})$ in the worst case.

Subtask 2

It is possible to reduce the amount of checking required. For each of the $M$ $M$ removals, generate a 2D sum array in $\mathcal{O}(N^2)$ $O (N^{2})$ time. Each square now takes $\mathcal{O}(1)$ $O (1)$ time to check. The best square size starts at $0$ $0$ , and it only matters when the best size gets beaten, so the $\mathcal{O}(N^3)$ $O (N^{3})$ possible squares are now reduced to $\mathcal{O}(N^2)$ $O (N^{2})$ possible squares. Therefore, a removal would take $\mathcal{O}(N^2)$ $O (N^{2})$ time to process.

There is a possible optimization which keeps the information of the best square so far. If a removal is not in the square, the answer will stay the same. This creates a mixture of $\mathcal{O}(N^2)$ $O (N^{2})$ and $\mathcal{O}(1)$ $O (1)$ removals. However, this optimization is unlikely to solve the last subtask in time.

Time complexity: $\mathcal{O}(MN^2)$ $O (M N^{2})$ , which can be $\mathcal{O}(N^4)$ $O (N^{4})$ in the worst case.

Subtask 3

It is important to keep track of all $\mathcal{O}(N^3)$ $O (N^{3})$ squares in an array. Initially, all values in the array are set to true. When a person leaves, then all of the squares containing that person must be set to false. This can be accomplished with a DFS. Whenever a square of size $X$ $X$ is true but needs to be removed, the four squares of size $X+1$ $X + 1$ should be removed. Therefore, the total number of operations done is $\mathcal{O}(N^3)$ $O (N^{3})$ . It may be interesting that the first removal takes $\mathcal{O}(N^3)$ $O (N^{3})$ .

To get the maximum square size available, one can use a histogram of available square sizes. The only corner case is when everyone leaves and the answer is now $0$ $0$ .

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

Comments

There are no comments at the moment.