DRCHEF - Editorial

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:

You can also save log2(n) values in double and then change it to integer. i think that would solve the problem without using any while loop. precision errors arise due to float. :slightly_smiling_face:

I used prefix array :face_with_hand_over_mouth:

test(t)
    {
        //-----------------------------------------
        ll n,X; 
        cin >> n >> X;
        ll A[n],B1[n],B2[n],Prefix_arr[n];
        ll Max_p = 0,Min_days;
        //-----------------------------------------
        for( ll i = 0 ; i < n ; i++ )
        {
            cin >> A[i];
            Max_p = max(A[i],Max_p);
        }
        //-----------------------------------------
        if(X >= Max_p)
        {
            cout << n << "\n";
        }
        //-----------------------------------------
        else
        {
        sort(A,A+n);
            //-----------------------------------------
            for( ll i = 0 ; i < n ; i++ )
            {
                if(A[i] <= X) B2[i] = 0;
                else B2[i] = ceil(log2(((double)A[i])/X)); 
                
                if( i == 0 ) B1[i] = 0;
                else {B1[i] = ceil(log2(((double)A[i])/A[i-1])); if( B1[i] == 0 ) B1[i] += 1;}
                
                if( i == 0 ) Prefix_arr[i] = B1[i];
                else Prefix_arr[i] = Prefix_arr[i-1] + B1[i];
            }
        
            //-----------------------------------------
            for( ll i = 0 ; i < n ; i++ )
            {
                if( i == 0 )
                {
                    Min_days = B2[i] + (Prefix_arr[n-1] - Prefix_arr[i]) + i;
                }
                else
                {
                    Min_days = min(Min_days,B2[i] + (Prefix_arr[n-1] - Prefix_arr[i]) + i);
                }
            }
            //-----------------------------------------
            cout << Min_days+1 << "\n";
        }
    }

We only choose to send vaccines to a country iff twice the number of infected individuals in that particularly is at least equal to the number of vaccines currently available. This ensures that the number of vaccines available does not decrease at any point.

For example, consider the situation : 2 3 7 11 125, with x = 5, (x is the number of vaccines available at any given point in time). If we decide to send vaccines to the 1st country with 2 infected individuals, we end up with having 4 vaccines at the end of the day, which is less than x. Hence we lost one vaccine.

Selecting the 2nd country instead would’ve given us 6 vaccines at the end of the day, which is >=x. So this is a deal that’s worth taking.

If we do not have any country that satisfies the given condition, then it is best to perform the operations on the country with largest number of infected people as that will help increase the number of vaccines by a factor of 2 everyday.

1 Like

Thanks for clearing this.