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

4 Likes

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.

1 Like

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.

2 Likes

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!

can you check please why am i getting wrong on test 7

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!

1 Like

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.

1 Like

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