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/-/68DvdctRuzkJ. 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.
