OVERPNT - Editorial

PROBLEM LINK:

Practice
Contest

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution 1.
Setter’s solution 2.

3 Likes

Author and Setter’s solutions link not working.

I am really sorry, that I have to post it here, I don’t have enough karma to ask the question…

Hello, in recent contest , February LTIME, I have scored 220 marks, and I should be at 124th position , but rankings are not being updated, I am worried about my ratings calculation…

You may please visit these links and confirm it…

Please help

EDIT: 1

Now rankings are ordered, Thank you.

1 Like

@admin can you please release the editorial of BRIBETR for this contest.

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
. Can you please explain this part and I tried p=1e9+7 but my solution gave WA.

Now wrong link.

2 Likes

just uploaded :slight_smile:

corrected, sorry for the inconvenience

Those coordinates were supposed to not exceed 15 so you can’t choose huge P.

1 Like

Thanks a lot :slight_smile: