BALL_GAME - Editorial

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

\frac{A_i}{B_i} \gt \frac{A_j}{B_j}

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,

\frac{A_i}{B_i} \gt \frac{A_j}{B_j} \iff A_i\cdot B_j \gt B_i\cdot A_j

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)

long double did work for ai/bi

Yes it will. Long double will fail in higher numbers but then I guess integer overflow will happen with cross multiplication

1 Like

Can somebody please tell me why my code didn’t work?
here’s the link →
https://www.codechef.com/viewsolution/1088852329
I used the same approach of sorting and comparing every value with its next value, if (i) and (i+1) don’t collide then answer++.

Using long double does work for this problem: CodeChef: Practical coding for everyone

Your approach is a bit wrong you should traverse from last.
Why?
Consider a case where first ball takes 2s 2nd ball takes 3s and 3rd ball takes 1s. Your code will gove answer as 2 since 2<3 but correct answer is 1 as the last ball collides both with 1st and second.
Hope it helps

1 Like

By higher numbers i meant numbers greater than the constraints given

2 Likes

Yeah I should have traversed backward :smiling_face_with_tear: , Thanks a lot

did this, didn’t sort used a different logic saw the editorial and saw that i just needed to sort :,)

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;

class hehe{
public:    
    long long x, y;
    long double z;
    hehe(long long  x, long long y, long double z){
        this->x = x;
        this->y = y;
        this->z = z;
    }
};

bool func(hehe*a, hehe*b){
    return a->x < b->x;
}

int solve(vector<int>&a, vector<int>&b, int n){
    // speed b, and pos a
    vector<hehe*>v;
    for(int i=0; i<n; i++){
        long long x = a[i];
        long long  y = b[i];
        long double z = ((long double)x/(long double)y);
        
        hehe *newNode = new hehe(x,y,z);
        v.push_back(newNode);
    }
    
    sort(v.begin(), v.end(), func);
    
    int ans = n;
    long double last_speed = v[n-1]->z;
    for(int i=n-2; i>=0; i--){
        if(v[i]->z > last_speed) ans--;
        else{
            last_speed = v[i]->z;
        }
    }
    
    // for(auto it:v){
    //     cout<<it->x<<" "<<it->y<<" "<<it->z<<endl;
    // }
    // cout<<"ans ";
    
    for (auto obj : v) {
        delete obj;
    }
    return ans;
}

int main() {
	// your code goes here
	int t; cin>>t;
	while(t--){
	    int n; cin>>n;
	    vector<int>a(n);
	    for(int i=0; i<n; i++) cin>>a[i];
	    vector<int>b(n);
	    for(int i=0; i<n; i++) cin>>b[i];
	    cout<<solve(a,b,n)<<endl;
	}
	return 0;
}