Блог пользователя unbelievable02

Автор unbelievable02, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone provide a hint for problem gift for 100 pts?

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится
A (chessboard)
»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
B (plan)
»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
F (treearrray)
  • »
    »
    6 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    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?