Hello,
In the analysis for the Infinite House of Pancakes (
https://code.google.com/codejam/contest/6224486/dashboard#s=a&a=1) there's
a solution (in C++) with complexity O(D*M). The analysis also mentions
another possible solution which is O(D*sqrt(M) + M), without showing the
code. Could you provide an example implementation of that solution, or
suggest how to adapt my Python solution to match it?
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/CAJjqdb9OCkkwg7R7E-sdbwvcvyNnotpKU03ceNnw0xecgtRB9A%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
