Codeforces Round #635 (Div. 2)
Problem: https://codeforces.com/contest/1337/problem/C
I need a brief explanation of solution and some intuition behind it. I believe dfs is the go-to approach to optimally select k cities with developing industries for this problem. My dfs game isn’t the strongest, hence I’m here 
Any kind of help would be appreciated. Thanks.
Let’s take any Industry city. The maximum happiness that it can have is its depth from the root. But when we select that city as an Industry, we reduce the happiness of each of its subtree node’s happiness by 1. So basically, choosing any city changes your total happiness by
Depth - No. Of Nodes in its Subtree
So we store for each node, this value, and then sort it and take the K maximum values.
Here is my solution from the contest so it might be messy: Solution .
I suggest you to go through some of the Top solutions for more Cleaner Code for better understanding. Like Um_nik
Can you check this?
WA on test 6
So here, by root you mean the capital right? Firstly we mark all leaf (non - capital) nodes as industry and then mark the closest non-marked node from the leaf as industry and so on. Let me know if I’m making some sense.
No, the leaves need not be the industries.
By root, I mean Node 1 (Capital).
You just calculate the “Depth-Size of Subtree” for EVERY node. And then take the biggest K.
You are doing “Depth - No. of Child”.
I assume deg[x] is the number of Child a node has.
That’s not going to work. Every Node in its subtree suffers when we add this node as an Industry. So instead, you should subtract the Size of its subtree rather than just the number of Children.
Alright, will try to code this up now
Well your reasoning is correct but incomplete!
What I am about to reason is not really relevant for the code part but it is necessary to prove that the mentioned greedy approach is indeed correct.
First we notice that if we choose any node as industry, to maximise happiness, all its descendants must have been chosen already, because if not, then choosing one of the descendants would increase the depth as well as the no. of industry cities would also either decrease or remain the same, thus the total happiness would increase. Hence, it is always optimal to choose a industry all of whose descendants have already been chosen.
Second, ordering the nodes in decreasing order of (depth-no.of descendants) ensures the above because if a node hasn’t been chosen yet, by the above reasoning, any of its ancestor(nodes on path from this node to root) would not be chosen.
Thus, the above solution gives us the optimal happiness.
Yeah, I completely agree with you. To write the equation “Depth - No. of Subtree”, I had to assume that the whole subtree below the node is taken. So it is necessary to prove that to support this argument. Thanks for your input!
I’m not sure but since you made the array of size N+1, the first entry is 0. You should understand that the values of the array l[i] - C[i] can be negative. And thus you would miss them if you sort the whole array. Try sorting only after index 1 and see if that helps!
Thanks bruh <3
Hey I’ve kind of done what you said
Depth - No. Of Nodes in its Subtree
Bottom up approach. Initially taking the leaf nodes (the nodes with the largest level) from the max heap and popping them from the heap one by one. If the parent of that node becomes a leaf, I push it in the max heap. But this time I’m also subtracting the no. of nodes in its subtree from that level.
My submission : Submission #77015830 - Codeforces
Verdict: RUNTIME_ERROR on test 9
The logic seems right. Where could I be going wrong? Any kind of help would be appreciated.
As far as I can understand, the main point of RE can be accessing empty heap or something like that. On a look of Test Case 9, It seems like it is a Bamboo. Try to check your code on these types of trees and see if you could find anything!
P.S. Bamboo means 10–9--8–1--2–3--4–5--6–7 This type of graph. See if your code works for these graphs.
Thanks for the response. It’s probably because of python.
I switched to C++ and implemented the same logic. Ran like a breeze : Submission #77158009 - Codeforces