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
Even after considering a special case ( 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.
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 ?