abhioshar's blog

Google APAC Test 2016 Problem
By abhioshar, history, 9 years ago, In English

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:

  1. 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).

  2. 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 ?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 to answer = -1.

You need to handle P = 100 case specially.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can somebody explain the logic behind the question, i.e how to find the min and max number of files? Thanks.

→ Reply