Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Round #300 E — Need help

Revision en9, by VastoLorde95, 2015-07-21 22:02:22

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.

In the editorial dp max(v) is given as but in the sample solution 10973864 it is given as . How is that the same?

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?

#### History

Revisions

Rev. Lang. By When Δ Comment
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)