The original solution is also O(NK), keep in mind that the size of D never exceed 139. So it does not matter whether you want to check the boundary from above or below. It is always O(139) for worst case.
Use binary search for finding the boundary could be faster, but the runtime could be dominated by the following loop anyway. -- 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/8a52fe2a-345a-43f8-89b6-e934fd38ad4e%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.