OK, I can see how that works. Furthermore, the Birthday Paradox formula is like the "worst case" for the expected trials (uniform probability), so it performs even better than that.
The solutions I don't quite get are the ones that simply try subsets non-randomly, in increasing order of cardinality (they look very similar to what one would do if one didn't realize that 2^500 was a big number!). The only hope of finishing in time is if there is a solution where both subsets have cardinality <= 4, but the pigeonhole argument doesn't seem to rule out a set of 500 numbers s.t. all subsets of size 4 or less have different sums. In fact I can pass the large input only trying subsets of size 3. So what am I missing? Is there an obvious argument that there must be subsets of size 3 that have the same sum? I recall having the idea to try something similar during the contest but came up with 6 as the required subset size, so I didn't bother. I'm anxiously awaiting the analysis :) On May 5, 9:15 pm, tutufan <[email protected]> wrote: > I'm thinking that Yui Yu Ho had the key observation on this above. Using > those numbers, I think you can liken this to a Birthday Paradox problem > where there are about 2^40 possible days of the year, and 2^500 people at > the party. The wikipedia page has some approximations that suggest that > the one hits a 50% of finding a matching pair at around 26 million or so, > if I've plugged it in right. > > > > > > > > On Saturday, May 5, 2012 9:51:59 PM UTC-5, [email protected] wrote: > > > Hmm, I thought I had figured out that randomly generating two subsets > > could be as bad as a 1 in k chance of having the same sum, where k is > > the number of distinct sums...this seemed too unlikely to work in > > time. > > > Though perhaps I made an arithmetic error. More likely there is some > > other observation we can make about the distribution of the sums and > > their multiplicities beyond what the simple pigeonhole principle tells > > us. That worst case was based on the power means inequality so it > > happens when all sums have the same multiplicity, which for cases I > > tried is definitely not the case. I didn't figure out how to > > formalize that though. > > > On May 5, 6:08 pm, Lewin Gan <[email protected]> wrote: > > > For A, binary search was the way I approached it as well. This was a > > > pretty straightforward trick, since you want to see if it is possible > > > to distribute the rest of the votes such that all of them go over some > > > amount. > > > > For B, you can notice that you want to get to the square as early as > > > possible. That is, you can always wait for the water level to be the > > > appropriate level. That gives a BFS approach using a priorityqueue, by > > > popping off the square with the least time elapsed, and expanding that > > > edge. > > > > I wasn't able to solve C, but most people solved the small using brute > > > force (O(2^20)). As for the large, it's impossible to construct a set > > > of 500 with all distinct subset sums (i.e. there are a total of 2^500 > > > possible subset sums, but the maximum value we can obtain is 10^12 * > > > 500, thus, by pigeonhole, there must be at least some subset sums that > > > are equal). Thus, since there is such high probability of collisions, > > > randomly generating subsets of a fixed size until finding a match is a > > > valid approach (i.e. if you fix the size to be x, there are a total of > > > (50 ncr x) subsets, so choose x small enough for an exponential > > > solution to run in time, but large enough so your probability of not > > > finding a match decreases quickly enough). > > > > Those are pretty short descriptions, but they give the basic ideal of > > > the solution. > > > > On May 5, 4:08 pm, tutufan <[email protected]> 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- Hide quoted text - > > > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. 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.
