Round #300 E — Need help

Revision en8, by VastoLorde95, 2015-07-21 21:56:27

Hi, I am unable to understand the solution provided in the editorial of this problem. I read the explanations in the comments but can't seem to understand them either.

Specifically, I am stuck on this part of the editorial —

"For every arrangement, the minimizing player can guarantee himself the result of at most "

I don't see the logic behind this formula.

Also in the editorial dpmax(v) is given as but in the sample solution 10973864 it is given as . How is that the same?

I have been at this for hours now! Can someone please help me? Thank you! :)

UPD - I have solved the problem using the method described here. But I would still like to know how the author's implementation is working since in the solution I implemented is different. In my submission, in one dfs we use the notation of dp(v) = k, being the k'th smallest value and in the other iteration as the k'th largest value, but in the author's solution, it seems to me that he has used the notation dp(v) = k as the k'th smallest value in both the cases. If so then can someone please clarify the transitions made by the author?

Tags 300, dp, tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English VastoLorde95 2015-07-21 22:02:22 273
en8 English VastoLorde95 2015-07-21 21:56:27 0 (published)
en7 English VastoLorde95 2015-07-21 21:56:16 16 (saved to drafts)
en6 English VastoLorde95 2015-07-21 21:49:53 611 Tiny change: ')\n\n**UPD** I have ' -
en5 English VastoLorde95 2015-07-21 21:10:08 4 Tiny change: 'I am unabl' -> 'Hi, I am unabl'
en4 English VastoLorde95 2015-07-21 21:09:22 11 Tiny change: 'u_i) - 1$
en3 English VastoLorde95 2015-07-21 21:07:59 296 Tiny change: 's_{i=1}^k \n\nI don'' -
en2 English VastoLorde95 2015-07-21 16:19:53 266 Tiny change: 's_{i=1}^k $\n\nCan ' -
en1 English VastoLorde95 2015-07-21 15:46:57 268 Initial revision (published)