Hi, just my two cents: I think it is much nicer to write

if (mp.count(i)) {
  // mp contains i
  // Do stuff
}

rather than

if (mp.find(i) != mp.end()) {
  // mp contains i
  // Do stuff
}

Of course this works with std::sets as well.

Yes, this was also my solution indeed. Only difference I was computing those L[i] and R[i] values using a binary search for each i.

But then you're right, it is possible to compute L and R inductively in O(n) time.

The point is: can we still solve the problem efficiently if we change that "min" into a "sum"?

Ahah, you're right! I meant "min" (I edited the post, thanks)

Yes, you're absolutely right. Sorry for that, I fixed the example :)

Just curious: what is a bamboo graph?

Thank you very much, that was really eye-opening! This is why I love Codeforces, great community! :)

I'm really striving to understand why the algorithm turns out to be linear instead of quadratic... I know the editorial says "That is because, we could cut exactly max{xi} in each 2 step.", but I can't really get what it means :\

Can you give me a hint? Thanks :)

Solution for problem C: «You can simply guess why such solution is correct.»

Can you give me any hint on how to prove this? I had to take that for granted during the contest, but was wondering what is the most elegant way to prove it...

If you're working with intervals (the so called "Interval union-split-find problem"), you can use any data structure that supports fast insertions and deletions. For example, STL's set should work fine. The lower bound is actually reached using van Emde Boas trees, which support every operation in time. This works because every union operation corresponds to a deletion, while every split is an insertion.

There are some other special cases other than the interval one (cyclic, ordered, ...). See this [1] for a complete reference (it also shows some recent result for the general union-split-find problem)

If by "split" you mean the possibility to backtrack, than there are some interesting results by Mannila and Ukkonen [2] (partial backtracking) and Apostolico, Italiano, Gambosi and Talamo [3].

[1] Katherine Jane Lai, Complexity of Union-Split-Find Problems

[2] Mannila, H. and Ukkonen, E., The set union problem with backtracking, Proceedings of the 13th Inter- national Colloquium on Automata, Languages and Programming (ICALP 86), LNCS, 226, Springer- Verlag, Berlin, 236–243, 1986.

[3] Apostolico, A., Italiano, G.F., Gambosi, G., and Talamo, M., The set union problem with unlimited backtracking, SIAM J. Comput., 23, 50–70, 1994.

I could only get the first three pics (using google translate, nothing special: I really can't get a word of Russian). The first says: "Join here in Codeforces". The second: "You! You've got to get on the top-300". Third: "You -- on the top-50"

I can't really understand the last one. Any hint?

This was the first thought when I took a look at the standings...

D'oh. You are right! Thank you all, guys!

Why is the best amount to donate some b[i]? I had to assume that when I solved the problem, but really didn't get that fully. Any hint? :)

wil93 and I once attended a conference about the theme. You can find some useful papers here, under "Fast Computation of the Neighbourhood Function and Distance Distribution", and here (look at the links in the bottom of the text). Hope this helps :)