Problem Link
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;
}
.