If you want to look on a code having exact same idea but bringing up the chain brute forcely then you can look at my code
1 Like
Can someone tell me why this approach does not work. In my thinking it should have worked. In the map i am storing the lev,node pair and whenever we reach a node with coin we can move that to the uppermost free level. It is gauranteed that in the path the coins will only be on top not in the middle since they are removed when reached. Also the sum of jumps should not matter whether coins from deepest are moved first. Fail cases and critics are much appreciated.
Thanks
My approach: CodeChef: Practical coding for everyone
Yup this is what I meant with my comment. Thanks for clarifying
Oh right. Thanks a lot !
You are wrong in this fact , actually moving a branch up doesnt mean moving a subtree up , you need to care about the subtree again , counter-reasoning , as if it would not had been the case you would had solved it even for real constarint using this approach.
1 Like
Nice problem. Just solved it. If you do not know how Euler Tour is being used check out the ‘Tree Queries’ chapter of cses handbook.
1 Like
Yeah, it’s the correct O(N) solution. Ref impl - CodeChef: Practical coding for everyone
Simply put in “Small to large merging with each subtree size bounded by the depth of the deepest node is just O(N)”.
2 Likes
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].
closest free ancestor what does this mean
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 ??
2 Likes
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 ? .
1 Like
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!
Link to submission : LINK
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
I understand offset in terms of the English language but I will try to solve by that way as well.
If I understand it I will explain here.
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
Can we do this question using Sparse table ???
I don’t think so , the main reason being you can’t update values in sparse table .
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