Google APAC Test 2016 Problem

general
, , , ,
1

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 ?

2

its better to just do

new_lower_bound = (k[i]*100)/(p[i]+1) ,

and check if (k[i]*100)%(p[i]+1) == 0 or not. and adjust accordingly.

oh, and in a special case check if p[i] == 99 also.

There might be an error because of how floats are implemented. 99.99999999 may be erroneously read as 100

1 Like
3

Easy if u do it

int o,l //Note o,l is not float

o=(p[i]*100)/k[i]

do{
l = (p[i]*100)/k[i]

i++

}while(o==l&&i<n)

if (o==l)

return o

else

return -1

4

I used a similar approach… Failed Large tests… Any idea why?

5

Actually this approach is giving -1 in the third sample case mentioned on the site instead of 23.

6

Finally got accepted for both small and large inputs.

During the iteration just do update as follows:

For lower bound(take the max so far):
if(p[i] != 100) (k[i] * 100)/(p[i]+1) + 1
else (k[i] * 100)/(p[i])

For upper bound(take the min so far):
if(p[i] > 0) (k[i] * 100)/p[i])