KKLING - Editorial

[rahulmysuru7]

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.

1. 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.
2. Store a parent array for each node in the new graph.
3. 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.
4. 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)

code

code

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

[rahulmysuru7]

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

[demoralizer]

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).

[david_s]

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

[shobhit10058]

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.

Submission

If there is something wrong, please let me know.

[ssuuyyaasshh]

Right Sir

[rahulmysuru7]

Time complexity looks O(n ^(3/2)) , I think it is hackable(to TLE) with specific test cases targeting your code.