There are T = 2^500 - 1 non-empty subsets, each takes on sums between 1 and S = 10^12 * 500. Since T > S, by pigeonhole principle there are at least two sets with the same sum. The harder (and more amazing) part is to prove that you can find one quickly by examining a very smal number of these subsets. Wait for the analysis ;).
On Saturday, May 5, 2012 4:08:36 PM UTC-7, tutufan wrote: > > The official analysis hasn't been posted (yet). Sometimes they don't post > one, so I'm not sure whether we get one this time. > > In any case, I'm impatient and interested in any insights, so here's some > half-baked speculation. (Disclosure: I didn't successfully answer any of > these, so all of this might be crap.) > > (spoilers, of course) > > For A, I initially conjectured that it was sufficient when looking at a > contestant to consider only the "other" contestant having the lowest score, > and to take enough votes from them to guarantee that they cannot beat us. > This is false, though, as input like "0 0 100" shows. > > The next idea was that maybe it's sufficient to claim 1/N of 2X total > score, imagining a sort of global leveling (imagine a landscape filling > with water). That doesn't work either, as some high scorers are like > "peaks" that will stick up, ruining the simplicity of this calculation. > > Later, I had the idea of imagining that I had X buckets of water (or > whatever) to distribute, with the goal of ensuring that my candidate > doesn't end up with less than anyone else. So, for example, if we have "0 > 2 5 98", we will have 105 buckets to distribute (based on audience vote). > We first distribute two buckets to "0", to bring it up to the next level, > 2. Then we distribute three buckets to each of the first two, to bring > them all up to five. This leaves us with 97 buckets, which we split across > the first three, bringing them up to (5 + 105/3) each. This indicates the > proportion that my candidate must get not to lose. (Corner case: with one > candidate, the answer is 0.) I think this might be correct, but didn't > have time to code it. > > The #1 rank solution to this problem was submitted in 4:03/4:34, and to me > it uses a quite impressive insight. The idea is that since we're trying to > estimate a proportion, and we have a reasonably easy way to check our > estimates, and furthermore that the result needs to be really close, but > not exact, that we can simply run a binary search to converge on the > answer. (This also requires some sort of convexity property or something, > which happens to hold here.) Amazing. Also amazing, or more like > incomprehensible, is being able to read the problem, conceive the solution, > type it, compile it, and go through the small/large submit cycles in under > five minutes. Is this the work of an AI? :-) > > For B, this looks like a reasonably straightforward search. We know > there's no point in visiting any square more than once. Search depth can > be bounded by the best result found at any given point. Perhaps A* or IDA* > could be used to some benefit, but probably it's fast enough without. It > would be nice to figure out the set of initially reachable squares and then > chain backwards from the end square, but I don't think this is possible, > because of the need to count the clock forward. > > For C, I assumed that the small input case could be easily brute-forced, > and that the large case could not, and required some sort of number theory > insight. (Why else would this problem be worth so many points?) It would > seem that the large case would take a spectacular amount of time to brute > force (O(2^500)), but apparently this was not the case. I believe the > reason is that for the inputs given, a solution was always possible, and > could be found within the alotted time (because the solution space was > dense with solutions). Indeed, at least one solution doesn't even have any > provision for printing "Impossible". Needless to say I'm slightly annoyed > I didn't catch this. So, I'm wondering, is this actually a provable > property of sets of distinct whole numbers <= 10**12 having size 500, or > was it just luck that these all had a quick solution? (I also saw that a > number of solvers made use of a random number generator--did this actually > matter?) > > Mike > > -- 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/-/vXeDGV6eyU8J. 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.
