WHY ll= x/2+x%2 ; why not ll=x ??
sorry i was wrong …my bad 
on first day we send our delivery man to second country now we have 8 vaccine, ( 7 infected in country 1st and 14 infected in country 2nd) ,then on second day we send him to 1st country now we have 14 vaccine ( 0 infected in 1st country and 14 in 2nd country) , on third day we send him to cure 2nd country. I hope it’s clear now.
In subtask 2, it think it should be 2 * Ai >= x .
I presume you are asking if we can deliver to that country if 2*a_i=x. Yes, we can. We can deliver to that country while doubling x or at the end. Either way it accounts for only 1 day for that country. My algorithm choses to deliver at the end.
1 Like
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)