I tried to solve CEOI 2017 Day1 problem — Mousetrap today during the csacademy mirror.
My idea is a bit different than what model solution does, but in the same time complexity O(nlogn).
I'll describe it briefly. First, let's assume we can freeze the mouse for a while and prepare the way for her. Let's calculate answer for this case and call it pathOnly. This is computed by the simple formula.
Now let's unfreeze the mouse. We will do binary search on answer — how many additional operations do we need now. Let's precalculate cost[] for each vertex x, meaning: how many additional operations if mouse gets to vertex x and stays there forever. Forever means in this case: until we prepare the rest of the graph for her.
Cost is computed by a simple recursive formula : cost[onPath] = 0 and cost[x] = cost[parent[x]] + degree(x) — 1 otherwise.
Now let's move to the last step of the solution. Assume we are at some step of binsearch checking if the result can be not greater than k now. If a vertex has cost bigger than k, we should never let the mouse reach it. Otherwise, the mouse can safely get to that vertex. We compute dp[x] now -> how many operations do we need to succeed to be done before the mouse enters vertex x, dp[x] can be either 0 or 1. When a vertex is forbidden or sum of dps from its sons is greater than 1, dp[x] equals 1. Otherwise, it is 0. In the end, if dp[root] > 0, the answer for our current k does not exist and does exist otherwise.
The problem is that this solution doesn't work in at least two ways. I believe the implementation is O(nlogn) and should fit in the time limit, but it fails a lot. It gets WA twice, too. I would be very grateful if someone expressed his opinion about it.
Thanks in advance. PS. How to link the submission on csacademy?
