PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: krrishmath
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting
PROBLEM:
There are N balls on the x-axis.
The i-th is at position A_i, and moves with a speed of B_i units per second towards position 0.
If two balls collide strictly before reaching 0, they merge into a single ball with the speed of the faster one.
Find the number of balls that will reach the origin.
EXPLANATION:
When two balls collide, they merge together with the speed of the faster one.
An alternate way of thinking about this, is that the slower ball simply disappears entirely.
So, we want to count the number of balls that don’t disappear before reaching 0.
Let’s look at the i-th and j-th balls, and see when they can possibly collide.
Suppose A_i \lt A_j.
Then, they can only possibly collide if the j-th ball reaches 0 strictly before the i-th ball.
Comparing their times taken to do so, we see that
must hold.
Now, we’re only concerned about which balls reach 0 eventually.
From the above, we see that the i-th ball reaches 0 if and only if no j like the above exists: that is, there is no j such that A_j \gt A_i and \frac{A_i}{B_i} \gt \frac{A_j}{B_j}.
Let’s sort all the balls in ascending order of their A_i values.
Now, when looking at the i-th ball, we’re only concerned with j \gt i.
Among all these j, we’d like to know if \frac{A_i}{B_i} \gt \frac{A_j}{B_j} for any of them.
Note that the LHS is fixed once i is fixed, so we only really care about the minimum possible value of the RHS.
In simpler words, once i is fixed, we only care about the minimum time to reach the origin, across all balls that start to the right of i.
This gives us the following algorithm:
- Let m be the index of the ball that reaches in minimum time, so far.
- For each i from N to 1 (in descending order),
- Compare \frac{A_i}{B_i} to \frac{A_m}{B_m}.
- If \frac{A_i}{B_i} is larger, ball i will not reach the origin.
- Otherwise, it will reach, so increase the answer by 1.
Note that in this case, we must set m = i, since \frac{A_i}{B_i} is the new minimum.
A note on precision
Our algorithm requires us to compare fractions of the form \frac{A_i}{B_i} against each other.
Since A_i, B_i can be between 1 and 10^9, it’s possible to have cases where directly dividing and comparing them using floating-point variables (such as float or double) will not have enough precision - one such case was provided in the sample tests.
To get around this issue, comparisons can be done entirely using integers with the help of cross-multiplication.
That is,
So, comparing A_i\cdot B_j against B_i\cdot A_j allows for fraction comparison using purely integers, which is completely precise.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll= long long;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<ll> arr(n),brr(n);
for (ll i=0;i<n;i++) cin>>arr[i]; // to store distances
for (ll i=0;i<n;i++) cin>>brr[i]; // to store speed
vector<pair<ll,ll> > crr(n);
for (ll i=0;i<n;i++) crr.push_back({arr[i],brr[i]}); // storing distance and corresponding time
sort(crr.rbegin(),crr.rend());
ll min_num=INT_MAX,min_dem=1; // trying to find the minimum fraction
ll count=0;
for (ll i=0;i<n;i++)
{
ll a=crr[i].first;
ll b=crr[i].second;
if (a*min_dem<=b*min_num) // comparing fractions
{
min_num=a;
min_dem=b; // updating minimum time
count++; // incrementing count
}
}
cout<<count<<endl;
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool is_greater(pair<int, int> &a, pair<int, int> &b){
return a.first * b.second > b.first * a.second;
}
int32_t main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
pair<int, int> a[n];
for(int i = 0; i < n; i++){
cin>>a[i].first;
}
for(int i = 0; i < n; i++){
cin>>a[i].second;
}
sort(a, a + n);
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
while(1){
if(v.size()){
if(is_greater(v.back(), a[i])){
v.pop_back();
}else{
break;
}
}else{
break;
}
}
v.push_back(a[i]);
}
cout<<v.size()<<"\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
indices = list(range(n))
indices.sort(key = lambda x: (a[x], b[x]))
ans = 0
num, den = 10**9 + 1, 1
for i in reversed(indices):
x, s = a[i], b[i]
# will reach at time x/s
# unless something after it reaches strictly before
# so, store minimum reach time so far
if x*den > num*s: continue
ans += 1
num, den = x, s
print(ans)
, Thanks a lot