Bro I learn this approach when I have to find sqrt(n) without sqrt function , but this upper bound sucks .
Hello, I have a doubt, if cooldown time x is valid, it means all cool down times from 1 to x are valid.
For this test case,
1
2 1
1 7
Answer is 7
First, we hit the enemy at t=1 , then we hit the enemy at t=8
So, total cool down time = 8-1=7
It means, all cool down times less than equal to 7 should be valid!
But for cool-down time, x=4 , I cannot find any strategy to kill both the enemies.
Can you tell how to kill both guys for x=4?
@ssrivastava990
@galencolin (I had the same doubt when I watched your video,great video though ;))
We kill the first enemy at t=1, then our next shot will be ready at t = 1 + 4 = 5, now our next enemy will appear at 7 and last up to 8. Now, as we already have our shot loaded and we can kill enemy at any time between 7 or 8.
1 Like
I thought that it is compulsory to shoot at every x interval 
I thought like t=1,5,9,13 are dead compulsory to shoot no matter what!
They should have clearly mentioned that, we can skip the shoots, and its not necessary to shoot after every cool down time
Thanks for your time, Man!
2 Likes
Another good problem just like this one(Binary search over decimals) is LOGS on AtCoder. Check it out.
1 Like
Can you explain the reason for Upper bound > 2*10^9. even I am facing the same issue but i dont know the reason for it @galencolin
since we first we hit the enemy at 1 and then the cool down is 4 we wait for 4 min then after cool down is done we can again hit the element at 7 , ie it we hit it at 1,7 (since at we have our machine already cooled and not hit any machine after 4) (PS. we do not fire at time =4 but we wait for next element to arrive after the cool down period ) look at the (else-if condition in for loop where nxt < a[i]) we curr firing time at c[i] since our machine is already cooled and we have not fired after that (CodeChef: Practical coding for everyone)
Very simple case:
1
2 1000000000
1 1000000000
answer is like 2 \cdot 10^9 - 1 or something
so you always have to make sure your binary search bound actually works by imagining the worst-case, and don’t just guess it
3 Likes
thank you
took different higher bound in the two submissions and also you have a different template in the other solution.