I just simulated efficiently, observed that an assassin who moves to a town that is not a leaf at that moment will always be killed by its descendants. So I kept checking this condition, but I couldnât prove the actual time complexity of my solution. If someone can prove the time complexity or hack my solution if possible 
2 Likes
This question can also be solved by storing IN Time(in and out time concept) as parameter to sort nodes at which assassins are. And then Linear Algorithm to find who kills who as all nodes in subtree will be one after another after sorting. This approach will also take O(NlogN) time.
3 Likes
dp array is storing the minimum days require to reach a node by all the assassins present in the subtree of that node.
This part is based on what is given in the editorial. If all the assassin (in the subtree of x) are not reaching on the same day then it will take 1 more day for the rest of the assassin to kill the assassin that will reach first. so dp[x] = (1 + minimum time require to reach its immediate child) + (1 if they all does not reach at the same time).
2 Likes
got it. Thanks a lot.
My Solution is O(N), and itâs pretty simple I only used dfs.
but itâs pretty different from everyoneâs solution here
Can anyone provide test cases for the failing items in the below submission? I have tried lots of different trees and all seem to be working fine 
https://www.codechef.com/viewsolution/46604947
Try this:
1
19
1 2
2 3
3 4
2 5
5 6
6 7
7 8
8 9
9 10
10 11
6 12
12 13
13 14
14 15
6 16
16 17
17 18
18 19
Expected output:
3 4
11 15 19
Thank youâŚ
Why does smaller to large set merging not pass? Shouldnât this be O(nlogn)? CodeChef: Practical coding for everyone
Thanks, This comment really made my day. This is the first problem I have authored so it means a lot to me ^_^.
3 Likes
really appreciable problem 
Yes, please if someone can provide some test cases. I just saw pes2020âs solution and it has failed in exactly the same test cases as my solution. Many others may also benefit if they are failing on these test cases
I canât understand your code but my idea ( code) was similar and had O(N) complexity + sorting at the last
My method for this problem is way different, I did a complete simulation of where each person is each second. Still got ac for 100 points by using some smart optimization.
- Convert to a weighted tree. and remove all intermediate nodes with only 1 child(Assasins never get killed here). For example, if we have a tree with 4 nodes connected like this 1-2-3-4,
i.e., 2âs only child is 3 and 3âs only child is 4.
I will connect 1-4 and store weight[1,4] =3. - Store a parent array for each node in the new graph.
- Now do the simulation like this, among all assassins, find the minimum distance to their parent,
send all the min ones to their parent, rest all reduce the distance to their parent by the min value. Increase time by that value. - Now, make a temporary variable to keep traversing up the tree to check if an assassin is present there. if present, move to the topmost node where the assassin is present in that path and make parent of all the nodes in this path as the topmost node where the assassin is present.
Keep doing this till some people reach 1.
Alternative for 4, do DFS from the assassins that reached their parent node on its subtree and find who all will reach there.
Got AC with no DSU or DFS for the simulation of the entire system.(did dfs to convert to weighted tree and getting parent array only)
With some bit of extra code My code can even tell the position of a given assasin at a given instant for 10^6 queries ,lol
1 Like
Even I did a similar unorthodox method, see to my other comment, but I think both our solutions are worst-case O(N^(3/2)) but very small constant. I also think they didnât think of a test case for our methods lol 
Hi, I have an easy linear time solution which I have explained in the official video editorial of the problem (itâll be uploaded in a few hours by the codechef team on the yt channel).
7 Likes
Yes, I too got 100 points using a simple algorithm, using no sets or any other data structure more complicated than a tree and variable length arrays (lists). The only special code was the use of time-in and time-out for each node in order to determine rapidly whether one node is the ancestor of another. I found this problem easier than Valid Paths, although the latter received more than 7 times the number of correct answers. Essentially the method is:
Create and maintain an array of assassins at each node and an array of all occupied nodes, which are those with assassins.
Loop one day at a time until finished:
Move every assassin to its parent node.
If the root (capital) contains any assassins, finished!
Sort the occupied nodes by time-in. Then a node can be the ancestor only of one or more nodes immediately to its right. For each occupied node âIâ find the last node J of which it is an ancestor, if any.
If found any J,
-
remove the assassins from node I.
-
set node J so that its parent is node I. Then the next day the assassin(s) at J will move to I.
-
for each node K where I < K < J: If K is an ancestor of (K+1), remove the assassins at K as they will not survive those at K+1. Else set the parent of K to be I, as was done for J.
-
set I = J
End of loop.
You can find my solution at CodeChef: Practical coding for everyone
1 Like
I did it in O(n).
I used some kind of dp and dfs , and then constructed the solution using that (that was the tricky part).
Basically, a assassin would be killed if it reached a node (not 1) before the other alive assassins in the subtree of the node and if they reach simultaneously, then they move together.
So, we need to get the minimum and maximum time taken by alive assassins from a subtree of node to reach it.
If node is not 1:
i) If the minimum and maximum are the same, then the time required to reach this node for alive assassins would be the same equal to the minimum.
ii) Else, the time would be minimum + 1 and minimum ones would not be taken(but we donât care about it now, we will use the timings later to see which child give us a solution).
If the node is 1, then the minimum one would be taken.
This could be constructed in top-down fashion easily using dfs.
One point is that the node may be never visiting a node and we taking out the time for each of them, this is just to get the time of the assassins, obviously, the assassins can take much less time by jumping to the position of an assassin above him and that we have taken care of already above.
Now, the difficult part is to get the leaf nodes that reach our node 1.
We will use the timings that we get for each node, so we need to store that from above.
Now, at node 1, the child of node 1 that gives the minimum time to reach would be ones from where our winners would be coming.
so, we move to those nodes.
Now at each node, we will see the child giving maximum and minimum time to reach, the minimum one may be taken out by the maximum, yes maybe as they both may basically kill something above them and reach there simultaneously. So, to take this into account, we will also maintain the smallest day, on which killing was done.
i) Now, when we get maximum and minimum different:
Then we will check if the smallest day event above our present node was less or equal (less or equal is important as all assasins above would be killed) than our present event(which will be at minimum ), then all the child will give our solution and we recurse to them and do not update the smallest day event.
else, we will knock out the minimum, update the smallest day event and recurse to other children.
ii) Now, when we get maximum and minimum same:
we do not update the smallest day event and simply recurse to all the children.
Now, if we arrive at a leaf node, we include that in our solution.
If there is something wrong, please let me know.
1 Like
Right Sir
Time complexity looks O(n ^(3/2)) , I think it is hackable(to TLE) with specific test cases targeting your code.