Contest Duration: - (local time) (120 minutes) Back to Home

## C - Fair Elevator Editorial by evima

First, let us sort out the conditions. Assume that:

• $$A_i < B_i$$
• $$A_1, B_1, A_2, B_2 \cdots, A_N, B_N$$ are all different.

Let us say that the person who got on at Floor $$1$$ gets off at Floor $$x$$. Then, we can see that the persons who got on at Floor $$2, 3, \cdots, x-1$$ get off at Floor $$x + 1, x + 2, \cdots, 2x-2$$.

By repeating this argument, we can see that the condition is satisfied if and only if it is possible to divide the $$2N$$ floors into segments where the persons with $$(A, B) = (x, x+k), (x+1, x+k+1), \cdots, (x+k-1, x+2k-1)$$ get on and off.

Now, let us think of a way to determine, for a fixed division, if it is possible to fill in $$A$$ and $$B$$ so that the above holds.

Let us make an array that stores (left/right, the person’s ID) for each floor if there is a person bound to get on/off on that floor.

For each segment, the following is necessary:

• There is no person with fixed $$A$$ and $$B$$ such that only one of them is contained in the segment. If a person has both $$A$$ and $$B$$ in the segment, they are in the correct positions.
• If the persons who got on/off at Floor $$x+i$$/$$x+k+i$$ are both already fixed, they are the same person.
• There is no pair of floors ($$x+i$$, $$x+k+i$$) such that the person at Floor $$x+i$$ is “left.”
• There is no pair of floors ($$x+i$$, $$x+k+i$$) such that the person at Floor $$x+k+i$$ is “right.”

On the other hand, if the above is satisfied for every segment, we can find one correct record by filling in $$A$$ and $$B$$ properly.

Thus, the problem can be solved by DP. Let dp[$$i$$]:= (true if a segment ends exactly at Floor $$i$$ and there is no contradiction until Floor $$i$$, false otherwise), and make dp[$$r$$] true when a new segment $$[i+1, r]$$ has no contradiction.

The time complexity is $$\mathrm{O}(N^3)$$.

Sample Implementation (added on July 8 (Japan time))

Sample Misimplementation (turned out to be wrong later)

posted:
last update: