VACCINE3 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

Given the population divided into age groups [1, 10], [11, 20], [21, 30], \ldots, [91, \infty). The age groups are numbered from 1 to 10 and there are X_i people in age group i.

The COVID vaccine drive has started, and people would be vaccinated in the decreasing order of their age groups. Every day exactly P people are vaccinated. If there are less than P people left in the current age group, then the remaining doses of that day are given to people of immediate smaller age group on the same day. People within the same age group can be vaccinated in any order.

Chef is in age group G, determine the minimum and the maximum number of days will it take for Chef to be vaccinated.

QUICK EXPLANATION

  • All people in age groups older than G would be vaccinated before Chef and all people in age groups younger than Chef will be vaccinated after Chef.
  • So Chef can only choose any position in the order people in age group G are vaccinated.
  • For the minimum day, the Chef shall be the first in his group to be vaccinated, and for the maximum day, Chef will be the last in his group to be vaccinated.

EXPLANATION

Since the age groups are processed in descending order, Chef has to wait for all the age groups older than the age group G to be vaccinated.

Similarly, all people including Chef shall be vaccinated before any age group younger than the age group G is vaccinated.

Chef has no control over the above two facts, so He has to wait for older groups to be vaccinated first, and he shall be vaccinated before the lower groups. All Chef can control is his position in the order, people of age group G are vaccinated.

Let us assume there are total S people in age groups older than age group G (\displaystyle S = \sum_{i = G+1}^{10} X_i) and C = X_G denote the number of people in age group G.

If we visualize all people from all age groups standing in a queue in the order they would be vaccinated, we can see that there are at least S people before Chef, and Chef is among the first S+C people. Hence, the position chef can be standing in this queue is between [S+1, S+C]

The first P people are vaccinated on day 1, the next P on day 2, and so on. So, for the minimum day, Chef must stand at position S+1, and for maximum day, Chef must stand at position S+C. Hence, the minimum day the Chef is vaccinated is the day the S+1-th person is vaccinated, and the maximum day the Chef is vaccinated, is the day the S+C-th person in the queue is vaccinated.

By basic math, we can see that person at position X is vaccinated on day \displaystyle \bigg\lceil \frac{X}{P} \bigg\rceil.

Hence, minimum day is \displaystyle \bigg\lceil \frac{S+1}{P} \bigg\rceil and maximum day is \displaystyle \bigg\lceil \frac{S+C}{P} \bigg\rceil.

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;
  
const int maxt = 1e4, maxp = 1e5, minpp = 1, maxpp = 1e5;
const string newln = "\n", space = " ";

int main()
{   
    int t; cin >> t;
    int g, p;
    int a[11];
    while(t--){
        cin >> g >> p;
        for(int i = 1; i <= 10; i++){
            cin >> a[i];
        }   
        int days = 0;
        for(int j = 10; j > g; j--){
            days += a[j] / p; a[j - 1] += a[j] % p;
        }
        int minans = days + 1, maxans = days + (a[g] + p - 1) / p;
        cout << minans << " " << maxans << endl;            
    }
} 
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
    #include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;


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);
	    }
    }
}

string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
	    char g = getchar();
	    assert(g != -1);
	    if (g == endd) {
		    break;
	    }
	    cnt++;
	    ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
    return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
    return readString(l, r, ' ');
}

int main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../in.txt", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 10000);
    forn(tc, T)
    {
	    int G = readIntSp(1, 10);
	    int P = readIntSp(1, 100'000);
	    vector<int> X(10);
	    int su1 = 0;
	    int su2 = -1;
	    forn(i, 10)
	    {
		    if(i<9)
			    X[i] = readIntSp(1, 100'000);
		    else
			    X[i] = readIntLn(1, 100'000);
		    if (i >= G)
			    su1 += X[i];
		    if (i + 1 >= G)
			    su2 += X[i];
	    }
	    printf("%d %d\n", su1 / P + 1, su2 / P + 1);
    }
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class VACCINE3{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int G = ni(), P = ni(), N = 10;
        int[] X = new int[1+N];
        for(int i = 1; i<= N; i++)X[i] = ni();
        int older = 0;
        for(int i = G+1; i<= N; i++)older += X[i];
        int minRank = 1+older;
        int maxRank = older+X[G];
        int minDay = (minRank+P-1)/P, maxDay = (maxRank+P-1)/P;
        pn(minDay+" "+maxDay);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new VACCINE3().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

6 Likes

https://www.codechef.com/viewsolution/46773973
dont know where it is wrong, any help be appreciated.

1 Like

Can anyone please tell me what is the wrong in this ? It’s passed all given test cases which is given in question…

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve();
int main()
{
int t;
cin>>t;
while(t–)
{
solve();
}
return 0;
}

void solve()
{
int G,P,x[10];
cin>>G>>P;
for(int i=0;i<10;i++)
cin>>x[i];

    ll min_sum=0,max_sum=0;
    for(int i=9;i>=G;i--) 
    {  
         min_sum+=x[i];
    }
    
    if(min_sum<=P) {
    cout<<"1 1\n";
    return ;
    }
    
    max_sum=min_sum + x[G-1];
    min_sum++;

    ll r1=min_sum%P ;
    ll r2=max_sum%P ;
    
    int d1=0,d2=0; 
    if(r1==0)
      d1=min_sum/P;
    else
      d1=min_sum/P + 1;

    if(r2==0)
      d2=max_sum/P;
    else
      d2=max_sum/P + 1;  

    cout<<d1<<" "<<d2<<"\n";

}

2 Likes

Use long long instead of int for summing up the value..

Dear Coders,

Request your help in cross verifying my Python code. I tried various test data and I was satisfied with the result produced by my code. But the solution is displaying Wrong answer post submission. Looking for some guidance. Cheers!

import math

try:
t=int(input())
for l in range(t):
G,P,a1,a2,a3,a4,a5,a6,a7,a8,a9,a0 = [int(x) for x in input().split()]
list_a = [a1,a2,a3,a4,a5,a6,a7,a8,a9,a0]
sum1 = 0
sum2 = 0
if ((G >= 1 and G <= 10) and (P >= 1 and P <= 100000)):
for i in range(9,G-1,-1):
sum1 = sum1 + list_a[i]
for j in range(9,G-2,-1):
sum2 = sum2 + list_a[j]
print(math.ceil((sum1+1)/P),math.ceil(sum2/P))
except EOFError as e:
print(e)

(Required indentation at necessary places as the code is not displayed the way as expected in the comment)

https://www.codechef.com/viewsolution/46823898

what is wrong with this solution please someone help i did like editorial only but i think one case is missing is spent 2 hr 20 mins debugging but didin’t get where its wrong please look into it

Can you explain the logic that you used as it will be easy to debug…

@taran_1407 Great Editorial man!!

Wow, Cakewalk question ,I must work hard not able to solve it in contest

3 Likes

Could anyone suggest me, which edge cases am I missing ?

#include
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int g,p,day=0,d,max,min,sum=0,cal;
int x[10];
cin>>g>>p;
for(int i=0;i<10;i++)
{
cin>>x[i];
if(i>=g)
sum+=x[i];
}

    min=sum/p+1;
    d=sum%p;
    cal=x[g-1]-d;
    
    if(cal<=p && d==0)
    max=min;
    else
    {
        if(cal%p==0)
        max=min+(cal/p);
        else
        max=min+(cal/p)+1;
    }
    
    cout<<min<<" "<<max<<endl;
}
return 0;

}

https://www.codechef.com/viewsolution/46823708
please help me unable to find error

Can anyone please tell me what is the wrong in this? passed all given test cases but give WA
https://www.codechef.com/viewsolution/46827647

there is a video editorial also available, you can check that out.
[- YouTube](https://vaccine video editorial)

Please someone tell me where i did mistake ?..
for _ in range(int(input())):
l=list(map(int, input().split()))
g=l[0]
p=l[1]
q=sum(l[g+2:]) #number of people before chef’s group
r=q//p #number of days taken for people before to be vaccinated
rem=q%p #number of people left from group before chef’sum
slots=p-rem #number of slots available for chef’s group
if slots>=l[g+1]: #if slots available is more than or equal number of people in chef’s gropu the chef will get vaccinated
print(r+1,r+1) #the day chef get vaccinated is one day more than groups before him
else: #when number of people in chef’s group are more then slots available
w=q+1/p #even the slots are less chef will get vaccinated 1st in his group (min days)
d=int(w)
e=sum(l[g+1:]) #sum of people from chef’s group to last group
t=e/2 #maximum number of days chef will get vaccinated
y=int(t)
max_=0
min_=0
if y<t: #if t is not integer
max_=y+1
else: #if t is integer
max_=y+1
if d<w:
min_=d+1
else:
min_=d
print(min_,max_)

1 Like

void solve() {
int G, P;
cin >> G >> P;
G–;
vector X(10);

int total = 0;
for (int i = 0; i < 10; i++) 
	cin >> X[i];

int next = X[G];
for (int i = 9; i > G; i--) {
	total += X[i];
}

cout << total / P + 1 << ' ' << (total + next + P - 1) / P << '\n';

}

You can do it too…
void solve() {
int G, P;
cin >> G >> P;
G–;
vector X(10);

int total = 0;
for (int i = 0; i < 10; i++) 
	cin >> X[i];

total = accumulate(X.begin() + G + 1, X.end(), 0);
cout << total / P + 1 << ' ' << (total + X[G] + P - 1) / P << '\n';

}

            #include <bits/stdc++.h>
            using namespace std;
            int vaccine(int G, int P, int a[])
            {
                long long sum=0;
                int min,max;
                for(int i=G-1;i<10;i++)
                {
                    sum += a[i];
                }
                int r = sum%P;
                if(r == 0)
                {
                    min = max = sum/P;
                }
                else{
                    min = sum/P;
                    max = (sum/P) + 1;
                }
                cout<<min<<" "<<max<<endl;
                return 0;
            }

            int main()
            {
                ios_base::sync_with_stdio(false);
                cin.tie(NULL);
                int T,G,P,a[10];
                cin>>T;
                while(T--)
                {
                    cin>>G>>P;
                    for(int i=0;i<10;i++)
                    {
                        cin>>a[i];
                    }
                    vaccine(G,P,a);
                }
                return 0;
            }

Can anyone please help me with this,
The following code passes the sample input(testcase) given in the question but its gets wrong while submitting

I have already defined int for long long i.e line no 11

i think you should start summation of groups which are greater than G. we dont need to add G group value to our sum

cout << (int)ceil(1.0*(s + 1) / p) << " " << (int)ceil(1.0*(s + v[g - 1]) / p)<<endl;

This code is working fine . I don’t the reason because I think ceil auto convert float to int.
Correct me If I am wrong or tell me the reason if you know.

1 Like