# BALL\_GAME - Editorial

**URL:** <https://discuss.codechef.com/t/ball-game-editorial/119907>\
**Category:** editorial\
**Tags:** editorial, sorting, start151\
**Created:** [September 11, 2024, 4:30pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907 "2024-09-11T16:30:39Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [September 11, 2024, 4:30pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/1 "2024-09-11T16:30:39Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/BALL_GAME)  
[Contest: Division 1](https://www.codechef.com/START151A/problems/BALL_GAME)  
[Contest: Division 2](https://www.codechef.com/START151B/problems/BALL_GAME)  
[Contest: Division 3](https://www.codechef.com/START151C/problems/BALL_GAME)  
[Contest: Division 4](https://www.codechef.com/START151D/problems/BALL_GAME)

_ **Author:** _ [krrishmath](https://www.codechef.com/users/krrishmath)  
_ **Tester:** _ [mexomerf](https://www.codechef.com/users/mexomerf)  
_ **Editorialist:** _ [iceknight1093](https://www.codechef.com/users/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:

[details = Author’s code (C++)]

```cpp
#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;
}

```

[/details]  
[details = Tester’s code (C++)]

```cpp
#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";
    }
}

```

[/details]  
[details = Editorialist’s code (Python)]

```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)

```

[/details]

---

<div class="post-metadata">

**Author:** ![sk511](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sk511/32/284859_2.png) [@sk511](https://discuss.codechef.com/u/sk511)\
**Post date:** [September 11, 2024, 4:45pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/2 "2024-09-11T16:45:22Z")

</div>

long double did work for ai/bi

---

<div class="post-metadata">

**Author:** ![krrishmath](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@krrishmath](https://discuss.codechef.com/u/krrishmath)\
**Post date:** [September 11, 2024, 5:04pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/3 "2024-09-11T17:04:28Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dev777g](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dev777g/32/262545_2.png) [@dev777g](https://discuss.codechef.com/u/dev777g)\
**Post date:** [September 11, 2024, 10:13pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/4 "2024-09-11T22:13:47Z")

</div>

Can somebody please tell me why my code didn’t work?  
here’s the link →   
[https://www.codechef.com/viewsolution/1088852329](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++.

---

<div class="post-metadata">

**Author:** ![sarodesparsh](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sarodesparsh/32/209114_2.png) [@sarodesparsh](https://discuss.codechef.com/u/sarodesparsh)\
**Post date:** [September 11, 2024, 11:55pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/5 "2024-09-11T23:55:08Z")

</div>

Using long double does work for this problem: [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/1088854228)

---

<div class="post-metadata">

**Author:** ![krrishmath](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@krrishmath](https://discuss.codechef.com/u/krrishmath)\
**Post date:** [September 12, 2024, 2:09am UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/6 "2024-09-12T02:09:02Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![krrishmath](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@krrishmath](https://discuss.codechef.com/u/krrishmath)\
**Post date:** [September 12, 2024, 2:10am UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/7 "2024-09-12T02:10:23Z")

</div>

By higher numbers i meant numbers greater than the constraints given

---

<div class="post-metadata">

**Author:** ![dev777g](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dev777g/32/262545_2.png) [@dev777g](https://discuss.codechef.com/u/dev777g)\
**Post date:** [September 12, 2024, 12:05pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/8 "2024-09-12T12:05:02Z")

</div>

Yeah I should have traversed backward 🥲 , Thanks a lot

---

<div class="post-metadata">

**Author:** ![neel\_04](https://discuss.codechef.com/user_avatar/discuss.codechef.com/neel_04/32/248686_2.png) [@neel\_04](https://discuss.codechef.com/u/neel_04)\
**Post date:** [September 15, 2024, 4:01pm UTC](https://discuss.codechef.com/t/ball-game-editorial/119907/9 "2024-09-15T16:01:10Z")

</div>

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

```auto
#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;
}

```