One Lane, Front Car First
A road is a row of n cells, numbered 0 on the left to n - 1 on the right.
A cell holds C for a car or . for empty space. Every car faces right.
A tick is not simultaneous, and the order is the whole problem:
the cells are considered from the RIGHT, that is from cell n-1 down to cell 0.
when a car is found:
if it is on cell n-1, it leaves the road
otherwise, if the cell immediately to its right is empty AT THE MOMENT IT
IS CONSIDERED, the car moves into that cell
So a car that has already moved on this tick has already freed the cell it
came from, and the car behind it sees that cell as empty. After exactly t
ticks, print the road.
``` n = 3, t = 1, road ".CC"
cell 2 holds a car, which leaves the road. cell 1 holds a car, and cell 2 is now empty, so it moves there. -> ..C ```
``` n = 3, t = 1, road "CC."
cell 2 is empty. cell 1 moves to cell 2. cell 0 then finds cell 1 empty and moves into it. -> .CC ```
## What most people try first
A simultaneous tick, in which every car looks at the road as it stood at the
START of the tick. On the first worked example that gives ..C as well, but on
the second it gives C.C: the car on cell 0 sees cell 1 occupied, because it
was occupied when the tick began, and so it waits. A whole queue of cars then
advances by one car per tick instead of moving as a block, and a long jam never
clears.
The other common attempt is to sweep from the LEFT. Then the car on cell 0 moves into cell 1 before the car that was there has gone, finds it occupied, and stays. Same wrong answer by a different route.
The rule in the statement is one of those three readings and the problem is unanswerable without saying which, so it says which.
## Every car advances on every tick
That is the whole solution, and it is a proof rather than a simulation.
Work from the right. The rightmost car has no car to its right, so it either leaves the road or steps into an empty cell. Either way it is no longer where it was. Now take any other car and suppose every car to its right has already advanced. The cell immediately to its right either was empty when the tick began, or held a car which has now advanced and left. In both cases it is empty at the moment this car is considered, so this car advances too. By induction from the right, every car advances.
So a car that starts on cell q is on cell q + t after t ticks, and has
left the road as soon as q + t reaches n. The answer is one pass over the
input:
for each cell q holding a car:
if q + t < n: the output has a car on cell q + t
and no ticks are simulated at all, which matters because t runs to 10^18.
## Why no two cars can land on the same cell
Distinct starting cells q1 < q2 give distinct destinations q1 + t < q2 + t,
so the output never has to resolve a conflict. The order of the cars is
preserved exactly, which is what you would expect of a single lane in which
nobody overtakes.
## Overflow
q + t reaches 10^18, which is far outside a signed 32 bit integer, whose top
is 2147483647. So the sum must be 64 bit, or compared as t >= n - q to avoid
forming it at all. The road itself is at most 2 * 10^5 cells.
## Cost
O(n) time and O(n) memory, with no dependence on t.