How Many Pairs Meet in Time
n particles sit on a line. Particle i starts at p[i], travels at speed
s[i], and moves right if d[i] is 1 or left if d[i] is -1. Positions are
distinct and given in increasing order. Motion is continuous and no particle
ever changes speed or direction.
Particles PASS THROUGH each other. Nothing is ever destroyed, so every pair
that can meet does meet. Count the pairs that are at the same position at some
instant in the closed interval from time 0 to time t, and print that count.
``` for i < j, so p[i] < p[j], with gap = p[j] - p[i]:
d[i] = 1, d[j] = -1 approaching meet at gap / (s[i] + s[j]) d[i] = 1, d[j] = 1 i catches j meet at gap / (s[i] - s[j]) if s[i] > s[j], otherwise never d[i] = -1, d[j] = -1 j catches i meet at gap / (s[j] - s[i]) if s[j] > s[i], otherwise never d[i] = -1, d[j] = 1 separating never ```
A pair counts when its meeting time exists and is at most t. The time may be
a fraction, and a pair meeting exactly at t counts.
``` 3 particles: (0, 1, right) (4, 1, left) (20, 1, left) and t = 5
0 and 1 approach over a gap of 4 at speed 2, meeting at time 2, which is within 5. 0 and 2 approach over a gap of 20 at speed 2, meeting at time 10, too late. 1 and 2 both go left at the same speed, so neither catches the other. -> 1 ```
``` 3 particles: (0, 10^9, right) (1, 1, right) (2, 1, left) and t = 10^18
0 and 1 both go right, and 0 is faster, so it catches 1. 0 and 2 approach. 1 and 2 approach. all three pairs meet, and t is enormous, so all three are in time. -> 3 ```
## What most people try first
Multiplying out. "Is gap / rel at most t" becomes "is gap at most
t * rel", which is the right idea and the wrong expression:
t reaches 10^18
rel reaches 2 * 10^9, since it is a sum of two speeds
so t * rel reaches 2 * 10^27
A signed 64 bit integer holds about 9.22 * 10^18, so that product does not
fit. In Java it wraps to a meaningless value, and in C and C++ signed overflow
is undefined behaviour. The comparison then answers more or less at random,
which is worse than being slow.
## The guard that makes the product safe
One test, before the product, settles most of the cases:
if t > gap:
the pair meets in time, with no product formed at all
else:
form gap <= t * rel
The first branch is sound because rel is at least 1, so t * rel is at least
t, and t > gap already gives t * rel > gap.
The second branch is safe because t <= gap there, and a gap is at most
2 * 10^9, since positions run to 10^9 in magnitude. So t * rel is at most
2 * 10^9 * 2 * 10^9 = 4 * 10^18, comfortably inside the roughly
9.22 * 10^18 a signed 64 bit integer holds. So the UNGUARDED product
overflows 64 bits and the GUARDED one cannot: the product is only ever formed
when forming it is representable, which is a proof rather than a hope.
## Why every pair meets at most once
Each particle's position is a linear function of time while it exists, and here nothing is destroyed, so it is linear for all time. Two distinct lines cross at most once, and two parallel lines, meaning equal speed and the same direction, never cross. So each pair contributes at most one instant, and the count is a count of pairs rather than of events.
This is also why passing through matters so much to the shape of the problem. In #2172 particles are destroyed on meeting, so a pair can be prevented from ever meeting by something that happened earlier, and the answer depends on the ORDER of collisions. Here nothing is prevented, so each pair is decided on its own and the pairs can be counted in any order at all.
## Overflow
Covered above, and it is the point of the problem. Without the guard the
product reaches 2 * 10^27, which is past the top of a signed 64 bit integer.
With the guard it reaches at most 4 * 10^18, which is inside that top. The
count itself is at most n * (n - 1) / 2, which with n at most 2000 is
1999000, so the count is small.
## Cost
O(n^2) time over the pairs and O(n) memory.