Problem B:
For the small case, there are only at most 20 diamonds. So even if you need to
decide left/right all 20 times, there are at most 2^20 scenarios. We all know
that 2^20 is a million and a bit. So we can just play out all the scenarios and
work out the probability the hard way.
For the hard case, I can't imagine any solution that doesn't include noticing
Observation 1.
Observation 1:
The falling diamonds actually fall in a very structured way, filling up bigger
and bigger triangles. Specifically when the location at (0,2k) is filled, the
filled locations will be all points with | X | + | Y | <= 2k, and no other
points.
Running a few simulations will persuade you of that. For proof:
In order for (0,2k) to be filled, both of the things down and to the left and
right must be filled, and all of the things you can get by moving down-left and
down-right in any order. This is all points of the form | X | + | Y | <= 2k.
Before (0,2k) is filled, any falling diamond falls to (0,2k) and then takes
steps of the form (0,-2), (1,-1) and (-1,-1) until it stops. Note that any such
move does not increase | X | + | Y |, so no points with | X | + | Y | > 2k can
be filled before (0,2k) is filled.
Next we need to work out how many (X, Y) have | X | + | Y | <= 2k. Let the
answer be f(k). We can calculate all relevant f(k)'s by:
* Set f(0) = 1
* Set k = 0
* While f(k) < 1,000,000:
* Increment k
* f(k) = f(k - 1) + 4k + 1. // 2 points at heights 0, 1, 2, ..., 2k-1 and 1
point at height 2k
Alternately we could know that this would mean f(k) would be quadratic and work
out the coefficients as 2k^2+3k+1.
For a given location (X, Y) with | X | + | Y | = 2k, we know that (X, Y) will
fill up within the first f(k) diamonds, but not within the first f(k - 1)
diamonds. Thus if N <= f(k - 1), the answer is 0 probability, and if N >= f(k),
the answer is 1 probability.
Otherwise, write N = f(k - 1) + r. We know that 0 < r < 4k + 1.
Once the first f(k-1) diamonds have fallen, the spaces with | X | + | Y | = 2k
and X negative fill up in increasing order of Y, as do the spaces with | X | +
| Y | = 2k and X positive, so the problem is equivalent to:
Suppose we flip r coins, but after the first 2k heads we note down all heads
as tails, and after the first 2k tails we note down all tails as heads. What is
the probability that there are at least Y+1 heads.
Note that if r <= Y, it is impossible to have filled the space, while if r >=
2k+Y+1, it is impossible not to. So in these situations we can return 0 and 1
respectively.
If, on the other hand, r < 2k+Y+1, it is impossible to have had 2k heads and
noted down Y+1 tails, so the problem is equivalent to: Flip r coins. What is
the probability that there are at least Y+1 heads.
It turns out that in the large data set, r cannot be more than 2000, so we can
work out all possible answers as follows:
* Set p(X,0) = 1 for all 0<=X<=2000 // Flip X coins, there will be at least 0
heads.
* Set p(X,X) = 1/2^X for all 0<=X<=2000 // Flip X coins, there will be at
least X heads with probability 1/2^X.
* For X=2 to 2000
* For Y=1 to X-1
* Set p(X,Y) = ( p(X-1,Y) + p(X-1,Y-1) ) / 2
Then for a given case (X,Y,N) we do the following:
* Let k = ( | X | + | Y | ) / 2
* If N <= f(k - 1) + Y: probability is 0
* If N >= f(k - 1) + 2k + Y + 1: probability is 1
* Otherwise: probability is p(N-f(k-1), Y+1).
On 5 May 2013, at 07:57, Luke Pebody <[email protected]> wrote:
> A brief outline:
>
> Problem A:
>
> If A=1, no motes can ever be eaten, so the answer is you have to remove all N.
>
> On the other hand, if A>1, suppose that in the optimal solution you remove k
> motes. It seemed intuitive to me that the k motes you remove would be the
> largest k and that for the others what you could do is:
> Arrange the smallest N-k motes in increasing size
> Then loop through the motes you are going to eat in increasing size:
> If you are already big enough to eat the mote, eat it.
> Otherwise, you add a mote of size A-1 (if you are going to add a mote, you
> might as well add as big a mote as you can possibly eat).
>
> To put another way, what you do is: whenever there is a mote you can eat,
> eat it. When there isn't, add the biggest mote you could eat and eat that.
>
> This leads to an O(N) solution - actually O(N log N) because you have to sort
> the motes.
> * Sort the motes in increasing order.
> * Set record = N // It is always possible to just remove all N motes, but
> maybe a boring level.
> * Set removals = N
> * Set additions = 0
> * Set currentSize = A
> * for each moteSize in motes:
> * while currentSize <= moteSize:
> * currentSize += currentSize - 1
> * additions += 1
> * currentSize += moteSize
> * removals -= 1
> * if additions + removals < record:
> * Set record = additions + removals
> * Output "Case #CaseNumber: record"
>
> Before submitting for large, if using fixed length integers, think about
> whether any of your integer variables can overflow.
>
> In this case, they won't - you will only double in size until you are bigger
> than a mote, which means doubling won't make you bigger than 2,000,000. The
> remaining increases in size will be from eating all the other motes, of which
> there are 100 of size at most 1,000,000, so you cannot possibly end up larger
> than 102,000,000, which is less than 10^9, which fits in a signed 31-bit
> integer.
>
>
> Sent from my iPad
>
> On 5 May 2013, at 00:43, Jugesh Sundram <[email protected]> wrote:
>
>> This time I was completely knocked out. I knew how to solve them but ended
>> up spending time in debugging. Can't wait for the Contest Analysis.
>>
>> Any idea when they will be out?
>>
>> --
>> Jugesh Sundram
>> ([email protected])
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Google Code Jam" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>> To post to this group, send email to [email protected].
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
