Need help.

Revision en3, by VastoLorde95, 2015-07-21 21:07:59

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 $ dp_{min}(v) = 1 + \sum\limits_{i=1}^k dp_{max} (u_i) — 1 $"

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! :)

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)