| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
Common case with Topcoder website :(
It seems to be in the calendar here, link.
The email reminder says it will be at 12:00 UTC-4, that is 19:00 MSK (why don't they put a link to timeanddate in their email?).
Very nice problems, 600 was very nice and 900 also looked interesting.
Any ideas on 600?
900 can be solved using 2-SAT on variables "i-th person in subtree of j-th vertex". There are some condition on this variables depended on tree structure, like, if you are in subtree of vertex, you are in subtree of it's parent. I lost condition, that you can't be in subtrees of two vertices wich are different sons of one, so failed systest.
Each of problem conditions can be expressed in terms of "both vertex in subtree of x[i], and at least one of vertices not in subtree of each son of x[i]". This changes a bit if r[i] is son of x[i]. But all subtrees for all roots are subtrees or their complements of original tree, so it's ok.
Let N be the number of points. We can see that (the number of finite regions) = (the number of crossings) + (the number of components) — N. Since the number of components is a constant (unless we make really stupid choice of directions), we want to maximize the number of crossings.
Now, let's convert the coordinates, and assume the following:
We want to color the points red and blue, and maximize the number of pairs of red point R and blue point B such that x(R) < x(B) and y(R) > y(B).
Here, in one optimal solution, we can prove that their is a shortest path from (0, 0) to (N, N) that splits the square [0, N] × [0, N] into two regions, such that in one region all points are red and in the other region all points are blue. Now it's not hard to come up with an O(N2) DP.
Am I right the solution for 900 is the 2-SAT on statements "person x lives in the subtree of directed edge y"? I've coded this, but haven't managed to get it working in time.
Ok, thanks PavelKunyavskiy :)