CRSHIT - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia Soltani

Editorialist: Kasra Mazaheri

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Observation, Two-Pointers

PROBLEM:

There are N cars on a circular race track of circumference K. The i-th car is X_i meters away from the start point of the race track in the clockwise direction and is either going in clockwise (D_i = 1) or counter-clockwise (D_i = 2) direction with the constant speed of 1. Whenever two cars crash into each other (not necessarily in an integer point), they both change the direction they were going and continue driving in the new direction. Find the number of crashes that will happen until the T_i-th second for Q queries.

QUICK EXPLANATION

  • Whenever two cars crash, we can assume that they pass right through each other (they continue in the same direction they were going). This doesn’t affect the number of crashes.
  • Since now no car changes it’s direction, crashes only happen between the cars that have different values of D. As a result, we can consider the cars with D_i = 2 to be stationary and the cars with D_i = 1 to move with a constant speed of 2.
  • Every \frac{K}{2} seconds, a racer with D_i = 1 crashes into all the racers with D_i = 2. So we can count such crashes and we’re left with T < \frac{K}{2}.
  • Now for each pair of racers, at most one crash might happen. More specifically, a clockwise racer at position A will crash into a counter-clockwise racer at position B if and only if A \le B \le A + 2T or A \le B + K \le A + 2T. It’s easy to see that such racers belong to a continuous segment of the race track.
  • We can loop over the racer with D_i = 1 and keep track of the mentioned segment of the race track. It can be done with two pointers after sorting the racers according to their positions.

EXPLANATION

The crucial observation in this problem is that we can assume that racers pass right through each other and so they’ll never change their direction. This doesn’t affect the number of crashes since the racers’ ids is not important to us, only their positions matter. And whenever two racers crash, it’s as if they pass through each other but their ids gets swapped. Since we only care about their positions, we can simply assume that they can pass through one another. Now we can see that the racers will never change their direction. Since the racers that are going in the same direction can’t crash into one another, it’s safe to say that crashes only happen between the racers of the first type (D_i = 1) and the second type (D_i = 2). It’s easy to see that a crash’s time depends on the distance between the two cars and not their exact positions. As a result, we can assume that the racers of the first type move twice faster (with the constant speed of 2) and the racers of the second type remain still in their positions. This doesn’t affect the crashes since the distance between any two cars at any moment remains the same.

It’s easy to see that after \frac{K}{2} seconds, all racers of the first type will have had one lap around the race track and now they’re back in their initial positions. We can see that in a lap over the whole race track, a racer of the first type will crash into every racer of the second type. So we can easily count the crashes that will happen in the \lfloor\frac{T}{K}\rfloor laps. Thus now we’re left with the case of T < \frac{K}{2}. One can see that at such constraints, a pair of racers may only crash into each other at most once. We can then see that a racer of the first type at position A will crash into a racer of the second type at position B if and only if A \le B \le A + 2T or A \le B + K \le A + 2T holds. It’s easy to see that such racers belong to a continuous segment of the race track. For every racer of the first type, we can count such racers of the second type using binary search (assuming that we have sorted the racers of the second type by the positions). However we can improve this solution. We can see that if we increase the value of A by one, the continuous segment on the track (that corresponds to all valid B's) will also move forward by one. So if we found the segment for A = X_i, we could increase the borders of it until it fits A = X_j for X_i \le X_j. So we can actually do this for every racer of the first type, but in the sorted order of their positions. This way we only increase the borders of the continuous segment at most 2N times. This concludes the solution.

TIME COMPLEXITY

The time complexity is O(N \cdot (Q + log(N))).

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q; ll k;
vector < ll > A[2];
int main()
{
	scanf("%d%d%lld", &n, &q, &k);
	for (ll i = 1, d, x; i <= n; i ++)
		scanf("%lld%lld", &d, &x), A[d - 1].push_back(x);
	sort(A[0].begin(), A[0].end());
	sort(A[1].begin(), A[1].end());
	for (int i = 0; i < n - (int)A[0].size(); i ++)
		A[1].push_back(A[1][i] + k);
	for (; q; q --)
	{
		ll t, tot = 0;
		scanf("%lld", &t); t *= 2;
		tot += t / k * (ll)A[0].size() * (ll)A[1].size() / 2;
		t %= k;
		int l = 0, r = 0;
		for (ll a : A[0])
		{
			while (l < (int)A[1].size() && A[1][l] < a)
				l ++;
			while (r < (int)A[1].size() && A[1][r] <= a + t)
				r ++;
			tot += r - l;
		}
		printf("%lld\n", tot);
	}
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
 
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 
 
using namespace :: std;
 
const ll maxn=1e5+500;
const ll inf=1e9+800;
const ll mod=1e9+7;
 
vector<ll> vec[2];
ll k,t;
 
ll pl;
ll pr;
 
void resett(){
	pl=0;
	pr=0;
}
ll tedade(ll l,ll r){
	while(vec[1][pl]<l){
		pl++;
	}
	while(vec[1][pr]<=r){
		pr++;
	}
	return pr-pl;
}
 
 
ll findAns(){
	if(vec[0].empty() || vec[1].empty())return 0;
	resett();
	ll ans=0;
	for(ll i=0;i<(ll)vec[0].size();i++){
		ans+=tedade(vec[0][i],vec[0][i]+t);
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	ll n,q;
	cin>>n>>q>>k;
	for(ll i=0;i<n;i++){
		ll d,x;
		cin>>d>>x;
		vec[d-1].pb(x);
	}
	sort(vec[0].begin(),vec[0].end());
	sort(vec[1].begin(),vec[1].end());
	ll x=vec[1].size();
	for(ll i=0;i<x;i++){
		vec[1].pb(vec[1][i]+k);
	}
	for(ll i=0;i<q;i++){
		cin>>t;
		t*=2;
		ll r=t/k;
		ll ans=(r*(ll)vec[0].size()*(ll)vec[1].size())/2;
		t%=k;
		ans+=findAns();
		cout<<ans<<endl;
	}
	
}

Feel free to share your approach. As usual, suggestions are warmly welcomed. :slight_smile:

4 Likes

3 copies of this problem.
Codeforces
Atcoder
USACO -> Appeared in contest which ended last sunday.

First two ask for positions and third one asks for no of collisions.

8 Likes

this is exactly same as today’s problem…except that the array is circular but it is trivial to convert this problem to the usaco one.

2 Likes

I’m sorry to see that a similar problem appeared a while ago. Although, you might wanna know that the problems for this round were chosen around a month ago. About the other two problems I must say that they are much harder and different than this one. Only the first observation is similar in them which I expected to be well-known.

8 Likes

Only suggestion for codechef I have right now is recruit more testers. One tester is not enough. Pick any codeforces contest you will find 4-5 testers.

4 Likes

I submitted an O(NQlogN) code. Why did it get TLE ?

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

Time limit was set in such a way that O(NQlogN) gets TLE.

1 Like

Can you explain the part after this?

Sure. We want to find for all A_i, the first B_j that A_i \le B_j where A_i is the position of i-th clockwise racer and B_j the position of the j-th counter-clockwise racer. First we sort the arrays A and B in increasing order. Then if B_{j-1} < A_i \le B_j (i.e B_j is the answer for A_i), we can be sure that the answer for A_{i+1} is never less than j since A_i \le A_{i+1} and B_{j-1} < A_i, so B_{j-1} < A_{i+1}. Thus we can keep track of the value of j for each i, if we consider the elements of A in increasing order. By the same technique, we can find the last index h where B_h \le A_i + 2T. Then the i-th racer will crash with all the counter-clockwise racers with index in [j,h]. We can do the same thing for A \le B + K \le A + 2T. You can check here for more details on two-pointers technique.

1 Like

Thanks man!

because NQlogN will give TLE

Also does a 10^5 * 10^3 algo work in 2 secs ?
We ususally say 10^6 to 10^7 operations per second.

actually the i/o is really time consuming so more than 1e6 i/o really pushes the time but normal operations can be performed about 1e8 times but dont forget to use fast i/o as it might give TLE otherwise.

Nice explanation

I have a simple doubt which i feel has to do something which precision issues.

instead of doubling the value of ‘t’ in beginning, if we do that later like this:

	tot += (t / (k/2)) * (ll)A[0].size() * (ll)A[1].size() / 2;
	t %= (k/2);
	t*=2;

We get error in some test cases, can anybody throw some light on this.

I take 10^8 operations per second as normal as mentioned in Competitive Programming 3 by Steven Halim. Don’t take operations per second that low.

I ran this code on codeforces customtest and it ran in 1076 ms, while it was a synced cout. I think it is fairly even to assume them to be 10^8.

#include <iostream>

int main() {
    int i = 0;
    while(i < 10000000){
        std::cout << i++;
    }
	return 0;
}

1 Like

nice one learn many things

I don’t understand the time complexity part.
Can you explain this part?