kazakhThunder's blog

Help needed in 1336A-Linova and Kingdom. Need a better explanation for the solution
By kazakhThunder, history, 5 years ago, In English

The editorial for the given problem is a tad bit too difficult to understand for me, and I suppose for many others. Thus, I am looking for simpler explanations to the solution. Any help would be greatly appreciated. UPD: Here is the link to the problem: https://mirror.codeforces.com/contest/1336/problem/A

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Considering that all paths end at the root(node 1) you may want to put the other end of the path as far as possible from the root. Therefore, starting with the highest depth node of the tree, place the nodes to get the highest possible answer using the following equation:

answer[node] = depth[node] - sizeofsubtree[node].

The size-of-subtree part is because adding an industrial city in the node will decrease the number of tourism cities of all its children. Using a priority queue with a key of the equation above, choose the highest k.

Notes for later: adding a link to the problem is rather helpful for people answering, also the announcement and editorial have comments with explanations other than the editorials most of the time, might want to check them out.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Link added. Thank you for the notes, will keep them in mind for the next time.

    → Reply