Can anyone please explain the approach to solve this problem, I have read its editorial but its not clear 
1 Like
I can explain you my approach to the problem.
Make a vector of coordinate of each ant and the max distance it can travel before meeting ant eater or going off grid.
Now iterate over this vector to find all possible pairs.
a pair is valid if the directions they are travelling allows them to meet in future and the distance of separation between them is even and less than or equal to the max distance the ants can travel.
Here’s the link to my submission.
https://www.codechef.com/viewsolution/24927921
1 Like
@all_too_well Thanks bro for helping but your code seems a little complex to me to understand 
can you please explain your approach with some example…?? 
3 3
R_D
_ _ -
R#U
for this test case maximum distance that can be traversed for each ant is as follows:
ant (1,1) can travel 2 units
ant (1,3) can travel 2 units
ant (3,1) can travel 0 units
ant (3,3) can travel 2 units
Now let’s start counting pairs:
ant 1 is moving towards right so it can only pair with ants that are moving up or down with j coordinate greater than that of ant 1 or ant that is moving towards left with same i coordinate.
if this condition is met we will check for another condition:
it is obvious that both need to travel equal distance before reaching the meeting point.
we can calculate the sum of distance of meeting point from both ants with abs(x1-x2)+abs(y1-y2).
Now distance that the ant needs to travel before reaching meeting point should be less than or equal to the max allowable distance for that ant.
checking all the conditions we can count the pairs.
ant (1,1) can form pair with ant (3,3) . max distance for both ants=2 and each ant needs to travel 2 units.
ant (1,3) can pair with ant(3,3) max distance for both ants is 2 and each ant needs to travel 1 unit.
1 Like
Here is how I solved the problem in the contest.
https://www.codechef.com/viewsolution/24926511
Just an overview of the approach:
Once an ant is visiting a coordinate, push it in a map an increment its count. At the end of each second if a coordinate is having more than or equal to 2 ants present there(say n), then it would total of nC2 ant pair interaction.