Chef and Ants ANTSCHEF SOLUTION Code Chef

Chef and Ants ANTSCHEF SOLUTION Code Chef

Chef and Ants ANTSCHEF SOLUTION Chef has been researching ant colonies for many years and finally discovered all their secrets.
An ant colony consists of N distinct lines (numbered 1 through N) that pass through a point O, which is the queen’s home. For each valid i, there are Mi ants on the i-th line.
For each valid i and j, the j-th ant on the i-th line initially has a non-zero coordinate Xi,j with the following meaning:

 

The distance of this ant from O is |Xi,j|.
Let’s choose a direction along the i-th line from O. The exact way in which this direction is chosen does not matter here, it only needs to be the same for all ants on the same line.
If Xi,j is positive, this ant is at the distance |Xi,j| from O in the chosen direction. Otherwise, it is at this distance from O in the opposite direction.
In other words, two ants j and k on a line i are at the same side of O if the signs of Xi,j and Xi,k are the same or on opposite sides if the signs are different.
 
All ants move with the same constant speed. Initially, all of them are moving towards O. Whenever two or more ants meet (possibly at O), all of these ants turn around and start moving in the opposite directions with the same speed. We call this a collision. Even if an ant reaches O without meeting an ant there, it keeps moving in the same direction. An ant may change direction multiple times.Chef and Ants ANTSCHEF SOLUTION
 
Help Chef find the total number of collisions between ants. Note that even if more than two ants meet, it counts as only one collision.
 
Input
  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a single integer N.
  • N lines follow. For each valid i, the i-th of these lines contains an integer Mi, followed by a space and Mi space-separated integers Xi,1,Xi,2,…,Xi,Mi.
Output
For each test case, print a single line containing one integer ― the number of collisions between ants.
 
Constraints
  • 1≤T≤1,000
  • 1≤N≤2⋅105
  • 1≤Mi≤5⋅105 for each valid i
  • 1≤|Xi,j|≤109 for each valid i,j
  • Xi,j<Xi,j+1 for each valid i,j
  • the sum of N over all test cases does not exceed 2⋅105
  • the sum of M1+M2+…+MN over all test cases does not exceed 106
Subtasks
Subtask #1 (30 points): N=1
Subtask #2 (70 points): original constraints
 
Example Input
1
2
2 -2 1
1 2
Example Output
2
Explanation
Example case 1: First, the ants on the first line collide at the coordinate −1/2 and change directions. Finally, ant 2 on the first line collides with the only ant on the second line; this happens at O. No collisions happen afterwards.Chef and Ants ANTSCHEF SOLUTION
 

6 thoughts on “Chef and Ants ANTSCHEF SOLUTION Code Chef”

Leave a Comment

close
error: Content is protected !!