ANTSCHEF - Editorial

he is saying that if the ants are identical then it does not matter that they collide in a line and change direction or not the end result is the same. Then end result changes only when they collide at O and change direction

Adhe asalu solution ahhra(enka template anukunna ra babu)…
edhakkade scam ra babu

Why do we need O(m log_2 m) ?

Is this only for sorting? Aren’t the ants already sorted on each line? If so, Sorting by distance from O is an O(m) operation as well?

For individual lines, your observation is correct. However, we want to sort all ants on all lines by distance from O.

Assuming that the author of this problem uses m = \sum_1^N M_i, concatenating all ants of all lines in one big list and sorting that, indeed takes \mathcal O(m \log_2 m).

You could also go for an N-way merge approach, where you fill the sorted list of ants by taking the ant closest to O one by one. If you sort the lines in a priority queue by which line has the ant closest to O, that would take \mathcal O(m \log_2 N).

Since the upper bounds of N and m are similar in size, it should not matter which of these two sorting approaches you take for this problem :slightly_smiling_face:

But why do we need to sort all ants of all lines in one big list?

For finding out collisions of an ant with other ants on same line, we don’t need to sort this big list but only need the small sorted lists. where each small list is sorted in O(M_i) so all small lists are sorted in O(m) .

For finding out collisions at origin, we again don’t need to sort this list as we only need to count all absolute values of indices which have a count more than 1

Of course i agree with the log factor in answer if the ants were not already sorted for each line.

Sorry if I am missing something, (I did get AC on this problem in O(m) )

I’ve looked up your solution, and it is indeed \mathcal O(m), nice!

If I read the original solution correctly, it considers all ants on all lines at once, which is why it needs to sort a list containing all ants. On the other hand, your solution first calculates the collision locations (and stores them in a dictionary) and then calculates the collisions one line at a time. With your solution, you never need to do any sorting indeed :smile:

1 Like

I am so disappointed in myself. I was able to conclude almost everything as explained in the editorial, but even then I was not able to solve the problem,(probably presuming that the idea of “ants crossing each-other” was too bizarre to be correct). It hurts, real bad. I need to trust myself and my instincts a bit more. There always a next time…

Why I am getting WA? Link If someone can provide some testcases that will be good.

Edit: Got AC.

you didn’t get the point what he tried to said that if ants on the same line doesn’t have co-ordinate equals to co-ordinates of ants of different lines…then would be similar whether the ants change the direction or just pass.