On Tuesday, May 8, 2018 at 10:25:26 AM UTC, henrik...@googlemail.com wrote: > I would really like to see how the Python Solutions that pass comfortably > look like. If I understood things correctly, the solutions in this thread > which pass just pass barely (with 13 secs out of 15 secs), and the whole > question is not so complicated that there is a lot of room for improvement. > > I just thought that it might be possible to look for the "h" using binary > search, which might speed up things a bit. But then the list in which we are > searching has at most 140 entries so it can't make things that much better.
Oh I didn't read your solution correctly. :-( So you correctly has the complexity O(nk). And I donno why searching from 0 makes it work (instead from from 139). Perhaps that has something to do with the actual test data (i.e. some data with N=100000 need much less than 139 entries). Anyway, the statement "For exactly 6 cases" in the problem statement is fishy, i.e. hinting constant level optimization. Anyway, binary search does somewhat helps, because you only need to do the comparison 8 times. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/8676575c-0cf0-46df-89f1-b0493e3dfda6%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
