ECPC10B - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Gourav Rathor
Tester: Sumeet Pachauri
Editorialist: Gourav Rathor

Difficulty:

EASY

Prerequisites:

Basic looping, Basic maths

Problem:

You have given eating time (in seconds) A_1 to A_N of N customers.
You have to find minimum activity per second so that no customer have to wait for panipuri.
Where activity is ‘making a panipuri and putting it into the plate of customer’.

QUICK EXPLANATION:

we can find the minimum time taken to eat a panipuri. In this minimum time N have to be served to avoid waiting.
so our answer will be ceil(N/minimum_time).

Explanation:

Consider panipuri seller have N customers waiting for panipuri.
when he serve the customers, customer starts eating panipuri.
The seller must put next panipuri in customer’s plate before customer finishes his previous panipuri.
let the first customer take T_1 sec to consume panipuri so after putting panipuri in customer’s plate, seller have T_1 time to finish N activity, N-1 activity for other customers and 1 activity for the first customer so that he can get panipuri just after finishing the previous one.
let S is speed of seller,
so we can say that S \geq N / T_1.
similarly for 2_{nd} customer S \geq N / T_2.
.
.
similarly for i_{th} customer S \geq N/T_i.
.
.
similarly for N_{th} customer S \geq N/T_N.

so S should satisfy all above conditions.
let N/T_k is heighest among all N/T_i where 1 \leq i \leq N.
If S is greater than or equal to N/T_k, then S is also greater than or equal to all N/T_i, where 1 \leq i \leq N.
As we need to find minimum integral speed so, our answer will be S = ceil(N/T_k).
Now N/T_k to be heighest, T_k should be smallest.
So our task is to find minimum time taken to eat a panipuri, which is T_k.
Then print ceil(N/T_k).

Solution:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int>v(n);
        for(int i=0;i<n;i++)
        cin>>v[i];
        int min=v[0];
        for(int i=1;i<n;i++)    //finding minimum time to eat a panipuri
        {
            if(min>v[i])
            min=v[i];
        }
        cout<<(int)ceil((float)n/min)<<"\n";
    }
    return 0;
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

1 Like
2

cool i used binary search (over complication i think)

1 Like
3

I still don’t understand why the answer to the first example is 2. In my simulation the 2nd and 4th consumers finish eating at the same time.

5

Why should this solution get a WA :anguished:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
const int mod = 1e9+7;



main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        ll a[n];
        ll mini = mod;
        for(int i=0;i<n;i++){
            cin>>a[i];
            mini = min(mini,a[i]);
        }
        cout<<ceil((double)n/mini)<<"\n";
    }
}
1 Like
6

Because the tester and the setter were not on the same page
The setter’s solution is also getting a WA!
Using (n/mini+(n%mini != 0) is getting an AC
But I don’t get it
Consider the input
5 6 7 8 9. Here answer is 1
6 6 7 8 9. But here how can the answer be 2. 6>5 so 1 should be the minimum speed that would do.

1 Like
7

There was a mistake in setters solution. i.e.
setter was trying to output ceil((float)n/min);
due to type casting the output will be float type although value is rounded off to integer, that’s why WA is coming. so we have to again type cast the final value to integer.
now editorial is edited,
statement
cout<<ceil((float)n/min)<<"\n";
is replaced by,
cout<<(int)ceil((float)n/min)<<"\n";

and now AC is coming.

1 Like
8

when seller have to serve 5 customers whose speed is 6 6 7 8 9.
1st and 2nd customer taking the smallest time to eat which is 6sec.
so panipuri seller have 6 seconds to serve 5 members, which required 5 activity to perform.
so speed sholud be 5/6 activity per second
which is equal to 0.8333 activity per second.
but speed should be integer and also minimum
so speed should be one.

9

That was interesting, btw the code I posted was my submission during the contest.It’s very similar to setter’s soln :laughing:

10

consider the fist example.
no of customer =4
time to eat a panipuri is 2 4 6 3 repectively.

continuing simulation when speed is 2 activity per second.

at
0.5s cust 1 got panipuri and start consuming.
1 s cust2 got panipuri and start consuming
1.5s cust3 got panipuri and start consuming
2 s cust4 got panipuri and start consuming
2.5s cust1 got 2nd panipuri and finishes first, starts consuming 2nd paipuri.
3 s cust2 got 2nd panipuri, but he would finish first at 5 sec. so panipuri is in his plate.
3.5 s cust3 got 2nd panipuri, but he would finish first at 6.5 sec. so panipuri is in his plate.
4s cust4 got 2nd panipuri, but he would finish first at 5 sec. so panipuri is in his plate.
4.5 s cust1 got 3rd panipuri and finishes second, starts consuming 3rd paipuri.
5 s cust2 got 3rd panipuri,he has finishe the first panipuri. so start consuming 2nd panipuri.
3rd panipuri will be in his plate .
5.5s cust3 got 3rd panipuri, but cust 3 is still consuming 1st panipuri, so 2 pan puri in his plate.
6 s cust4 got 3rd panipuri, he had finishes the first and started consuming 2nd on 5th sec,will
finish second panipuri at 8sec. so 3rd panipuri will be in his plate.
6.5 cust1 got 4th panipuri and finishes 3rd, starts consuming 4th paipuri.

when speed is 2 activity per second no customer is waiting although slow eater has extra panipuri in their plate.
this is why answer is 2.

11

Now I managed to understand, thanks for the explanation.

1 Like