Damn! I desperately need some sleep. But here it is the trick: do not look for candidates just above the last number you added to the evil set, because it the place where collisions are more dense. Instead skip forware, for example skip the first D = S[-1]-S[-2] and look for candidates from there (or from D*102,4% if you want to go faster).
So, I could build an evil set of 500 numbers below 10**12 in just above 5 minutes. I'll post the code here later: http://codejamdaemon.blogspot.it/2012/05/equal-sums-google-codejam-2012-round-1b.html A. On Tuesday, 8 May 2012 21:47:00 UTC+2, Luke wrote: > > I have an idea for implementation of finding an evil set. But no time in > which to code. > On 8 May 2012 20:41, "A" wrote: > >> The series you point out is not our evil set (one with no duplicate sums >> adding up to 3 numbers) >> because is starts with 1,2,3 and 1+2=3. The equivalent evil set start >> with 1,2,4 then the algorithm >> is the same: http://oeis.org/A062065 >> >> I further optimized my implementation and I managed to build an evil set >> of 174 numbers >> with the highest being 194274204 in 1.5 hours on my notebook. >> >> My current estimate is that evil sets of 500 numbers obviously exist, but >> building one >> will require anywhere between 1.5 and 150 years on my hardware. >> >> So somehow Google could come up with one evil set if it desperately >> needed it :) >> >> A. >> >> On Monday, 7 May 2012 12:13:41 UTC+2, Luke wrote: >>> >>> http://oeis.org/A036241 >>> >> -- >> 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/-/zSGZ3AVZii8J. >> 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. >> > -- 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/-/mJudPtvHegwJ. 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.
