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)
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
“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 .
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
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?
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.
Instead of mathematical proof, I can give you a logical observation
(because I am not a mathematics genius)
Let’s take this test case:-
2 10
9 20
We will check only for day one as you will see the difference on day one also
We have to cure counties with most cases first to increase the vaccine count.
When we don’t take the condition into account :
On Day 1
we will use 10 vaccines to cure 10 people in country2 (20 infected)
new vaccine count -> 10*2 = 20
But look what happened on day 2, everyone in country2 again got infected, therefore on Day-2 we have :
No. of infected countries -> 2
Vaccine count -> 20
When we take the condition into account :
On Day 1
we will use 10 vaccines to cure everyone in country1 (10 infected)
new vaccine count -> 10*2 = 20
On Day 2 we have :
No. of infected countries -> 1
Vaccine count -> 20
After seeing the result of both the process after Day 1, we know which will take a longer time.
And the same will happen for all the test cases.
Actual on day 2 number of vaccines will be 18 because you cured 9 people in day 1 with 10 vaccines 9*2 = 18 will be the next count of the vaccines. Because only number of used vaccines can be doubled.
So the answer will be 3
On day 1 you covered 9.
On day 2 you have 18 but country 2 has 20 infected people even you cure 4 of them will be left. So, it’s ok you don’t use the cure and just double it.
On day 3 your x is 36 which is greater than country 2 infected people so, you just cure them.
That is the point. I understand that we need to consider thus corner case to save 1 day. My doubt is that why does it always work? Meaning suppose not considering this condition we would get 2x vaccines next day but giving it to the nearest smaller givable country we get 2p.
So later on the increase in vaccines is less than what it would have been in previous case.
So how can we be sure that the lesser increment won’t affect the number of days.
