DRCHEF - Editorial

#include
#include
#include

using namespace std;

int main() {
// your code goes here
int t,n,i;
long x,a,mini,infec;
cin >> t;
while(t>=1)
{
cin >> n >> x;
vector days;
for(i=0;i<n;i++)
{
cin >> a;
days.push_back(a);
}
sort(days.begin(),days.end(),greater());
infec = days[0]; //infec variable contains max population amongst countries
mini =0;
/*
In this algo what I am doing is I am running a while loop to increase the value of x until it becomes greter than the
total no of people infected in country with max population. I am decreasing the value of infec when 2*x>infec

    while increasing the value of x if it becomes greter than the population of other countries than i am increasing value of days and 
    removing that country from list.
    
    my test cases are running fine.
    
    */
    while(!days.empty() && x<infec)
    {
        if(x>=days.back() && (2*days.back())>x)
        {
            mini++;
            x = days.back()*2;
            days.pop_back();
            //cout << mini <<endl;
            continue;
        }
        else
        {
            mini++;
            x = x*2;
            if(infec<2*x)
           {
            infec = infec - x;
            infec = 2*infec;
            
            //x = x*2;
           }
        }
        //cout << x <<endl;
    }
    if(x>=infec && !days.empty())
        {
            
            while(!days.empty())
            {
                days.pop_back();
                mini++;
            }
        }
    cout << mini <<endl;
    t--;
}
return 0;

}

please sir can u check my code

plzz tell me whats wrong in my code

https://www.codechef.com/viewsolution/35721857

Sorry, mistook my own testcase… :sweat_smile:

1 Like

Could you explain what is happening in your last while loop?

in last while loop, i am comparing the last element with x and multiplying x by 2 and decrementing a[n-1] - x and then multiplying a[i]*2 and after that if a[i] becomes greater than that of original value of a[i] then don’t change a[i].

in this process if we find an element in the array a, which became less than x due to doubling of x.
then what we do is, we give vaccines to that one and make the infected people of that country zero. and x= a[pos] * 2
(HERE POS IS THE POSITION OF THAT ELEMENT WHICH IS SMALLER THAN OR EQUAL TO X)
(THIS I HAVE DONE IN THAT FOR LOOP INSIDE WHILE LOOP)
(IF WE FOUND POS THEN DO THE ABOVE THING ELSE CARRY ON WITH THE LAST ELEMENT)

HI Can any body tell me what will the output of the given tc:
1
4 20
9 19 20 41

I think it must be 6 but editorial show it 5.
Can anybody explain me why the given test case answer is 5.

1st we will cure country with pop 20 and get 40 vac. +1
now we will cure the country with pop 41 and get 80 vac. but it will not cure it fully +1
now we will cure ‘19’ and get 38 vac +1
//by this time array looks like 9,0,0,4 due to doubling of pop.
now we will cure 9 ans get 18 vac. +1
//now array is {8}
we will cure last one. +1
total ‘+1’ -->5

Easiest solution to understand so far -

#include <bits/stdc++.h>
using namespace std; 

int main() {
   ios_base::sync_with_stdio(false);cin.tie(NULL); 
   #ifndef ONLINE_JUDGE 
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout); 
   #endif
   int t;
   cin >> t;
   while(t--){
       int n,x,MAX_p = 0;
       cin >> n >> x;
       vector<int> v(n);
       for(auto &i:v)
         cin>>i;

      sort(v.begin(), v.end());
      int count = 0;
      for(int i=0;i<n;i++)
      {
         if(x>=v[i])
         {
            count++;
            x = max(x, 2*v[i]);
            continue;
         }
         while(x<v[i])
         {
            count++;
            x = x*2;
         }
         count++;
         x = a[i]*2;
      }
      cout<<count<<endl;
   }
}

time limit exceeds for 5 cases in subtask 2
please help:-

#include
#include
#include
#include
#include
using namespace std;
long long sums(vector a){
long long sum{};
for(long long c:a)
sum=sum+c;
return sum;
}
int main(){
long long n{};
cin>>n;
vector result{};
for(int i{};i<n;i++){
long long m{},vaccines{},sum{},counts{};
cin>>m>>vaccines;
vector a{};
for(int j{};j<m;j++){
long long h{};
cin>>h;
sum=sum+h;
a.push_back(h);}
sort(a.begin(),a.end());
while(sum!=0){
vector pos{};
if(a[m-1]<=vaccines){
sum=0;
for(long long c:a){
if(c!=0)
counts=counts+1;}}
else{
for(long long j{};j<m;j++){

            if(a[j]<=vaccines and 2*a[j]>=vaccines){
                vaccines = 2*a[j];
                a[j]=0;
                counts=counts+1;
                sum=sums(a);}}}
        
        if(sum!=0){
            for(long long j{m-1};j>=0;j--){
                if(2*a[j]>=vaccines){
                    pos.push_back(j);
                    break;}}
             sort(pos.begin(),pos.end());       
             if(pos.size()==0){
                 sum=0;
                 for(long long c:a){
                     if(c!=0)
             counts=counts+1;}}
             
                         
             else{       
             long long z{pos[pos.size()-1]};
             for(long long j{};j<m;j++){
                 if(j!=z)
                     a[j] = min(a[j],2*a[j]);}
             a[z] = min(a[z],2*(a[z]-vaccines));
             
            vaccines=2*vaccines;
            sum=sums(a);
             counts=counts+1;}}  
    }  
    
result.push_back(counts);

}
for(long long c:result)
cout<<c<<endl;
}

1 Like

@g_himanshu0100 your logic goes O(n^2) in the worst case , while O(n) or O(n logn) is accepted , try reducing your complexity
if you have any doubts ,
click here to view my solution

I used Priority queues!
https://www.codechef.com/viewsolution/35298120

Can anyone help me figure out why my code is not giving correct output ?
My solution link - https://www.codechef.com/viewsolution/35869168

my logic - i have created a multiset storing poppulations of every country in ascending order.

  1. At any day (be it the first day of curing) if the number of cures vailable, X,
    is equal or greater than the largest element in multiseet (country with the largest population) then the answerw will be size of the multiset (as if we start from the last we can cure each country in one day)

  2. IF X is less than last element of multiset then arises two cases :

A) if its the first day of curing - then simply use X to cure the country with highest population (last ekement of set), no need to update X (X remains same for the next day) and then update the coutnries population (after doubling) on which we used X cures. and we increment the tally of total days required by one.

B) else (when its not first day) - then we further chek a condition hence two cases arise -

        a) we will search for a element in multiset within the range [x,2x] inclusively
        if a value found then we will use as many cures as the value of element returned 
        i.e size of population found within range [x,2x] let that population be P, 
        thus X = P (updating X for next day) and we remove that element from multiset 
        (because this country will be country cured on that day) and we increment the 
        total days required by one.

        b) else (hwen no such value in multiset exits in range [x,2x] ) then again we will 
        go to cure the country with largest population present. X will be updated to 2*X 
        (because today we can use 2*X cures to cure the most populated country), thus 
        X = X*2, we also update the population of that country adter doubling at end of 
        the day.

Note : Also before doing all these tasks i also chek whether my multiset is empty or not.

I have also attached explanation with sample testases.

Testcase 1 :
when X = 1, N =5 and country’s populations are 10, 20, 30, 40, 50

Testcase 2 :
when X = 10, N = 3 and country’s populations are 1, 20, 110

PLZ read this and help me out with my logic and piece of code .

If we do not deliver any cure on a single day, will the value of x be changed?
If yes, please describe in a brief.

Deliver Or not the value of x will be doubled until you get a equal or the consecutive smaller country let me take the example from sample
3 10
1 20 110
On first day x is 10 now if we use it at 1 our next x will be 2 so we can’t do that if we use 10 at 20 remaining infected people will be 10 and next x will be 20 and the next value will be 20 again because remaining infected people and cure gets double. So if you look closely I will give u a scenario in case of 20 last time we took two days to eliminate but what if we don’t use the cure on first day now or 10 will increase to 20 and on second day it will cutt off the 20 once at all it took 2 days again. So, it doesn’t matter you use the x Or not the days will remain the same.
Now if you try to solve x for 110 you will also observe that the scenario will be same in that case too and in all other cases. So, if you want to use x every time it won’t be wrong :x: but if you don’t use x and double it every time until you find equal and a previous consecutive value the scenario will also be same.

0 1 2 3
9 19 20 41
1.x=20 then a[2]>=20 a[2] cured , next x= 40
2.then 40<a[3] ; 40 used for a[3] but still not equal to population, next x=80
3.then 80>a[3], 41 used for a[3] next x= 82 ,a[3] cured
4. 82>a[1] ,used for a[1] , x=2*a[1]=38 ,a[1] cured
5.38>a[0], used for a[0], a[0] cured .
all country are cured now.

Have a look at the this case.

5 8
10 20 30 40 50

If we do not deliver the cures and wait for it to become 16, we can cure all 10 of them in a single day and thus x will be 20. It takes less number of days in this case if we assume that the number of cures will be doubled even if we do not deliver any of them.

If I assume x won’t be doubled if I don’t deliver any cure:
we can cure 8 people of the first country and thus x will be 16. In this process, it takes more days.

I can’t understand why we have to double the value of x after delivering 0 cures. (0*2 = 0)
The problem statement says,
Chef can supply twice the number of cures that were delivered (i.e. people that were cured) on the previous day. Chef cannot supply leftovers from the previous or any earlier day.

Definitely I’m wrong as I’m getting WA. But I want to understand.

Hope you understand after this :slight_smile:

!
!

2 Likes

Why the idea of line 22 in the code https://www.codechef.com/viewsolution/35370409 is wrong . I changed it to x = 2*arr[i] and it worked.

Accepted :+1:
Added 5 more lines in my previous code.
https://www.codechef.com/viewsolution/36178964

My algorithm is not looking good, the code has become too long.
however, it worked. Thanks for clarifying the problem.

1 Like

Always Happy to Help :slightly_smiling_face: