Editorial for JOI '23 Open P2 - Cell Automaton - Olympiads Online Judge

Editorial for JOI '23 Open P2 - Cell Automaton

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: Akihito Yoneyama

Subtask 1

Following the rules in the problem statement, it is enough to calculate the color of each cell $(x, y)$ ~(x, y)~ in the range $-100 \le x, y \le 100$ ~-100 \le x, y \le 100~ at time $t$ ~t~ ( $0 \le t \le 50$ ~0 \le t \le 50~).

Subtask 2

A cell is black if the shortest distance to initially black cells is $t$ ~t~; it is gray if the shortest distance to initially black cells is $t-1$ ~t-1~; otherwise, it is white. Therefore, it is enough to calculate the shortest distance for every cell $(x, y)$ ~(x, y)~ in the range $-2000 \le x, y \le 2000$ ~-2000 \le x, y \le 2000~ by Breadth-first search (BFS).

Proof

We prove the assertion by induction on $t$ ~t~.

The assertion is true if $t = 0$ ~t = 0~.

If the assertion is true in time $t$ ~t~,

a cell whose shortest distance is $d > t+1$ ~d > t+1~ is white in time $t+1$ ~t+1~ because it is initially white and it is not adjacent to a currently black cell (whose shortest distance is $t$ ~t~);
a cell whose shortest distance is $d = t+1$ ~d = t+1~ is black in time $t+1$ ~t+1~ because it is initially white and it is adjacent to a currently black cell (whose shortest distance is $t$ ~t~);
a cell whose shortest distance is $d = t$ ~d = t~ is gray in time $t+1$ ~t+1~ because it is initially black;
a cell whose shortest distance is $d = t-1$ ~d = t-1~ is white in time $t+1$ ~t+1~ because it is initially gray;
a cell whose shortest distance is $d < t-1$ ~d < t-1~ is white in time $t+1$ ~t+1~ because it is initially white and it is not adjacent to a currently black cell (whose shortest distance is $t$ ~t~).

Therefore, the assertion is true also in time $t+1$ ~t+1~.

Subtask 3

Sorting the $X$ ~X~-coordinates in ascending order, we classify the relations between adjacent cells into the following types and its contribution to the answer:

It does not clash yet.
It has just clashed (if the difference of the $X$ ~X~-coordinates is even).
It already clashed.

The total time complexity is $\mathcal{O}(QN \log N)$ ~\mathcal{O}(QN \log N)~.

Subtask 4

In the classification for Subtask 3, the contribution of each type to the answer is a linear function in $t$ ~t~. Thus, pre-calculating the time when the classification changes and the amount of change of the linear function in advance, we can calculate the answer by sweeping $t$ ~t~ in ascending order and updating the linear function representing the current answer. The total time complexity is $\mathcal{O}(N \log N + Q)$ ~\mathcal{O}(N \log N + Q)~.

Subtask 5

We calculate the contribution of each edge of a square to the answer. For each edge, we have a restriction to a remaining square $(X_i+p, Y_i+q)$ ~(X_i+p, Y_i+q)~ from other squares such as " $|p| \le a$ ~|p| \le a~ after time $t_0$ ~t_0~" or " $|q| \le a$ ~|q| \le a~ after time $t_0$ ~t_0~."

For each edge, calculating these restrictions from each square, we can determine the number of cells (contribution to the answer) satisfying the conditions at time $t$ ~t~. The total time complexity is $\mathcal{O}(QN^2)$ ~\mathcal{O}(QN^2)~.

Subtask 6

The contribution of each edge to the answer is a linear function in $t$ ~t~ on an interval whose boundaries are the time when the restriction is added ( $t_0$ ~t_0~ in the restriction in Subtask 5) and the time when the number of cells satisfying the conditions becomes $0$ ~0~. Therefore, pre-calculating these time and the amount of change of the linear function in advance, we can calculate the answer by sweeping $t$ ~t~ in ascending order and updating the linear function representing the current answer. The total time complexity is $\mathcal{O}(N^2+Q)$ ~\mathcal{O}(N^2+Q)~.

Full Score Solution

First, we consider the case where there is no pair of squares such that $x$ ~x~, $y$ ~y~, $x+y$ ~x+y~, $x-y$ ~x-y~ are equal.

The linear function in $t$ ~t~ representing contribution of each edge to the answer changes only in the following situation:

When a corner of a square clashes another square and vanishes, the edges of the squares are reduced.
When an edge vanishes completely because it is reduced by other squares from both sides, the edges of the squares clash and are reduced.

Both of these cases occur at most $\mathcal{O}(N)$ ~\mathcal{O}(N)~ times.

For the first case, we can enumerate them in $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~ time by sweeping the plane about $8$ ~8~ times using segment trees. For the second case, we can enumerate them using the results for the first case for each edge.

By a similar process, we can calculate the answer even when there is a pair of squares such that $x$ ~x~, $y$ ~y~, $x+y$ ~x+y~, $x-y$ ~x-y~ are equal. The total time complexity is $\mathcal{O}(N \log N + Q)$ ~\mathcal{O}(N \log N + Q)~.

Comments

There are no comments at the moment.