Hi there!
Problem from past regional olympiad: There are N ≤ 5000 distinct points |xi|, |yi| ≤ 104 on the plane. You are asked to find the number of different right triangles, where the vertices are from N points.
TL: 2s, ML: 64MB
Thanks
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi there!
Problem from past regional olympiad: There are N ≤ 5000 distinct points |xi|, |yi| ≤ 104 on the plane. You are asked to find the number of different right triangles, where the vertices are from N points.
TL: 2s, ML: 64MB
Thanks
Name |
---|
Denote a right triangle as with the right angle at vertex . Try choosing each point as . Sort the other points by angle around it, then try choosing each point as (in sorted order) and use 2 pointers to keep the range of points which are at 90° to it (candidates for ). Time: due to sorting.
Can be improved to O(N2) — if we choose , there are just N interesting lines (the ones perpendicular to some ), and we need to count the points lying on each of them; that can be achieved using hashmaps.
Still not so good, because of GCD calculation.
So, how can it be improved, maybe converting to unit vectors?
Well, in such a case you'll be dealing with floating-point numbers. If you want to hash them, you need to round them first. It's inherently not a very good thing.
You can still do it, but you need to calculate the needed precision for rounding first.
Do you have any other suggestions?
If you really want to do something, you can implement all of the three solutions and choose the fastest one :).
Or you can try to prove that this problem can be solved only in ω(n2) time :).
None of these ideas is really serious, though.
Good point. I considered the coordinates to be O(1), since they're pretty small, but even if they weren't, they're limited by int size anyways, and there's a large constant factor in the hashing solution anyways. I
estimateguess that even if we had all |x| and |y| coprime, we wouldn't get a serious boost in complexity. And the is actually quite fast, because it stands on quicksort, which can have a really low low constant factor (in a contest, I'd code that immediately).For N=5000 it seems not the optimal solution
Many contests in Kazakhstan are not prepared well, you must know it. There can be no maximal test cases or the solutions can be run and checked manually, ignoring the limits. So, from exactly what contest did you take this problem from?
http://olympiads.kz/node/53
It's obvious that arti's solution is exactly the same as was described by Xellos (with hashtable).
But why didn't you try just to run the solution? I've done this and the result is exactly what should have been expected: TLE (my laptop is obviously much more powerful than the judges' machines in 2008).
BTW, the solution with sorting is really faster, when implemented correctly.
I've also tried to run my solutions but got TL with different methods: using gcd, unit vectors and just angles, all of them give me TL. I will try to do it using quicksort, but how to be sure that solution will not give TL for N = 5000?
You can't be 'sure' with anything, but you can speak from experience — some solutions passed 372C - Watching Fireworks is Fun. The runtime depends a lot on what the algorithm actually uses, and quicksort is... well, quick. And 2 pointers also have a low constant.
GCD could be precalculated in O(n^2) for all a,b<5000
They're up to 104 here, but yeah, with some tricks like first few steps of GCD + precalc, that'd work pretty fast, too.
The question at this point is rather whether there's a solution that takes O(N2) when the coordinates can be arbitrarily large (provided we can do constant time arithmetics on them).
Such a solution does exist. I've asked a question in Russian yesterday and Igorjan94 has given me a link to an article.
I've come up with some ideas that tell me that this problem should be solvable in O(n2). I'll describe the solution when it'll be ready.