HLDOTS - editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Roman Furko
Editorialist: Balajiganapathi Senthilnathan

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic programming

PROBLEM:

A heavy light decomposition of a tree is where you label exactly one edge going out of each node (i.e. away from the root) as heavy and others as light. A correct heavy light decomposition is where the number of light edges from root to any node is at most \lfloor{log_2} n \rfloor. Given a tree, find the number of correct heavy light decomposition it can have.

QUICK EXPLANATION:

This can solved by using dynamic programming with the state(node index, number of light edges seen from root so far). To calculate dp[x][cnt] we loop through each outgoing edge of x and mark it as heavy in turn. We recursively solve for the children and only increment cnt if that edge is light. If at any stage the number of light edges is \gt log_2 n we return 0. If we reach a leaf then we return 1. See explanation for how to calculate this optimally.

Explanation

Since this is a tree, it is not much of a leap to guess that we need some sort of recursive solution. Suppose we start recursion from the root and solve recursively for children, what extra information do we need? And what do we do for each node? From the statement, it is clear that the action we must perform for each node is: choose each of the edges as a heavy edge and calculate the number of ways we can make a correct heavy light decomposition with that edge marked heavy. Sum up these ways for all the edges.

The only other constraint is that the number of light edges from root to any node must be \le log_2 n. So, besides the node index itself, we also need the number of light edges traversed so far. This gives us the state of our recursion: (x, cnt) where x is the current node index and cnt is the number of light edges traversed from the root to x.

Suppose the function solve does this, the final answer will be solve(1, 0).
How to calculate solve(x, cnt)?

x has say m children c_1, c_2 ... c_m. We make each of the m edges heavy in turn and increment cnt while calling recursively for all children except the one we made heavy. Now since the number of correct heavy light decomposition for one child is independent of the other children, we multiply the ways we get for each children. We sum this up for all possible choices of heavy edges to get the answer for solve(x, cnt). Since a state may repeat, we do memoization to avoid re calculations.

So,
solve(x, cnt) = \sum_{i = 1}^{m} (\prod_{j \ne i} solve(c_j, cnt + 1) * solve(c_i, cnt))

A straight forward implementation of this formula will TLE for subtask 3 as it will take O(m^2) = O(n^2) (Consider a tree where the root has n - 1 children).

To optimize let us see the inner product in detail.
We have \prod_{j \ne i} solve(c_j, cnt + 1) * solve(c_i, cnt).
We can split it as
\prod_{j = 1}^{i - 1} solve(c_j, cnt + 1) * \prod_{j = i + 1}^{m} solve(c_j, cnt + 1) * solve(c_i, cnt).

Why is this helpful? Well, we can see that we need two types of products: from left side till i - 1 and from right side till i + 1. We can precalculate this.

Let us define two arrays left and right.

left[i] = \prod_{j = 1}^{i} solve(c_j, cnt + 1)

right[i] = \prod_{j = i}^{m} solve(c_j, cnt + 1)

Now note that we can calculate this array in O(m):

left[0] = solve(c_0, cnt + 1)

left[j] = left[j - 1] * solve(c_j, cnt + 1)

and similarly for right.

Putting these two together:

solve(x, cnt) = \sum_{i = 1}^{m} (left[i - 1] * solve(c_i, cnt) * right[i + 1])

Remember that all calculations are modulo 19101995.

Complexity

How many possible states are there? There are n possible values for x and since we stop when cnt is log_2 n, the total number of states is O(n log n). Work done in each state is equal to the number of edges from that node. So, overall we can add them up and they will be equal to n - 1 - the number of edges. So, overall complexity is still O(nlogn)

AUTHOR’S, TESTER’S and Editorialist’s SOLUTIONS:

setter
tester
editorialist

1 Like

WEAK TESTS

written in bold, italic and double heading style, because my code is O(N^2\log{N}) for stars (it easily runs over 10 seconds) and it gets AC with 0.15 seconds worst case. Seriously, no star? That’s one of the basic tests for beating slow codes when the input is a tree.

Thanks for the good question.

We would have solved this problem much more easily by making use of modulo inversion if given mod was some large prime say 1e9+7 :slight_smile:

1 Like

Can anyone please explain it in another way?

Next time write some testcases for N^2 solutions beforehand…

I just managed to fit in O(n(logn)^2) solution using segment trees :smiley:

I am just wondering we had added test cases of star during the contest itself.

Yes, your code got TLE on the new added test case. You have got 55 points for the task.

I had 100 points 1.5 hours after the start of the contest.

Mind you, it’s not a good idea to add tests in the middle of / at the end of the contest.

1 Like

@gdisastery1: I think no \mathcal{O}(n^2) passed in the problem.

@dpraveen Please read Xellos’ entry - I was in the same situation. I was immersed in another problem and without any notification system there was no way to figure out that my solution to this problem has been rejudged as WA ;( Luckily, I saw this at the very end of the contest.

I think the notification system needs to be improved regarding these kind of scenarios. I will ask codechef developers regarding this.

IMHO, it was a good idea to add tests in the middle of contest because we thought that letting \mathcal{O}(n^2) solutions pass is injustice to people who have used expected algorithm to pass the problem.

Nope it’s just ethically wrong and never practiced in any kind of contests where the prize is high (see IOI especially).

It’s better than not adding these tests in that ppl will learn more on it, but it’s not fair to anyone who thought they have a full score on the problem and ignored it or something. 1.5 hours is plenty of time to lose interest in trying anymore and go do something else. It’s generally bad practice to change results in the middle of a contest.

2 Likes

I second @xellos0 's view. Once the contest has started, no test files should be added or removed. Definitely not after half the contest. A similar thing happened at IOI 2014; some test files were dropped for a question after the contest because of constraints violation and a re-evaluation was performed. This was heavily criticised. As @gdisastery1 says, it is unethical to change the data once even a single contestant has attempted and got points on it.

Personal Opinion
I am not getting the unethical part. How is this ethically wrong? The person who submitted the solution knows very well that his solution should get TLEd. So ideally, he should not be getting points for that solution.

In this situation, Jury had missed a test case which we had realized a lot before. It’s not like taking one’s submission and doing stress test to find the test case against it.

Personally, I think that adding test cases is ok.

Being unethical? No. We haven’t cheated or lied. Being unfair? Yes. We agree that it is undesirable to change test data once the contest has started. There is no argument here. However, due to human errors, at times the identification of the test data being weak happens only during the contest. At that time we have mostly a couple of options. Either change the test data at that time or leave things unchanged. Both are unfair to a different set of people. For the sake of a better contest, we tend to falter towards the first. And we agree that it is being unfair to a set of people.

A better use of the notification system could have notified the users who were on the system. But still there is no way to make everyone aware of the changes. This is an exceptional situation and we do apologise. Going ahead, we would try and avoid this scenario. In case, we are unable to, we will try and notify users in a better way and extend the contest. I hope this would not need to happen.

2 Likes