My logic in this question was different than this… I use set in c++ and depth of each node only to compute the answer.
I am briefly explaining my implementation details here-
Run dfs on the tree. Store the depth of each node while traversing. Also for each node, in a separate array, say arr ,store the node which is its closest free ancestor. This can be computed while during dfs.
After this insert all the nodes with tokens in a set in the form of pair - {depth[node], node}.
Run a while loop till size of this set is non-zero. Pop an item from the last.
The depth to which this node should move to is given by depth[arr[node]] but it may be possible that it is already filled by some more deeper node before. So applying compression technique, find the closest free ancestor of this node and update the answer as depth[node]-depth[free_ancestor].
Can anyone tell what do they mean by finding the deepest node ??
1
8
00110010
1 1 3 3 3 2 2
In this case, if we take the deepest node for 1 which is 7, and move it then it will give the wrong answer according to editorial logic.
but the code provided by setters works fine.
can anyone tell am I missing something or not understanding the editorial correctly ??
Before solving for 1 , you will solve for 2 and 3 , and while solving for 2 you will make the 1 on 7 as 0 and 0 on 2 as 1 , then max depth for 1 would be depth of 4.
Do you know what is exactly meant by offset in 3rd solution ? .
I have one other approach for this question . The approach is as follows:
Sort the token nodes in non - decreasing order of their depths. Now start shifting them to the farthest ancestor such that , the ancestor node does not have any token above it. To to this , we can mark tin (in time) of node as 1 if there is a token in it , and 0 otherwise.
To find such an ancestor , we can use binary lifting. Suppose for our current node u , we want to check whether node v has a token above it or not. To do so , we can simply query the sum from root to v. If the sum is 0 , there is no token above it , otherwise there exists some token(s) above it . We can use fenwick tree to find the sum. After shifting , update the value of tin[v] to 1.
Can anyone tell my approach is correct or not ?I am finding some difficulty in the query part.Thanks!
Can anyone please tell me, how can I optimise my code further… I am getting TLE on 3 test cases.
Its a bit slower because I used array of size 8*N for implementation… Can I make any optimization with this approach… https://www.codechef.com/viewsolution/47295270
Can anyone help me debug this code ,
My approach is:
store last index of all continuous chain of tokens for the subtree
if root of subtree doesn’t have token, move path with token with max depth 1 up.
finally check for no repetitons. https://www.codechef.com/viewsolution/47296362
I used a different approach. I use BFS to traverse the tree from the root node and then if any node has a token, then I use Binary Lifting to find the position of the top most node the token can go to, and I move the token there and update the string accordingly while calculating the number of steps moved up. The total number of steps that can be moved up for all the tokens is printed as the answer. This approach would also take O(N * LogN) time but my code shows WA. It passes the samples and I also tested with my own test cases. Yet, I couldn’t figure what the mistake in this approach is. It would be helpful if anyone can share any case or logical error for which my solution would fail. https://www.codechef.com/viewsolution/47300406
I think rather than creating an array of 2 * N to build the tree, you can create an array of size N as described in the editorialist’s solution. If that is not clear how to create such an array you can refer this link in the section subtree and paths.
I did try to follow what was given in the editorial, but for some reason I am getting a WA. The last subtask is giving TLE which I will improve later but right now I am trying to figure out what’s wrong in my solution.
If anyone would like to have a look that would be a great help. https://www.codechef.com/viewsolution/47305853
Moving the deepest token directly to the node makes sense because
the
number of moves needed to move all the intermediate nodes in the path to their nearest ancestor is equal to the number of moves needed to move the deepest node to the current node.
I have used same approach as given in the editorial but it is still giving WA . Can anyone point out my mistake in my CodeChef: Practical coding for everyone
Turns out this problem was actually an exact copy of CodeForces 965E, but with tighter limits so that small to large merging doesn’t work. In case anybody is curious original problem link. Nonetheless I found this problem’s idea very interesting, it’s just a bit unfortunate it’s a recycled problem.