Regarding C-large, during the competition I guessed that crafting a low collisions set was very difficult. I created one large test case with random numbers and sure enough it had collisions already summing up to 3 numbers.
So I downloaded the large input attempting the brute force solution summing up to 4 numbers that looked like a safe and fast bet (by mistake I really only summed up to 3!). I assumed that in the event of a degenerate set I would have had the time to look at it and find a way to deal with it. In fact summing up to 3 number proved to be enough and I submitted with plenty of time to spare. The reason it worked is the very high probability of collisions. See http://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem for the general formula. Basically summing up to 4 numbers you have approximately 2*10**7 results in a 10**14 space. Assuming random results (not true, but for a very rough estimate) and using the n(p,d) formula in the article you need to draw 2*10**7 numbers for a 90% probability of collision within a 10**14 range. Just within range. All results had 3 numbers or less for me, so probably there is more to it. A -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/c7gAd6DoAWMJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
