Indeed Luke, using a greedy algorithm I can build such solutions, but it absolutely non-trivial! The actual complexity of the full algo must be higher.
limiting the number of items to sum to 3 I could build the following largest evil sets: space, len, set 10**4, 21, 1 2 4 8 15 28 52 96 165 278 460 663 980 1332 1864 2609 3375 4769 5600 6776 9141 10**5, 35, 1 2 4 8 15 28 52 96 165 278 460 663 980 1332 1864 2609 3375 4769 5600 6776 9141 11505 14453 17404 21904 25023 31159 35006 42780 51792 55799 68834 75036 87163 96746 10**6, 57, 1 2 4 8 15 28 52 96 165 278 460 663 980 1332 1864 2609 3375 4769 5600 6776 9141 11505 14453 17404 21904 25023 31159 35006 42780 51792 55799 68834 75036 87163 96746 116231 128924 144085 172606 193507 207826 232675 251441 277342 323253 356137 371053 431659 486285 522272 581498 611809 706660 745654 795188 869441 907179 My greedy algorithm looks decently optimized and is CPU bound on pypy, I'm not going to see beyond 10**6 without access to a real cluster. So summing up to 3 still looks like a safe bet even assuming a decent degree of evilness form the problem authors :) Really nice problem. A. BTW: The easiest impossible testcases are just the powers of two. For a 10*12 number space you can build impossible testcases only with sets it less than 37 items, i.e. [2**i for i in range(37)] is Impossible. On Monday, 7 May 2012 05:01:56 UTC+2, Luke wrote: > > I am pretty sure you can find such a set, yes. Greedy Algorithm will work. > Take the smallest positive integer you can at each stage that won't cause > two triples to have the same sum. > > The number of forbidden numbers, if you have n numbers already, is at most > 10C(n,5). For n = 500, this is about 500^5/12=31250000000000/12=2.6x10^12. > On 6 May 2012 19:29, wrote: > >> I'm a bit uncomfortable with using that formula for a rigorous >> analysis of the "examine all subsets of size k" solution. >> >> I can agree with it for the "randomly sample all subsets" solution, >> because I can even show that it is quite pessimistic there. And it >> would certainly convince me during the contest (had I come up with it) >> that this approach was worth trying. >> >> However, from the problem setter's point of view, I'd want to come up >> with a set where all 3-subsets have distinct sums. More generally, >> I'd want to find a set that maximizes the minimum cardinality of the >> answer. The birthday paradox formula does not exclude the existence >> of such a set, though it indicates that it might be quite difficult to >> find. >> >> I'm fairly sure that the numbers in such a set simply grow too fast >> (from my attempts to construct it) though I don't have a proof that >> there isn't a significantly more economical construction. I found >> some literature about sets where all subsets have distinct sums, but >> nothing yet about k-subsets for small k. >> >> Flipping the problem around, can you find a set of 500 numbers in the >> range [1, 10^15] such that testing all 3-subsets won't find a >> collision? The birthday formula gives only a 7% success rate, but I >> suspect that it is guaranteed to work even in this expanded range. >> >> On May 6, 7:49 am, "Richard Braakman" <[email protected]> wrote: >> > > All results had 3 numbers or less for me, so probably there is more >> to it. >> > >> > No I think your analysis is enough. >> > >> > Picking 3 numbers from 500: about 20 million possibilities >> (500!/497!/3!) >> > >> > Range of the sum of 3 numbers of that set: about 3 * 10**12 >> > >> > According to the formulas on the wikipedia page for the birthday >> problem, >> > drawing 20 million numbers from that range gives an almost certain >> collision. >> > The chance of not finding one would be about 1 in 10**31. >> > >> > Richard Braakman >> >> -- 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/-/jjMGqcmlOn4J. 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.
