PROBLEM LINK:
Author: Kamil Debowski
Tester: Niyaz Nigmatullin
Editorialist: Kamil Debowski
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
none
PROBLEM
The task is to generate such N (N ≤ 10) points with non-negative coordinates up to 106, that each triple of points would be mistakenly treated as coolinear by the following function, that makes all computations modulo 232:
typedef unsigned int UI;
bool areCollinear(UI ax, UI ay, UI bx, UI by, UI cx, UI cy) {
return (bx - ax) * (cy - ay) == (by - ay) * (cx - ax);
}
EXPLANATION
Let’s think about any general equality A * B == C * D.
Let’s say we want this equality to be true modulo some value X, but false without modulo.
So A * B and C * D should be different but their remainders should be the same.
Trying random numbers won’t work for big X because the probability of getting equal remainders is very low.
But we must notice that X is some special numbers in this problem — it’s equal to 232.
The main part of this problem is to get the idea that it’s easy to make numbers A * B and C * D divisible by 232.
If we want A, B, C, D to be quite small (not exceeding 106), we can say that each of those four numbers is of form k * 216 for some k.
In other words, each of them is divisible by 216 = 65536.
Then both A * B and C * D are divisible by 232 so obviously they are equal modulo 232.
In the given problem about points we will try to find such points that all their coordinates are divisible by 216.
This ensures that we satisfy all equalities modulo 232, because for all triples of points we have (bx - ax) * (cy - ay) mod 232 = 0.
The remaining thing is that the points can’t be collinear.
So, we want each point to be of form (xi * 216, yi * 216) and we need to find N points that none three of them are collinear.
We can say that we just need pairs (xi, yi) where xi, yi ≤ 106 / 216 ≈ 15.
We are looking for N points with coordinates up to 15, such that none three of them are collinear.
At the end we will multiply their coordinates by 216 and print them.
Since N ≤ 10, we can just find 10 such points on paper.
For example, I found points that form the convex shape (the parabola) so they must be non-collinear: (0,0), (1,5), (2,9), (3,12), (4,14), (5,15), (6,14), (7,12), (8,9), (9,5).
The alternative approach is to generate random points and check if they aren’t collinear — in such a case try again, and so on, till you find the valid set of points.
Yet another approach is used in the tester’s code — it uses the fact for for any prime P points (i, i * i % P) aren’t collinear, so we can say that P = 13 and generate 13 points this way.
