Hello,
The analysis for the "Infinite House of Pancakes" problem
(https://code.google.com/codejam/contest/6224486/dashboard#s=a&a=1) shows code
for the O(D*M) solution. However, it also mentions a O(D*sqrt(M) + M) solution
(without showing the code). Can someone provide an example code or tell me how
to adapt my Python solution to be O(D*sqrt(M) + M) ?
def solve():
T = int(input()) # the number of test cases
for case in range(1, T+1):
input() # the number of diners with non-empty plates, ignored
diners = [int(x) for x in input().split()]
minutes = max(diners) # the max stack of pancakes (= the max time)
# try to arrange all pancakes to stacks of equal height
for ncakes in range(1, minutes):
s = sum([(d - 1) // ncakes for d in diners if d > ncakes]) #
number of special minutes
if s + ncakes < minutes:
minutes = s + ncakes
print(f'Case #{case}: {minutes}')
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/fe0d6ab4-a4bd-46bc-98e7-eacc890f31ae%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
