ANTSCHEF - Editorial

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

  1. count how many ants will meet the closest ant to O on that line.
  2. remove that ant.
  3. 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.

  1. 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).
  2. 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.
  3. Remove that ant.
  4. 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;
}

VIDEO EDITORIAL:

8 Likes

13 posts were merged into an existing topic: Use this for anything related to plagiarism - Reporting cheating, appeals, etc

why my code is falling for Subtask 1.
https://www.codechef.com/viewsolution/41379796

you need to use long long instead of int, the answer may be very large.

this is wrong , in problem it is written collision possibly at O ,meaning that collisions can happen anywhere , lets for example happens at O as well … plz you have to mention which collisions are u talking of , and which collisions lead to turning of ants…

i wasted my whole time on this problem and at last u are saying that they will change only when they meet at O… collision is collision whether at o or somewhere else…

bad scripting of question …

1 Like

Collisions can happen anywhere but but we shud consider change in direction at point O collisions only.You may take change in direction at other collision as well but it is equivalent to just the two ants crossing each other.

1 Like

I had a slightly different solution: Solution: 41590342 | CodeChef (in the PRACTICE contest, because my original solution was a bit messy :innocent:)

The main idea remains the same: an ant changes it’s direction if and only if it meets another ant at O.

I extended this even further: if an ant meets other ants at O, the problem can be transformed by flipping that ant’s coordinate (and direction) w.r.t. point O. After flipping these ants, I run a “simulation” by moving all ants on all lines until no more ants can collide. This is of course not a step-by-step simulation, but for every ant I just calculate the new position as old\_position + direction \cdot max\_time, where max\_time is taken sufficiently large such that no more collisions happen after this time.

Then, the final answer becomes the sum of (the number of times that multiple ants were at O at the same time) and (the number of inversions on every line).

Counting the number of inversions on lines works, because the coordinate of a flipped ant will end up on the same coordinate as it would when doing a step-by-step simulation. The number of inversions on a line can be calculated by an adaptation of merge sort.

I like this solution because it does not require the removal of ants one by one, but instead transforms the input without changing the solution :smile: Very nice problem overall! :blush:

4 Likes

You can checkout my solution , implemented using priority queues and hash maps. I have also added comments for better understanding. (C++)

https://www.codechef.com/viewsolution/41593708

1 Like

what is the int range, how come this is accepted Solution: 41593875 | CodeChef and this is not Solution: 41415880 | CodeChef

If I run this in a practice submission on CodeChef:

cerr << sizeof(int) << " " << sizeof(long int) << " " << sizeof(long long int) << endl;

I get 4 8 8, i.e. int is 32-bits and the others are 64-bits. The answers to this problem indeed lie outside of the 32-bit range (i.e. larger than 4 billion).

Funny, because on my local machine, I get 4 4 8, so I have to use long long int to get a 64-bit integer :thinking:

1 Like

m was supposed to be less than or equal to 5*10^5

  • first one has b & c as long int while
  • Second has b & c as int due to which it overflows and gives wrong answer when you multiply b*c
1 Like

that means b*c is not displayed directly, rather its stored in b or c first ?

Yes, but for example, if you have 2\cdot10^5 ants left of the origin and 3\cdot10^5 right of the origin, you get an answer of (2\cdot10^5) \cdot (3\cdot10^5) = 6\cdot10^{10} or 60 billion.

2 Likes

int can only store values smaller than 2^32, but the answer can be larger than that, so you need to use long long.

1 Like

thanks to everyone, I thought b*c would be directly sent to the output stream

1 Like

Yes b and c are stored in output buffer they are not sent to output stream directly…

1 Like

but even this is not getting submitted Solution: 41595639 | CodeChef

As I already said b and c are int so when you multiply them it will overflow… the overflown answer is stored in ans…

The correction should be to first declaring b and c as long long then storing it in ans

1 Like

I did not knew all this, thank you

1 Like