Ah! This should have occurred to me. And this explains the random
numbers, to make sure that we don't accidentally start searching in a huge
part of the space that happens to have no solutions. Since T >>> S, as
long as we're sufficiently random, we should trip over a match very quickly.
I suppose it's obvious that the "distinct subsets" bit is kind of a red
herring. If there is a match { 1, 2, 100, 101, 102 } and { 3, 100, 101,
102 }, there will also be { 1, 2 } and { 3} (i.e., that have no members in
common). I think this means that the number of cases we'd have to consider
is the number of ways the set can be partitioned into three sets (i.e.,
subset A, subset B, and everything else), which I'm thinking is 3^500 -
2^501. (?) Not important to the solution, though.
On Saturday, May 5, 2012 7:04:31 PM UTC-5, Yiu Yu Ho wrote:
>
> 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/-/7rZbbl5iPbMJ.
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.
