DRCHEF - Editorial

Problem Link

Practice
Div 1
Div 2

Author and Editorialist: Sudipan Datta
Tester: Encho Mishinev

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Greedy, Observation.

PROBLEM :

There are N countries with populations a_1,a_2,...,a_n, all of them are initially infected with coronavirus.

There are x vaccines on day 1. The cures available on day i+1 is twice the number of cures delivered on day i. The number of cures delivered to some country on some day cannot exceed the number of infected people it currently has. Also the infection spreads again to the cured people. The number of infections doubles in a country everyday (after all cures on that day, and without exceeding the initial population of that country).

Find the minimum number of days required to cure the world from coronavirus.

QUICK EXPLANATION:

Sort the array of countries and greedily deliver the cures but always trying to maximize the next value of x without wasting days.

EXPLANATION:

Subtask 1: a_1 = a_2 =...=a_N

There are two possible cases:

  • x \ge a_N: we can start delivering to any country. The available cures double every day, so there will be more cures available than the population of any country. We need N days to cure the world. One day for each country.
  • x < a_N: keep delivering the cures to the country with maximum population until the value of x becomes greater or equal than all populations. Then each of the remaining countries can be cured with one more day.

Subtask 2:

First let’s sort the array of populations. Our goal is to increase the value of x to a value greater or equal than the maximum population of all countries. After that we can deliver the cures to the remaining countries in decreasing order and each country will take one day. While increasing x we can cure some of the countries to save some days.

If x<a_i for all i then we deliver to the biggest country and double x.
Let’s say that we have some a_i \le x, we can deliver the cures to a_i if 2 \cdot a_i \gt x in that way the day is not wasted because one country is fully cured and at the same time x is also increased. So the strategy we must follow is always deliver a cure to a country if delivering increases the value of x.

What if we delivered cures to a country that doesn’t increase the value of x? If 2*a_i<x, then is not necessary to send cures to country i, because we can send to a country with higher population and after x becomes greater than all populations, a_i can be again cured in just one day by delivering in decreasing order of populations.

Let’s say x=14, If we deliver cures to a country with population 16, then x=28 next day but the infected population of that country will double again from 2 to 4. After that a common mistake is to deliver cure to that country again. That is x will become 8 from 28. We can avoid this kind of situation by delivering to the biggest country always while doubling x and when its infected population decreases choose the next biggest.

Overall complexity :

O(N \cdot log N).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int tt;
cin>>tt;
while(tt--){
    int n;
    cin>>n;
    ll x;
    cin>>x;
    vector <ll> v(n);
    for(int i=0;i<n;++i)cin>>v[i];
    
    //First step Sort the array.
    
    sort(v.begin(),v.end());
    
    int ans=0;
    int i=-1;
    int cnt=0;
    // cnt is the counter of number of countries already cured.
    while(i+1<n){
        //finding the right position for x i.e a[i] <= x < a[i+1].
        if(x>=v[i+1]){
            i++;
            continue;
        }
        // If v[i]*2>x we deliver to country i.
        if(i>=0&&(v[i]*2)>x){
            x=v[i]*2;
            cnt++;
            ans++;
            continue;
        }
        // If next element is the last one we keep on delivering it.
        if((i+1)==(n-1)){
            while(x<v[n-1]){
                x=x*2;
                ans++;
            }
            cnt++;
            ans++;
            break;
        }
        //To double x we deliver last element
        if((i+1)!=(n-1)&&x<=v[n-1]/2){
            x*=2;
            ans++;
            continue;
        }
        //We just take (remaining countries+1) days more in this condition.  
        if((i+1)!=(n-1)&&x>v[n-1]/2){
            ans++;
            break;
        }
    }
    ans+=(n-cnt);
    cout<<ans<<endl;
}
return 0;
}    
Tester's Solution
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long llong;
 
int t;
int n;
llong a[100111];
llong b[100111];
llong x;

int F[100111];
int reach[100111][31];
 
int main()
{
//freopen("0.in.txt", "r", stdin);
//freopen("test.txt", "r", stdin);
int test;
int i,j;

scanf("%d", &t);

for (test=1;test<=t;test++)
{
    scanf("%d %lld", &n, &x);

    for (i=1;i<=n;i++)
    {
        scanf("%lld", &a[i]);
    }

    sort(a+1,a+1+n);

    llong coef = 1LL;
    for (i=1;i<=30;i++)
    {
        coef *= 2LL;

        reach[0][i] = 1;
        for (j=1;j<=n;j++)
        {
            reach[j][i] = reach[j-1][i];

            while(reach[j][i] < n && a[j] * coef >= a[ reach[j][i]+1 ])
                reach[j][i]++;
        }
    }

    for (i=1;i<=n;i++)
    {
        llong cx = x;

        F[i] = 0;
        while(cx < a[i])
        {
            cx *= 2LL;
            F[i]++;
        }
    }

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=30;j++)
        {
            int r = reach[i][j];

            if (F[r] == -1 || F[r] > F[i] + j - 1)
                F[r] = F[i] + j - 1;
        }
    }

    printf("%d\n", F[n] + n);
}

return 0;
}
14 Likes

Can someone help me why solution on this lines won’t work for this. Instead of looping values I tried using log2() to get to my solution.

Here’s my solution: https://www.codechef.com/viewsolution/35472094

Can anyone help me with this.

1 Like

I tried solving it using binary Search.

I mean First I sort the given array in increasing order then find the index of country such that p[i]>=x and then cure every country one by one in forward manner, this way the cures delivered previous days will keep on increasing as p[i]>=x and at the end I’ll just add the initial no of countries where p[i]<x in my answer.

But got 4-5 test cases WA. Can anyone help?

Can somebody tell me which test case is my solution failing? I have gotten 20points on it: https://www.codechef.com/viewsolution/35550549

3 Likes

i did same and got WA during the contest.
Just needed to change p[i]>=x to 2*p[i]>=x to get accepted.
so sad… :cry:

1 Like

oh x could decrease , i didn’t even imagine that , i am so stupid :woozy_face: :woozy_face:

How did my joke solution work in first attempt? I don’t even know.
https://www.codechef.com/viewsolution/35521877

#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " " << x << '\n' 

int main() {
	int t;
	cin >> t;
	while(t--){
	    int n,x,MAX_p = 0;
	    cin >> n >> x;
	    multiset<int> population;
	    for(int i=0;i<n;i++){
	        int p;
	        cin >> p;
	        population.insert(p);
	        MAX_p = max(MAX_p,p);
	    }
	    int c = 0;
	    while(x < MAX_p){
	        int ll = x/2+x%2;
	        auto it = population.lower_bound(ll);
	        auto it_val = *it;
	        if(it!=population.end()){
	            if(it_val>x){
	                x*=2;
	            }
	            else{
	                x = 2*(it_val);
	                population.erase(it);
	            }
	            c++;
	        }
	    }
	    cout << population.size() + c << '\n';
	}
}
2 Likes

Editorial of Codechef july long challenge 2020 Video Editorial|video solution
Beginer friendly Editorial

1)Chef and Strings : CHEFSTR1

2)Chef and Card Game : CRDGAME

3)Ada King : ADAKING

4)Missing a Point : PTMSSNG

5)Chefina and Swaps : CHFNSWPS

6)Doctor Chef : DRCHEF

7)Chef and Dragon Dens : DRGNDEN

6 Likes

Never use log2(n) , it causes precision issues and fetches wrong result sometimes.
Instead use a while loop and keep dividing n by 2 :slight_smile:.

7 Likes

can someone plaese help me with my code?
https://www.codechef.com/viewsolution/35487629

First you find the first element which is greater than or equal to x and if that element is strictly greater than x then you will waste first day, for this check first element where population*2>=x, and start iteration from that index, this will save you the wasted first day.
my solution

1 Like

Can anyone help me in identifying in which cases my code fails, some test cases of subtask 2 are not getting accepted?
link to my solution:
https://www.codechef.com/viewsolution/35361919

great explanation…good job bhai

one of the TC, where your solution will fail, is
1
3 10
8 23 30
your solution gives: 5 days
while the correct answer is 4 days
it wastes the first day by not delivering to the first country

2 Likes

nice problem
thanks @sudipandatta

we can only deliver the cures to a[i] only when 2.a[i]>x in order to preserve optimal solution.

but why cant we deliver to a[i] when 2.a[i]=x because , that one day is being used which would have been used even if we have skipped a[i] ,but x does not decrease as well as a country is cured .
it would be sufficient to provide a test case that contradict my assumption.
@sudipandatta @enchom

Your assumption is correct. If x=2*a[i], it doesn’t matter if you deliver it at the end or during doubling. I chose to deliver them in the end.

glad u replied . @sudipandatta
i asked just because
editorial says.

we can deliver the cures to a[i] if 2.a[i]>x…
but i missed that it says can not only can…my bad
so i thought perhaps i am not able interpret the outcome properly

Oh thanks @rishav_iitkgp !!
I thought that will reduce the complexity, I had tried using while and that worked in the end. Just couldn’t figure out the reason.

1
6 5
1 2 3 4 8 10
Correct output is 6
Your code gives 7…may be this helps

1 Like