There was a problem in Google APAC Test 2016 Round C (Problem B) — gFiles (https://code.google.com/codejam/contest/4284487/dashboard#s=p1 — Google Login may be required).
The approach that I came up with which ran successfully on the sample cases was:
Find the lower bound and upper bound on the number of elements (because for a particular value of k[i] and p[i] only a handful of values of total files are possible which lie between lower_bound and upper_bound).
To find these bound, iterate over the entry i (p[i] and k[i]) and do
Iterate over array
if(p[i] != 0 && k[i] != 0)
lower_bound = max(lower_bound, ceil((k[i]*100.0)/(p[i]+0.9999999)) upper_bound = min(upper_bound, floor((k[i]*100.0)/(p[i]))
else if(p[i] == 0 && k[i] != 0)
lower_bound = max(lower_bound, ceil((k[i]*100.0)/(p[i]+0.9999999))
End of Iteration
If lower_bound == upper_bound
answer = lower_bound
else
answer = -1
While giving the correct outputs for the sample cases, it failed on system test on small inputs.
Can anyone give a hint on where was the fault in my approach ?
Assume only one piece of information available:
K = 10000, P = 100.Correct answer is
answer = 10000, obviously.However, your algorithm gets
lower_bound = 9901, upper_bound = 10000, which leads toanswer = -1.You need to handle
P = 100case specially.Yeah, that was a bug. Thanks.
Even after considering this case specially ( checking P[i] for 100 in the iteration and modifying the lower_bound and upper_bound according to it i.e setting both of these to K[i] ), I am not getting the correct output.
Maybe there is some other silly bug or my approach is incorrect. Not sure!
Can somebody explain the logic behind the question, i.e how to find the min and max number of files? Thanks.