2174. A Bounce Is Only a Relabelling
n ants stand on the integer cells 0 to m of a stick. All start on
distinct cells, each facing left or right, and all move at one cell per tick.
The two ends are walls. Every ant moves at the same instant, so the whole
system advances one tick at a time.
One tick, in order:
1. an ant standing ON a wall and facing INTO it turns around first, so an ant
at 0 facing left turns to face right, and an ant at m facing right turns to
face left.
2. every ant then moves one cell in the direction it now faces.
3. collisions are resolved:
two ants that LAND ON THE SAME CELL both turn around and stay on that
cell.
two ants that SWAPPED CELLS, which happens when they were adjacent and
facing each other, both go back to the cell they came from and turn
around.
After exactly t ticks, print the positions of all n ants in increasing
order, separated by single spaces. The ants are not labelled in the output, so
you are asked where the ants ARE, not which ant is where.
``` m = 5, t = 1, ants at 0 facing right, 2 facing left, 4 facing right
0 goes to 1, 2 goes to 1, 4 goes to 5. The first two land on cell 1, so both turn around and stay there. -> 1 1 5 ```
m = 5, t = 100, same three ants -> 0 2 4
## What most people try first
Simulating the ticks. It is a faithful reading and it cannot work: t runs to
10^18, so the ticks have to go. The second worked example is a hint about
what replaces them, since after 100 ticks the ants are back exactly where they
started.
## The claim that removes the collisions entirely
Collisions do not affect the answer at all. Replace the rule "two ants bounce" with "two ants pass through each other" and the multiset of (position, direction) pairs after every tick is identical.
Check both collision cases against pass-through:
``` LANDING ON ONE CELL. Two ants come from c-1 facing right and c+1 facing left. pass through: they are at (c, right) and (c, left). bounce: both land on c and turn, giving (c, left) and (c, right). the same two pairs, in the other order.
SWAPPING CELLS. Two ants are adjacent at c facing right and c+1 facing left. pass through: they are at (c+1, right) and (c, left). bounce: both go back and turn, giving (c, left) and (c+1, right). again the same two pairs. ```
In both cases a bounce produces exactly the pairs pass-through produces, with
the two ants exchanged. Since the ants are indistinguishable in the output, the
exchange is invisible, and by induction over the ticks the multiset of positions
after t ticks is the same under both rules. Note how much the exact wording of
the two cases matters: an ant that landed on a shared cell must STAY there, and
one that swapped must GO BACK. Change either and the correspondence fails and
the whole method with it.
Three ants cannot share a cell, because a cell is entered only by an ant from the left and an ant from the right, at most one of each.
## Folding one ant on its own
Under pass-through, each ant is alone, and an ant bouncing between two walls at
0 and m traces a triangle wave of period 2m. Let
u = p + d * t be where it would be with no walls at all. Then:
r = u mod 2m, taken non-negative
position = r if r <= m
2m - r otherwise
The folded path visits 0, 1, ..., m, m-1, ..., 1, 0, 1, ..., which is exactly
the turn-then-move rule above. So the whole answer is one fold per ant and a
sort, with no ticks and no collisions.
## Overflow
u = p + d * t reaches 10^18 in magnitude, and 2m reaches 2 * 10^9.
Both are far outside a signed 32 bit integer, whose top is 2147483647, so
every one of these must be 64 bit. A declared test runs 999999999999999 ticks
specifically so that a 32 bit build gives a different and wrong fold.
Watch the sign of the remainder. In C, C++, Java and JavaScript, % keeps the
sign of the left operand, so -1 % 6 is -1 and not 5. A left-facing ant
gives a negative u, so the remainder must be corrected by adding 2m when it
comes out negative.
## Cost
O(n log n) for the sort, O(n) otherwise, and no dependence on t.
Constraints - `1 ≤ n ≤ 2000` - `1 ≤ m ≤ 10^9` - `0 ≤ t ≤ 10^18` - `0 ≤ p[i] ≤ m`, and the starting cells are distinct - `d[i]` is 1 or -1 - all ants move at the same instant, one cell per tick - an ant on a wall facing into it turns before moving
Input
The first line contains three integers n, m and t: the number of ants, the index of the far wall, and the number of ticks.
Each of the next n lines contains two integers, the starting cell and the direction, which is 1 for right and -1 for left. The starting cells are distinct and lie between 0 and m inclusive.
Output
Print the positions of all n ants after exactly t ticks, in increasing order, separated by single spaces. The ants are not labelled, so only the multiset of positions is asked for.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.