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 
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 
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ā¦
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.
Nice question.
Thanks to the problem setter.