VACCINE2 - Editorial

PROBLEM LINK:

Practice
Div2

Setter: Daanish Mahajan
Tester: Alexander Morozov
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Ceiling function

PROBLEM:

We have an array of ages for N people. Anyone whose age is \ge 80 or \le 9 is considered to be at risk. Per day, you can only vaccinate up to D people and on each day you cannot vaccinate both categories of people (those who are at risk and those who are not at risk). The task is to find the minimum number of days to vaccinate all N people.

QUICK EXPLANATION:

First find the minimum numbers of days to vaccinate all the people who are at risk, then find the same for all the people who are not at risk and add the results to get the required answer.

EXPLANATION:

Since on a particular day we can’t vaccinate both risky people and non-risky people, let us treat both the cases separately and finally add both the results to get the final answer.

  • First count the number of people who are at risk. Let the count be R . Since on each day we can give vaccine to atmost D people, the minimum number of days required to vaccinate all the risky people wll be \Bigl\lceil \dfrac{R}{D} \Bigr\rceil .

  • The number of people who are not at risk will be N-R . Similar to the above case, the minimum number of days required to vaccinate all the non-risky people will be \Bigl\lceil \dfrac{N-R}{D} \Bigr\rceil .

  • Therefore, the minimum number of days required to vaccinate all N people will be
    \Bigl\lceil \dfrac{R}{D} \Bigr\rceil + \Bigl\lceil \dfrac{N-R}{D} \Bigr\rceil .

TIME COMPLEXITY:

O(n) for each testcase.

SOLUTION:

Editorialist's solution (C++)
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, d;
		cin >> n >> d;
		vector<int> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];

		int risk = 0, not_risk = 0;

		for (int i = 0; i < n; i++)
		{
			if (a[i] >= 80 || a[i] <= 9)
				risk++;
			else
				not_risk++;
		}

		int ans = (risk / d) + (risk % d > 0) + (not_risk / d) + (not_risk % d > 0);
		cout << ans << endl;
	}
	return 0;
}
Setter's solution (Java)
import java.util.*;
import java.io.*;
public
class Main
{
	static PrintWriter out;
	static InputReader in;
public
	static void main(String args[]) throws IOException
	{
		out = new PrintWriter(System.out);
		// out = new PrintWriter(new FileWriter("/home/daanish/CP/codechef/LearningTeam/Testing/2020/Long/Dec/2/out.txt"));
		in = new InputReader();
		new Main();
		out.flush();
		out.close();
	}
	Main()
	{
		solve();
	}
	final int maxd = (int)1e5;
	final int maxn = (int)1e4;
	void solve()
	{
		int t = in.nextInt();
		while (t-- > 0)
		{
			int n = in.nextInt(), d = in.nextInt();
			int c1 = 0, c2 = 0;
			for (int i = 0; i < n; i++)
			{
				int x = in.nextInt();
				if ((x >= 0 && x <= 9) || (x >= 80 && x <= 100))
					c2++;
				else if (x > 9 && x < 80)
					c1++;
			}
			if (c1 + c2 != n || n > maxn || n < 0 || d > maxd || d < 0 || t > 9 || t < 0)
				System.out.println("wrong test no: " + t);

			out.println(((c2 + d - 1) / d + (c1 + d - 1) / d));
		}
	}
public
	static class InputReader
	{
		BufferedReader br;
		StringTokenizer st;
		InputReader() throws IOException
		{
			br = new BufferedReader(new InputStreamReader(System.in));
			// br = new BufferedReader(new FileReader("/home/daanish/CP/codechef/LearningTeam/Testing/2020/Long/Dec/2/in.txt"));
		}
	public
		int nextInt()
		{
			return Integer.parseInt(next());
		}
	public
		long nextLong()
		{
			return Long.parseLong(next());
		}
	public
		double nextDouble()
		{
			return Double.parseDouble(next());
		}
	public
		String next()
		{
			while (st == null || !st.hasMoreTokens())
			{
				try
				{
					st = new StringTokenizer(br.readLine());
				}
				catch (IOException e)
				{
				}
			}
			return st.nextToken();
		}
	}
}

VIDEO EDITORIAL:

Please comment below if you have any questions, alternate solutions, or suggestions.

4 Likes

#include
using namespace std;

int main() {
// your code goes here
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b,d=0;
cin>>a>>b;
int ar[a];
for(int j=0;j<a;j++)
{
cin>>ar[j];
}
int age1=0,age2=0;
for(int j=0;j<a;j++)
{
if(ar[j]<=9 || ar[j]>=80)
{
age1++;
}
else
age2++;
}
int s1=(age1%b>0)+(age1/b);
int s2=(age2%b>0)+(age2/b);
d=s1+s2;
cout<<d<<endl;
}
return 0;
}

It’s Showing Runtime SIGSEGV Error.

Your code is not formatted well and I’m not able to read it and I don’t know if I’m able to read it because I don’t know the problem but this error looks like a c++ error, check your index and your method to access at to element in an array

you have not taken T (no. of test cases) in input

And why am i getting WA in this type of Qs? I can’t seem to figure out?
edit: it did run when i put >0 for remainders? but why?

#include

#include

#include

#include

using namespace std;

#define ll long long int

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);      //this is fast I/O (inputput output) use header file <cstdio>

ll t;cin>>t;

while(t--){

    ll n, d; cin>>n>>d;

    ll a[n];

    for(int i=0; i<n; i++)

        cin>>a[i];

   

    ll c1 =0, c2=0;

    for(int i=0; i<n; i++){

        if(a[i]<=9 || a[i]>=80)

            c1++;                       //at risk

        else

            c2++;                       //at not risk

    }

    if(d==1)

        cout<<n<<endl;

    else{

        ll ans1 = c1/d + c1%d;

        ll ans2 = c2/d + c2%d;

        cout<<ans1+ans2<<endl;

    }

   

}

return 0;

}