For the Problem C, I was trying to use the below strategy.
First count m days in the answer, since rate of replenishing the stock is greater than the rate of consumption. After that, for the next day, the number of grains left would be
n-m-1
for the next to next day, the grains left would be
n-m-1-2
and so on.
At the last, we get
x^2 + x -2n + 2m >= 0
where x is the number of days required. But using this strategy fails.
All the solutions that I saw were using binary search. Has somebody use similar technique in their solutions or can someone point out mistake in doing this way?
First of all, this is problem C, and not B.
Now, moving to the problem, consider a simple case where the answer is less than M. Example :
1 10
The answer for this case is 1, whereas urs would be 10 I guess
@_AJ_, corrected that mistake.
Yes, you are write. I didn't thought of that case. But when m is less than n, then this will work?
Just saw the editorial. The problem is with using the square root function which leads to error in accuracy.
Doing binary search, avoids that issue.
Formula solution works as well. Just need to be a little bit tricky.
@serrg, Yes it can be done. For that I think, if we get ans as x, then we should also check x-1, x+1 values. And use one, which satisfy our criteria.
I just computed r=sqrt(2(n-m)). The only two candidates are r+m and r+m+1. If r*(r+1)>=2(n-m), then that's it, if not it should be r+m+1. Almost all people who solved this problem in my room uses similar logic, some of them failed the system test, some of them (including me) passed:)
@yinanzhu, can you tell why you use the above equation, r=sqrt(2(n-m)). In my code I was using this (-1 + math.sqrt(1.0 + 8 * (n — m))) / 2.0 but it is failing some cases.
If n>m, the rats took x more days after mth day to empty the barn. x will be the first number such that x*(x+1)/2+m>=n, so I used that formula. I do not understand your formula but I guess it is right because it can past some testcases. I think in order to avoid precision issue you should avoid doing division as much as possible, and of course check if the result is what you want before you submitted it.
@yinanzhu, thanks for your reply. Really good suggestion to keep in mind. But I finally managed an AC. Instead of
I just changed it to
It seems individually multiplying by 8 was an issue.
Glad you made it:)
I used the sqrt approach. Check my submission.