Hello Codeforces!!!
Izho 2018 have been finished. I wish everyone the best awards. Let's solve the problems together and compensate our mistakes on olympiad.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello Codeforces!!!
Izho 2018 have been finished. I wish everyone the best awards. Let's solve the problems together and compensate our mistakes on olympiad.
Name |
---|
Can anyone provide a hint for problem gift for 100 pts?
First 3-4 subtasks are possible with brute force only, right?
Yes
Would you please explain me why answer is always subarray of length 1 or 2?
And would You please define a notion of subarray?, is it a continuous segment in array?
fact: depth[lca(a, b)] >= depth[lca(a, b, c)]
Let's denote V as set of vertices which are in subtree(v), so if we'll increase size of V, lca of all vertices of V won't at least become more distant from v, so all we need to do is find two vertices(x, y), lca(x, y) = v & if we'll denote i as index of x and j as index of y in array, is it correct that all vertices in range[i, j] in array must be in subtree(v) to say that answer for current query is (x, y)?
Thanks in advance!
UPD: I forgot that fact that those vertices (x, y) must be in two different children of vertex v, how should I do there?
UPD': Probably, I got it! Thank you very much! But here's last request to confirm something: if we have set of vertices V that all vertices locate in subtree of v, will it be correct & enough to consider always & only adjacent vertices from set V?
Last UPD: YES
Thank you so much!