skpro19's blog

By skpro19, 7 years ago, In English

This was the fourth question in the November Lunchtime. I am not able to understand it, even after reading the editorial. Can someone please explain it in a bit more detail?

Contest link Problem Link Official Editorial Link Unofficial Editorial Link

I can not udnerstand anything in the official editorial.

I can't understand the dp states in the unofficial editorial, and also how to use the treap data structure being discussed in the editorial.

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

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

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

You don't need a treap, a segment tree works fine.

DP[L][R][X][Y] denotes the min cost to connect the interval [L, R]. X=1 denotes index L is connected to the left and X=0 denotes otherwise. Similar argument for R and Y.

Now, each node of the segment tree stores DP[L][R][X][Y], for 0 <= X, Y < 2, for the range [L, R] corresponding the node of the segment tree. Consider the index M = (L+R)/2. You can choose to either connect M to M+1 or not. Handle both cases separately and merge the 2 DP values from left and right children to get the DP value for the current node. See my code for more details.

My code