Editorial for JOI '20 Open P1 - Furniture - Olympiads Online Judge

Editorial for JOI '20 Open P1 - Furniture

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.

We may regard the pieces of furnitures initially located in the room are located by operations. It is enough to consider the solution if there is no furniture in the room in the beginning. More concretely, for each $i, j$ ~i, j~ satisfying $C_{i,j} = 1$ ~C_{i,j} = 1~, we add a new operation to the block $(i, j)$ ~(i, j)~ in the beginning. We do not output the results of the new operations.

Subtask 1

In this subtask, it is possible to perform $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~ calculations for each operation. Therefore, for each operation, we temporarily locate a piece of furniture at the block, and decide whether the arrangement is nice or not. If it is not nice, we remove the piece of furniture.

By breadth first search or the depth first search, it is possible to decide whether the arrangement is nice or not in $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~ time.

Subtask 2 (Full Score)

A move satisfying the condition of a nice arrangement will be called a nice move. If there is a nice move passing through the block $(i, j)$ ~(i, j)~, we put $R_{i,j} = 0$ ~R_{i,j} = 0~. Otherwise, we put $R_{i,j} = 1$ ~R_{i,j} = 1~.

Assume that we perform an operation to the block $(X, Y)$ ~(X, Y)~.

Case: $R_{X,Y} = 1$ ~R_{X,Y} = 1~.

In this case, there is no move passing through the block $(X, Y)$ ~(X, Y)~. If we locate a piece of furniture at the block $(X, Y)$ ~(X, Y)~, a nice move will remain nice. Therefore, the arrangement is nice.
Case: $R_{X,Y} = 0$ ~R_{X,Y} = 0~.

If we locate a piece of furniture at the block $(X, Y)$ ~(X, Y)~, a nice move passing through $(X, Y)$ ~(X, Y)~ will not remain nice. We need to consider whether there exist other nice moves.
1. Assume that there exists $(V, W)$ ~(V, W)~ satisfying $R_{V,W} = 0$ ~R_{V,W} = 0~, $V+W = X+W$ ~V+W = X+W~, and $(V, W) \ne (X, Y)$ ~(V, W) \ne (X, Y)~.
  
  In this case, the arrangement will remain nice if we locate a piece of furniture at $(X, Y)$ ~(X, Y)~. In fact, there exists a nice move passing through $(V, W)$ ~(V, W)~. Since such a move does not pass through $(X, Y)$ ~(X, Y)~, it remains nice if we locate a piece of furniture at $(X, Y)$ ~(X, Y)~. For a nice move, the value of $x+y$ ~x+y~ for a block $(x, y)$ ~(x, y)~ which we pass through will increase. Hence we do not pass two blocks with the same value of $x+y$ ~x+y~.
2. Assume that such $(V, W)$ ~(V, W)~ does not exist.
  
  In this case, the arrangement will not remain nice if we locate a piece of furniture at $(X, Y)$ ~(X, Y)~ because every nice move will pass through $(X, Y)$ ~(X, Y)~. There will be no nice move if we locate a piece of furniture at $(X, Y)$ ~(X, Y)~. which we pass through will be increase by $1$ ~1~. Hence it must pass through $(v, w)$ ~(v, w)~ satisfying $X+Y = v+w$ ~X+Y = v+w~. There is no such $(v, w)$ ~(v, w)~ other than $(X, Y)$ ~(X, Y)~ in this case.

Therefore, it is enough to manage the values of $R_{i,j}$ ~R_{i,j}~ efficiently. If we locate a piece of furniture at $(X, Y)$ ~(X, Y)~, we update as $R_{X,Y} \gets 1$ ~R_{X,Y} \gets 1~. It may happen that we need to update as $R_{x,y} \gets 1$ ~R_{x,y} \gets 1~ for some other $(x, y)$ ~(x, y)~. Such $(x, y)$ ~(x, y)~ are detected as follows.

Case: $R_{x+1,y} = 1$ ~R_{x+1,y} = 1~ and $R_{x,y+1} = 1$ ~R_{x,y+1} = 1~.

In this case, we cannot travel from $(x, y)$ ~(x, y)~ to $(N, M)$ ~(N, M)~. Hence there does not exist a nice move passing through $(x, y)$ ~(x, y)~.
Case $R_{x-1,y} = 1$ ~R_{x-1,y} = 1~ and $R_{x,y-1} = 1$ ~R_{x,y-1} = 1~.

In this case, we cannot travel from $(1, 1)$ ~(1, 1)~ to $(x, y)$ ~(x, y)~. Hence there does not exist a nice move passing through $(x, y)$ ~(x, y)~.

Conversely, if there is no block satisfying the above conditions, the values of $R$ ~R~ are updated correctly. In fact, for any $(x, y)$ ~(x, y)~ with $R_{x,y} = 0$ ~R_{x,y} = 0~, either $R_{x+1,y} = 0$ ~R_{x+1,y} = 0~ or $R_{x,y+1} = 0$ ~R_{x,y+1} = 0~ is satisfied. Hence we may move to such block. Continuing this process, we will arrive at $(N, M)$ ~(N, M)~. Similarly, repeating to move from $(x, y)$ ~(x, y)~ to $(x-1, y)$ ~(x-1, y)~ or $(x, y-1)$ ~(x, y-1)~, we will arrive at $(1, 1)$ ~(1, 1)~. Connecting two paths, we get a nice move.

Therefore, for each update $R_{x,y} \gets 1$ ~R_{x,y} \gets 1~, we need to find adjacent blocks where the value of $R$ ~R~ should be updated. Once we update as $R_{x,y} = 1$ ~R_{x,y} = 1~, then the value of $R_{x,y}$ ~R_{x,y}~ will never be $0$ ~0~ again. Therefore, the time complexity of this algorithm is $\mathcal{O}(Q+NM)$ ~\mathcal{O}(Q+NM)~.

Comments

There are no comments at the moment.