I get you. Even I was thinking the same, I know many have done just hit and trail. I tried to get a proof and I submitted it assuming maximum population will always have enough people to be cured so that we can every time double supply for some country having less population.
@sudipandatta can you provide me some valid argument to prove ? 
it’d be helpful
Help!
Please correct if I am wrong.
As per question only way of doubling the x is to deliver the cure to a country that has infected_population > =x and that countries infected_population decrease by x and become double (or initial population). But when we will cure the last country it is possible our x can drop down at last day.
Example test case:
n=3 x=30
14 55 111
day 1> x=30 ar=[14, 55, 111] deliver x to 110 and it will become 110 next day again
day 2> x=60 ar=[14, X, 111] deliver x to 55
day 3> x=110 ar=[14, X, 1] deliver x to 111
day 4> x=220 ar=[14 ,X,2] deliver x to 2
day 5> x=4 ar=[14, X, X] deliver to 14
day 6> x=8 ar=[6, X, X]
day 7> x=16 ar[X,X,X]
But the correct ans is 5 days
can anyone help me under the algorithm because I think I am missing something.
I think as if the author has just taken x=ar[n-1]*2 at last without taking the reducing population of ar[n-1] in consideration.
Try this TC:
1
3 7
3 14 28
ans is 4 days
your solution will give 5 days
reason: you are checking for (x/2) which gives 3 and you are starting from 1st country instead of 2nd country you should do (x+1)/2 in case of odd x and x/2 in case of even x.
thanks a lot man!!
Can someone tell me what’s going wrong in this code (I got TLE in most test cases, but its running correct for many of my own test cases):
test=int(input())
for k in range(0,test):
info=input().split()
N=int(info[0])
x=int(info[1])
pop=[int(y) for y in input().split()]
pop.sort()
day=0
country=0
active=[]
for num in range(0,len(pop)):
active.append(pop[num])
while country!=N:
j=0
while j in range(0,len(pop)) and active!=[0]*N:
maximum=max(active)
if x>=maximum:
day+=1
country+=1
x=maximum*2
j=0
active[active.index(maximum)]=0
for i in range(0,N):
if active[i]*2>=pop[i]:
active[i]=pop[i]
else:
active[i]=active[i]*2
continue
if x>=active[len(pop)-j-1]:
if x<=2*active[len(pop)-j-1]:
day+=1
country+=1
x=2*active[len(pop)-j-1]
active[len(pop)-j-1]=0
j=0
for i in range(0,N):
if active[i]*2>=pop[i]:
active[i]=pop[i]
else:
active[i]=active[i]*2
elif 2*active[len(pop)-j-1]>=maximum:
day+=1
country+=1
x=2*active[len(pop)-j-1]
active[len(pop)-j-1]=0
j=0
for i in range(0,N):
if active[i]*2>=pop[i]:
active[i]=pop[i]
else:
active[i]=active[i]*2
elif j==N-1:
day+=1
x=2*x
j=0
for i in range(0,N):
if active[i]*2>=pop[i]:
active[i]=pop[i]
else:
active[i]=active[i]*2
else:
j+=1
elif j==N-1:
x=x*2
day+=1
else:
j+=1
print(day)Ans is 3
Day1- you give 4 cures to pop=14 country
day2- you give 7 cures to pop=7 country
Day3- you give 14 cures to pop=14 country
no the population of country 2 will remain 14 after the first case, as its the maximum people possible. remember no. of cases cannot exceed the population of country. So, correct ans remains 3
Oh, this was the mistake. Now that this is sorted, I think I will have to take down the post. Thanks for the clarification though.
Can anyone give me the test case where this solution fails : CodeChef: Practical coding for everyone
Thnx in advance.
“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” -----> But value of x can decrease in the maximum population country at the end .Then it is not possible to cure rest of country in single day.Please give clarity on this .
Video Editorial for another approach.
whts this?
we need to make x to max(Ai) and after that each Ai taken in decreasing order can be done in 1 step.
but when we are going to make x to max(Ai) then in the process if it is possible we can cure some Ai’s.
Now a question arises : how to check which Ai’s can be cured in the process.
so if thr current value of X = x then we are going to check whether there is any Ai which is greater than X/2 ,if there is any such Ai then we are going to cure it why?
because in 1 step Ai will be cured and we will have X = 2*(Ai) which is >= x.
so this Ai was anyhow going to be cured in 1 step after we would have reached max(Ai) and start to cure Ai’s in decreasing order.
but as you can see, we have used that 1 step beforehand to make X = 2*Ai which can be greater than current x and can lead us to max(Ai) in less number of steps.
PS :
ll = x/2 + x%2
can be seen as :
if(x%2==1) ll = x/2 + 1
else ll = x/2
That is just ceil(x/2)
Hello
Actually One thing which is confusing me is that
considering test case 2
5 1
10 20 30 40 50
if when I supply 1 to 50 on next day will the number of people infected next day 50?
Yes number of infected people will be 50 again
What will be the answer for following test case:
2 20
9 20
It seems, that answer is 3, but Setter’s Solution is giving 2 as answer.
Can someone give a formal(mathematical) proof that this algo will give the minimum ans. I still have doubt as to why it is better to give cure to a country with p<x but 2*p>x. What if giving like this might increase days later on.