unbelievable02's blog

IZHO 2018
By unbelievable02, history, 8 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, hide # |
← Rev. 4  
Vote: I like it +8 Vote: I do not like it
A (chessboard)
→ Reply
»
8 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it
B (plan)
→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it
F (treearrray)
→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 5  
    Vote: I like it 0 Vote: I do not like it

    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?

    → Reply