# PROBLEM LINK:

Practice

Div-3 Contest

Div-2 Contest

Div-1 Contest

* Author & Editorialist:* Arayi Khalatyan

*Radoslav Dimitrov*

**Tester:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Greedy, Implementation, Observation

# PROBLEM:

There are N lines each of which is passing through a point O. There are M_i ants on the i th line and initially all the ants are moving towards the O. All the ants are moving at a constant speed and they never stop. Each time when an ant meets another ant(ants) it turns around and goes in the opposite direction. When two or more ants meet it is called a collision. Find the number of collisions.

# QUICK EXPLANATION:

## main observation

Letâ€™s assume that two ants from the same line met. Right after the collision the first ant will start to move in one direction and the other ant will start to move in the opposite direction. The same would happen if they passed through each other instead of turning around (see this animation).

## help for implementation

Separately count the number of collisions at O and at other points on lines (assume that if two ants from the same line collide they pass through each other).

`map`

can be used for counting the number of collisions at O.

For counting the number of collisions happened on a line, we can

- count how many ants will meet the closest ant to O on that line.
- remove that ant.
- repeat.

# EXPLANATION:

### Main idea

Letâ€™s assume that two ants from the same line met. Right after the collision the first ant will start to move in one direction and the other ant will start to move in the opposite direction. The same would happen if they passed through each other instead of turning around (see this animation). This means that problem can be changed into *an ant changes itâ€™s direction if and only if it meets another ant at O*.

### Subtask #1

Here all the collisions will happen on the first line. This means no ant will change itâ€™s direction. So two ants will meet if and only if their coordinates have different signs and they move towards each other. The answer will be * number of ants with positive coordinate* *

*.*

`number of ants with negative coordinate`

### Subtask #2

Letâ€™s count the number of collisions at O and at points other than O separately and then sum them up. First, letâ€™s create `map<int, int> coord`

where `coord[x]`

is the number of ants with x coordinate.

##### Collisions at O

We need to find the number of x 's that `coord[x]+coord[-x] > 1`

which means that two or more ants will arrive to the O at the same time, because there are 2 or more ants at distance |x| from O

Also we can construct an array with different coordinates of ants for this.

##### Collisions on lines

For every valid i letâ€™s count the number of collisions on the i-th line. Letâ€™s sort them in increasing order by their distance from O.

- Take the nearest to O ant, letâ€™s assume itâ€™s coordinate is X_{i,j} . It wonâ€™t meet any ants until O(because it will get there first).
- If it collides at O(coord[X_{i,j}]+coord[-X_{i,j}]>1): the ant will turn around at O and will collide with the ants that were behind it. The answer will be increased by the number of ants that had the same sign coordinate.

If it doesnâ€™t collide at O(coord[X_{i,j}]+coord[-X_{i,j}]\leq1): the ant will continue to move in the same direction and will collide with the ants that were in front of it. The answer will be increased by the number of ants that had the opposite sign coordinate. - Remove that ant.
- Repeat.

# Time complexity

O(mlog_2m) If you have any other solutions write it in comments section, we would like to hear other solutions from you)

# SOLUTIONS:

## Setter's & editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int t, n, m;
long long ans;
vector <int> ant[N];
map <int, int> coord;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> t;
while (t--)
{
cin >> n;
ans = 0;
vector <int> distances;
for (int i = 0; i < n; i++)
{
cin >> m;
while (m--)
{
int x;
cin >> x;
coord[abs(x)]++;
if (coord[abs(x)] == 1) distances.push_back(abs(x));
ant[i].push_back(x);
}
}
for (int i = 0; i < n; i++)
{
long long pos, neg;
pos = neg = 0;
vector<pair<int, int> > s;
for (auto p : ant[i])
{
if (p < 0) neg++, s.push_back({abs(p), -1});
else pos++, s.push_back({abs(p), 1});
}
sort(s.begin(), s.end());
for (auto p : s)
{
if (p.second == -1) neg--;
else pos--;
if (coord[p.first] > 1)
{
if (p.second == -1) ans += neg;
else ans += pos;
}
else
{
if (p.second == 1) ans += neg;
else ans += pos;
}
}
}
for (auto p : distances) if (coord[p] > 1) ans++;
cout << ans << endl;
for (int i = 0; i < n; i++) ant[i].clear();
coord.clear();
}
return 0;
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int n;
vector<int> a[MAXN];
void read() {
cin >> n;
for(int i = 0; i < n; i++) {
int sz;
cin >> sz;
a[i].clear();
while(sz--) {
int x;
cin >> x;
a[i].pb(x);
}
}
}
void solve() {
// subtask 1
int64_t answer = 0;
map<int, int> cnt;
for(int i = 0; i < n; i++) {
for(int x: a[i]) {
cnt[max(x, -x)]++;
}
}
for(int i = 0; i < n; i++) {
vector<pair<int, int>> ord;
array<int, 2> contribution = {0, 0};
for(int x: a[i]) {
if(x < 0) {
ord.pb({-x, 1});
contribution[1]++;
} else {
ord.pb({x, 0});
contribution[0]++;
}
}
sort(ALL(ord));
for(auto it: ord) {
contribution[it.second]--;
answer += contribution[it.second ^ (cnt[it.first] <= 1)];
}
}
for(auto it: cnt) {
if(it.second > 1) {
answer++;
}
}
cout << answer << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
```