Блог пользователя arun_prasad

Автор arun_prasad, история, 8 лет назад, По-английски

I was trying to solve this problem on Codechef . Click Here

After spending a couple of hours on this I could not come up with any dp relation .

Can someone please provide a dp recurrence for this problem and help me solve it ?

Thanks in advance.

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
  1. It is not a dynamic programming, at least as far as I know.
  2. I posted the solution here, will just copy paste here:

Break free can be solved using binary search and greedy. Let us binary search on the answer, now we have to find minimum number of edges to be broken to decrease all subtree sizes to less than X. The greedy idea is to DFS the tree, and whenever a sub tree has greater than X weight, remove the edge to the heaviest children. It is easy to see why this works. Complexity is where S = max sum of tree weights(2·1013).

Code