3_Problems_Everyday's blog

Please help me to understand binary raise used in this problem .
By 3_Problems_Everyday, history, 9 years ago, In English

Hello everyone ! I am trying to solve this problem.I didn't understand the editorial properly. Please help me to understand the binary raise used in the editorial. Because i am new to this concept, provide me some tutorial to learn it.Thanks :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like it refers to the Sparse Table structure complementary to the LCA algorithm. The author may have used this name because the Sparse Table indexes are equivalent to powers of two ("binary raises")

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe binary raise refers to "skips" of power of two used in the LCA algorithm. For LCA, we store for each node, the nodes at distances 1, 2, 4, 8... and so on, going to the root. That way we'll be able to answer queries in logarithmic time. I think the editorial is pretty clear to understand the rest of the problem (dealing with different cases). The pictures are very helpful.

Refer to my code if it helps -> C++ Code

→ Reply