ATWNT - Editorial (work in progress)

# DIFFICULTY:
Medium

# PREREQUISITES:
dfs, eratosthenes sieve

# EXPLANATION
For the first subtask, the size of the tree is small enough so you can implement algorithm straightforward.

For the full solution, first of all, we need to merge every node v with his child if v has 1 child. After that, since we do every work on the leaf and every node other than leaf has degree > 1, if we calculate path from leaves to nodes the path value, for particular leaf we only need to consider log(10^6) parents of the leaf.
Now after we calculated for every leaf v every possible value of the path. We can solve for all queries in “offline” by eratosthenes, we iterate over every possible path from v to leaf which is divisor of w

VIDEO EDITORIAL:

i calculated the divison factor for every node.

divison factor means number of division that a node can perform from itself to any reachable leaf node.

if the number of given tasks modulo divison factor of given node is zero then all the tasks get executed so answer is 0
else in other case i calculated maximum possible tasks that can be solved and this will be equal to the gcd of division factor of node v and the number of tasks w and if we divide the number of tasks by gcd then we will have non executed tasks.

but i am getting WA and SIGFPE

https://www.codechef.com/viewsolution/428155581

An interesting point is that factorization doesn’t seem necessary at all for w during queries. One of my friends used the fact that the number of distinct product of degrees till a leaf must be small, so if we keep track of the count in a map for each node, the construction is is still O(n * log^2(n)) but we can naively answer queries by just checking if each value in the map divides it.

While the proof for this is likely trickier than that for the editorial idea, at least intuitively it seems true, and in practice it appears to run faster than my solution which solves the problem in a similar manner to the editorial in O(n * log^2 n + q * (\sqrt{W} + divisors(W) * log(n)).

So for each query we would traverse all the leaves that would have some contribution ( the product of sizes of the parents of the leave is less than 10^6). I was able to generate some cases where the number of distinct leaves which have some contibution came around 600 to the root node ( each node has 2, 3, 4, 5, 6 or 7 children). So was Q * 700 the inteded solution ? I just felt the test cases were a bit weak.
Upd: That 700 hundred comes from the fact that the number of distinct leaves cannot be more than sqrt(N). But how does compressing the tree help ( removing the nodes that have only one child ), for me it just looks like a random heuristic that worked.
I am sure I am missing something and it would be helpful if someone points it out.

I found a slightly different solution that worked. As in the editorial I merged nodes with only 1 child, but then used simple recursion. I however speeded this up in two ways:

  1. I pre-calculated a “perfect” value for each node, which is the minimum non-zero value required for a node to perform all tasks assigned to it. If the number of tasks is any multiple of this then all tasks will be completed
  2. I cached the results for every node in a map (Python dictionary).

Neither of these is guaranteed to make a difference, however, between them they got me full points.

https://www.codechef.com/viewsolution/42741412

2 Likes

https://www.codechef.com/viewsolution/42793832

Can anyone tell me why this is getting tle in the first subtask? Thanks

hey can you explain how you did the merging part that is merged node only with 1 child.

In your function “lost” you are passing a vector g, what this is doing is you are actually passing a copy of vector g every time and this is time consuming for large vectors . So you should pass by reference like this:-
ll lost(vector<vector<ll>> &g, ll u, ll k)
your solution with just the ‘&’ changed-Solution: 42840111 | CodeChef
Only the last 3 task tle.

2 Likes

Ah I see… Thank you very much. This simple stupid mistake probably cost me 300 ranks :sweat_smile:

thanks it work after many time wa

Having found the children of each node I created a Disjoint Union (see Disjoint union - Wikipedia). If a node only had one child I placed it and its child in the same set set. This gave me sets of nodes with each set containing precisely one node with either 0 or more than 1 child. I could then treat each of these sets as a single node for the recursion.

1 Like

I got it
thanks for the explanation