DRCHEF - Editorial

editorial
, , , ,
108

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:

109

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";
        }
    }
110

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
111

Thanks for clearing this.

1 Like
112

plz someone help me out as well to fix error in my code !
mine is 92nd comment in this forum

113

Simple yet efficient solution. Thanks a lot for sharing.