Round #300 E — Need help

Правка en8, от 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?

Теги 300, dp, tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский VastoLorde95 2015-07-21 22:02:22 273
en8 Английский VastoLorde95 2015-07-21 21:56:27 0 (published)
en7 Английский VastoLorde95 2015-07-21 21:56:16 16 (saved to drafts)
en6 Английский VastoLorde95 2015-07-21 21:49:53 611 Tiny change: ')\n\n**UPD** I have ' -
en5 Английский VastoLorde95 2015-07-21 21:10:08 4 Tiny change: 'I am unabl' -> 'Hi, I am unabl'
en4 Английский VastoLorde95 2015-07-21 21:09:22 11 Tiny change: 'u_i) - 1$
en3 Английский VastoLorde95 2015-07-21 21:07:59 296 Tiny change: 's_{i=1}^k \n\nI don'' -
en2 Английский VastoLorde95 2015-07-21 16:19:53 266 Tiny change: 's_{i=1}^k $\n\nCan ' -
en1 Английский VastoLorde95 2015-07-21 15:46:57 268 Initial revision (published)