TRTOKENS - Editorial

editorial
, , , , , ,
22

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
23

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
24

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

25

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

26

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.

27

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

28

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

29

Can we do this question using Sparse table ???

30

I don’t think so , the main reason being you can’t update values in sparse table .

31

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.

32

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

33

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 hope this makes sense.

1 Like
34

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

35

Hey , why

what will be the cost of this? I guess the number of ones leading to the deepest 1 right?

36

I am trying from past 2 days but not able to get AC on single test case.

Solution Link: https://www.codechef.com/viewsolution/47363257

Please tell me where i am wrong: @cherry0697 @taran_1407 @ssjgz @jtnydv25

37

Finally Got AC.

38

Nice

39

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. :frowning: