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.
№ | Пользователь | Рейтинг |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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.
Название |
---|
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!