PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Author & Editorialist: Arayi Khalatyan
Tester: Radoslav Dimitrov
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;
}
)
Very nice problem overall! 
