The First Collision, as an Exact Fraction
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.
Find the earliest instant at which any two particles are at the same position. Print it as an exact fraction in lowest terms, then the indices of the two particles that meet then:
a b i j where a / b is the time, b > 0, gcd(a, b) = 1, and i < j
NONE if no two particles ever meet
If several pairs meet at that same earliest instant, report the smallest i,
and then the smallest j for that i. Nothing is destroyed in this problem:
particles pass through each other and keep going, so every pair that can meet
does, and the question is only which pair is first.
``` 2 particles: (0, speed 3, right) (10, speed 1, left)
the gap is 10 and they approach at 3 + 1 = 4, so the time is 10 / 4, which reduces to 5 / 2. -> 5 2 0 1 ```
``` 3 particles: (0, 1, right) (2, 1, left) (3, 1, right)
pair 0 and 1 approach over a gap of 2 at combined speed 2, so time 1. pair 0 and 2 both go right at the same speed and never meet. pair 1 and 2: particle 1 goes left and particle 2 goes right, so they separate and never meet. -> 1 1 0 1 ```
## What most people try first
Dividing. gap / (s[i] + s[j]) as a floating point number is fine for a rough
answer and wrong for this one, in two separate ways. It cannot be printed as a
reduced fraction, and it loses exact ties, which is precisely what the tie-break
rule is about: two pairs meeting at the same instant must be told apart by
index, and that requires knowing the times are EQUAL rather than merely close.
So keep the time as a pair of integers throughout and never divide.
## Comparing and reducing, both with integers only
For i < j, with gap = p[j] - p[i], which is positive:
d[i] = 1, d[j] = -1 approaching gap / (s[i] + s[j])
d[i] = 1, d[j] = 1 i catches j gap / (s[i] - s[j]) if s[i] > s[j]
d[i] = -1, d[j] = -1 j catches i gap / (s[j] - s[i]) if s[j] > s[i]
d[i] = -1, d[j] = 1 separating never
Every denominator above is positive, so a1 / b1 < a2 / b2 exactly when
a1 * b2 < a2 * b1. Scan all pairs in order of i and then j, keep the best
by that comparison, and take a strict < so that an equal time leaves the
earlier pair in place. That is what makes the tie-break fall out of the scan
order instead of needing a separate rule.
Reduce at the very end with the greatest common divisor:
g = gcd(a, b), then print a / g and b / g. Since the gap is positive and
the denominator is positive, the fraction is positive and no sign handling is
needed. A time of a whole number of units prints with a denominator of 1, as in
the second worked example.
In C++ this is std::gcd from <numeric>. Do not reach for __gcd: it is an
internal name that libstdc++ happens to expose and Apple's clang does not, so
code using it fails to compile on some machines and not others.
## Why the first collision is well defined
Every pair either never meets or meets exactly once, because two particles with fixed speeds and directions have positions that are linear in time, and two distinct lines cross at most once. Parallel lines, meaning equal speed and the same direction, never cross at all. So the set of meeting times is finite, with at most one entry per pair, and a finite non-empty set of positive rationals has a least element.
## Overflow
The comparison is where the width goes. A gap is at most 2 * 10^9, and a
denominator is at most 2 * 10^9, so a product reaches 4 * 10^18. That FITS
in a signed 64 bit integer, whose top is about 9.22 * 10^18. It does not come
close to fitting in a 32 bit one, whose top is 2147483647, so every product
here must be 64 bit.
## Cost
O(n^2) time for the pair scan and O(n) memory.