VACCINE1 - Editorial

PROBLEM LINK:

Practice
Div2

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

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic math, Ceiling function

PROBLEM:

We have two companies A and B. Company A produces V1 vaccines starting from day D1 and company B produces V2 vaccines starting from day D2. We are asked to find the minimum number of days required to produce P vaccines.

QUICK EXPLANATION:

Without loss of generality assume D1<D2. Let the required answer be d. Check two cases:

  • D1 \le d<D2

  • d \ge D2

Form mathematical expressions accordingly and find the minimum value of d.

EXPLANATION:

First of all if D1>D2, then swap D1 with D2 and V1 with V2. This clearly won’t affect our final answer. Now check the following cases:

Case 1:

  • D1 \le d < D2
    If this is the case, then the total vaccines produced by the end of d^{th} day will be
    (d-d1+1) \cdot V1 . This must be greater than P. Then, we have (d-d1+1) \cdot V1 \ge P. On solving this, we get d \ge \Bigl\lceil \dfrac{P}{V1} \Bigr\rceil + D1 - 1 . Thus, minimum d will be \Bigl\lceil \dfrac{P}{V1} \Bigr\rceil + D1 - 1 . If this value of d \ge D2, we move on to the next case.

Case 2:

  • d \ge D2
    If this is the case, then the total vaccines produced by the end of d^{th} day will be
    (d-D1+1) \cdot V1 + (d-D2+1) \cdot V2 . This must be greater than P. Then, we have (d-D1+1) \cdot V1 + (d-D2+1) \cdot V2 \ge P. On solving this, we get
    d \ge \Bigl\lceil \dfrac{P+(D1-1) \cdot V1+(D2-1) \cdot V2}{V1+V2} \Bigr\rceil . Thus, the minimum value of d will be the right side of the inequality .

TIME COMPLEXITY:

O(1) since we are just solving a bunch of inequalities.

SOLUTION:

Editorialist's solution (C++)

#include <bits/stdc++.h>
using namespace std;

int main()
{

int D1, V1, D2, V2, P;
cin >> D1 >> V1 >> D2 >> V2 >> P;

if (D1 > D2)
{
	swap(D1, D2);
	swap(V1, V2);
}

int d = (P / V1) + (P % V1 > 0) + D1 - 1;

if (d < D2)
	cout << d << endl;
else
{
	int num = P + (D1 - 1) * V1 + (D2 - 1) * V2;
	int den = V1 + V2;
	d = (num / den) + (num % den > 0);
	cout << d << 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/1/out5.txt"));
		in = new InputReader();
		new Main();
		out.flush();
		out.close();
	}
	Main()
	{
		solve();
	}
	void solve()
	{
		int d1 = in.nextInt(), v1 = in.nextInt(), d2 = in.nextInt(), v2 = in.nextInt(), p = in.nextInt();
		if (d2 < d1)
		{
			d2 ^= d1;
			d1 ^= d2;
			d2 ^= d1;
			v2 ^= v1;
			v1 ^= v2;
			v2 ^= v1;
		}
		int maxp = (d2 - d1) * v1;
		if (maxp >= p)
		{
			out.println(d1 - 1 + (p + v1 - 1) / v1);
		}
		else
		{
			p -= maxp;
			v1 += v2;
			out.println(d2 - 1 + (p + v1 - 1) / v1);
		}
	}
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/1/in5.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 (English):

VIDEO EDITORIAL (Hindi):

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

This code is showing WA for one part, I have tried many test cases but I can’t find the test case where my code fails. https://www.codechef.com/viewsolution/40456770

1 Like

I think the test case 1 1 1 2 2 returns 0, but should be 1.

1 Like

I have the same problem when I apply the formula. It’s always task 3 in sub-task 2. I kinda don’t like that you can’t look at the test data, or just get information of what I might be failing on.

Here’s my code: https://www.codechef.com/viewsolution/40454827

1 Like

Thanks. Can you please tell me some more test cases where this code fails.

I am getting stuck at SubTask 2, Task #3. Here is my solution https://www.codechef.com/viewsolution/40456449

Any test case where d1 == d2 and v1 < p <= v2 returns 0.

1 Like

3 2 1 1 1 returns 2, but should be 1.

2 Likes

Ah yes, forgot about d1 > d2. Thank you!

1 1 3 1 1 returns 2, not 1.

Why ceil value

1 Like

Here in this question, we have used ‘‘ceil’’ instead of ‘‘floor’’ because d>=n if and only if d≥⌈n⌉ where n is the value which we are getting in both case 1 and case 2? Actually, I am trying to understand the reason behind using “ceil”, so can anyone tell is my interpretation is correct or something more should I know?

can somebody please tell me the difference between these two codes. d1,v1,d2,v2,p=map(int,input().split())
c=0
cur=0
while cur<p:
c+=1
if c>d1 or c==d1:
cur+=v1
if c>d2 or c==d2:
cur+=v2
print©
and this code…
d1,v1,d2,v2,p=map(int,input().split())
c=0
cur=0
while cur<p:
c+=1
if c>=d1:
cur+=v1
if c>=d2:
cur+=v2
print©

I felt like both are same but after submitting that I felt there are actually not. but y i cant understand.

#include
int main()
{
short d1,v1,d2,v2,p;
int total{};
int days{1};
std::cin>>d1>>v1>>d2>>v2>>p;
do
{
if((d1==d2)&&(days>=d1))
{
total+=(v1+v2);
}

    ++days;
}
while(total!=p);
std::cout<<days;
return 0;

}
Hi!
This is my block for the d1==d2 portion, can someone explain why its going wrong?
Its showing a value of 893214637.

i was missing this case and now i got all correct

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

all the code working perfect on c++ compiler on my local machine but showing error, I could n’t able to understand the problem with my code, please help me.