В теме http://mirror.codeforces.com/blog/entry/17502 много сообщений... Решил спросить в новом разделе... Подскажите пожалуйста, как решаются задачи B, E и F?
# | 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 |
В теме http://mirror.codeforces.com/blog/entry/17502 много сообщений... Решил спросить в новом разделе... Подскажите пожалуйста, как решаются задачи B, E и F?
Name |
---|
Copied from main thread:
My solution to B — in cycle pick every city as a center.
Central city can be allocated to either top or bottom cities group depending on where you need it by shifting line some infinitesimal amount up or down. We can do it because no three cities lie on the same line.
After you picked central city you can use magic atan2 function and simulate rotating line through your central city and calculate how many people live above or below it. You can do it by sorting two lists by atan2 value (or one list) and going through it with two pointers. Pick minimum, but remember that you can always allocate central city the way it's better for you (my code was like abs(abs(x) — central)).
I bet there are easier solutions but this one got ACed and I am happy with that.
For me it was tough round, much tougher then Round 1 in GCJ this year. I solved just one problem and spend 1 hour solving Saw or Not To Saw — I think I was very close, but couldn't get through WA3 :(
I can only tell you about E as I only managed to solve this(a bit too late).
Note that there can only be at most 60 updates with k > 1, so any other update can only have k = 1. Updates with k = 1 are just like adding a node to the top of the old tree and calling this new node a root. 2 consecutive updates with k = 1 is like adding 2 nodes to the top of the tree.
So if you store updates in a queue, with all the consecutive k = 1 updates joined together then your queue length will be relatively small.
Now lets answer queries.
For every x y query I found 3 things: depth of x, depth of y and depth of lca of x and y. To do this simply travel down your queue of updates and move into the correct branch of the tree accordingly. Final answer is (depth_x-depth_lca) + (depth_y-depth_lca)
Here is my code. Hope it helps.
I decided that doing LCA is an overkill for this problem, so instead I built two paths to the vertices (which is simple given the set of operations), then reduce both paths while they start with similar operation, then find the length of the remaining paths and sum them up to get the answer.
That is also how I did it. I just did the following things: find depth till the point where both paths start with similar operation(which is what I called LCA) and then build paths to both the vertices. I think this is what you are also saying.
I just used the word LCA because I couldn't think of any better way to describe what I did.