COVSPRD - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N people in ChefLand. A disease has spread such that at the end of day 0, a single person is infected. Until everyone is infected,

  • The number of infected people doubles during the next 10 days.
  • The number of infected people triples from day 11 onwards.

Find the number of infected people at the end of day D.

EXPLANATION:

Subtask 1: D \leq 20

Initially, the number of infected people equals 1. We run a loop for days 1 to D. For each day, if the day number is less than or equal to 10, we double the number of infected people, else, we triple the number of infected people.

Finally, since the number of infected people cannot exceed N (the total population), we print the minimum value out of the current number of infected people and N.

Subtask 2: D \leq 10^8

Since the number of testcases can go upto 300 and for each test case, we run a loop with complexity O(D), the solution described for Subtask 1 would not pass for the given time limit.

A simple observation is to note that the maximum value of N is 10^8. Since the number of infected people is increasing exponentially, it will be equal to 10^8 in ~ 21 days only.

Thus, we can keep a check on the number of infected people at the end of each day. Once it exceeds the total population N, we know that the answer cannot change and we can break the loop to print the answer.

Additionally the maximum value calculated will be at most 3 \times N \leq 3 \cdot 10^8, which is well within the maximum limit of a 32 bit integer (2^{31} - 1 \approx 2 \cdot 10^9) and thus no overflow occurs.

Many participants, correctly identified that the answer is \mathsf{min}(N, 2^{\mathsf{min}(X, 10)} \cdot 3^{\mathsf{max}(0, X - 10)}), but still received only 30 pts, since they used math functions (such as the pow() function from mathlib.h library in C++) which was incorrect since the pow() function can only return values upto 10^{308} ( the long double data type). Moreover, 3^{10^8} = 10^{\log_{10}{3} \cdot 10^8} \approx 10^{4.7 \cdot 10^7} is so large that it is very difficult to obtain its digits (there are around 4.7 \cdot 10^7 digits) within the time limit (in any language including Python).

TIME COMPLEXITY:

The time complexity is O(\mathsf{min}(D, \log{N})) per test case.

SOLUTION:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0) {
                fi = g - '0';
            }
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);

            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if (g == endd) {
            assert(cnt > 0);
            if (is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        }
        else {
            assert(false);
        }
    }
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = readInt(1, 300, '\n');
while(t--){
    ll n, x;
    n = readInt(1, 100000000, ' ');
    x = readInt(0, 100000000, '\n');
    ll tot = 1;
    ll temp;
    for(int i = 0; i < x; i++){
    temp = tot;
    if(i < 10){
        temp *= 2;
    }else{
        temp *= 3;
    }
    if(temp > n){
        tot = n;
        break;
    }
    tot = temp;
    }
    cout<<tot<<"\n";
}
return 0;
}
Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n, x;

void solve()
{
    cin>>n>>x;

    int infected = 1;
    
    for(int i = 1; i<=x; i++){
        if(i<=10){
            infected *= 2;
        }
        else{
            infected *= 3;
        }
        if(infected>=n){
            break;
        }
    }
    cout<<min(n, infected);
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}
3 Likes
2

hey! i just wanted to know why my code is giving WA. What am I doing wrong? Thanks in advance.

#include
#define ull unsigned long long
using namespace std;
int calculate(ull, ull);

int main() {
// your code goes here
int t;
cin >> t;
while (t–)
{
ull population, days;

    cin >> population >> days;
    calculate(population, days);
}
return 0;

}
int calculate(ull a, ull b)
{
ull infected =1;
if (b==0)
{
cout << infected << endl;
return 0;
}
for (int i=1;i <=b;i++)
{
if (infected > a)
{
infected = a;
break;
}
if (i<=10) infected *= 2;
else if (i>10) infected *= 3;
}
cout << infected << endl;
return 0;
}

3

There have been a disproportionate number of problems about coronavirus - see here (CF is no better in this regard). Most of these problems have nothing to do with coronavirus; their setters probably started with the idea of including the term in their story and created a minimal problem statement. The topic was mysterious and fun to discuss during the first lockdown. Now it is only grim and painful to think about the void it has created in every family.

4

Thanks for reporting, we’ll reduce this in the future.