PROBLEM LINK:
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. 