2011 Google Code Jam: Round 1

Again, here is the most important detail first: I advanced!

As of this writing I'm sitting at 910th place in Round 1B.  Assuming no disqualifications of me or anyone else, that's where I'll stay.  As a reminder, Round 1 is split into sub-rounds A, B, and C.  Everyone can compete in 1A, and the top 1000 advance.  All but those 1000 can compete in 1B, and again, the top 1000 advance.  Finally, everyone but the already-advanced 2000 gets one final shot in 1C, and again, the top 1000 advance.  This mean there will be 3000 coders in Round 2, and I'm one of them.

As Google noted, Round 1A was brutal.  I skipped the lowest-value Problem A out of fear it wouldn't be enough to advance (As it turns out, solving it in 42:01 would have been enough).  I also felt like there were some tricky cases in it that made it harder than it should be for the points offered.  Problem B also seemed like it could wind up taking too long to run a quickly coded solution.  So, I focused in on the highest-value, Problem C.

You are playing a game with a fancy deck of cards. Each card has three bonus numbers: a card bonus c, a score bonus s, and a turn bonus t. Some of the cards start in your hand, while the rest are in a deck on the table. You start with one turn.

On each turn, you can choose any card from your hand and play it. If it has bonus numbers c, s, t, then the following happens:

• The card is discarded from your hand, and it can never be used again.
• You draw the first c cards from the deck into your hand. If the deck has fewer thanc cards in it, you draw all of them.
• Your total score increases by s.
• Your number of remaining turns increases by t.

If you do not have any cards in your hand at the start of a turn, then nothing happens on that turn. Your goal is to get as high a score as possible before running out of turns.

For example, suppose your hand and deck contain the following cards:

         +---+---+---+            +---+---+---+
   HAND: | c | s | t |      DECK: | c | s | t |
         +---+---+---+            +---+---+---+
Card #1: | 0 | 0 | 2 |   Card #4: | 1 | 1 | 0 |
Card #2: | 0 | 5 | 0 |   Card #5: | 0 | 1 | 1 |
Card #3: | 2 | 1 | 1 |   Card #6: | 2 | 2 | 0 |
         +---+---+---+            +---+---+---+

The following table shows how you can get a score of 8 from these cards. The first three columns show your hand, the number of turns left, and your score before playing each card, and the final column shows which card to play.

+---------+------------+-------+------+
| Hand    | Turns left | Score | Play |
+---------+------------+-------+------+
| 1, 2, 3 |      1     |   0   |   1  |
| 2, 3    |      2     |   0   |   3  |
| 2, 4, 5 |      2     |   1   |   2  |
| 4, 5    |      1     |   6   |   5  |
| 4       |      1     |   7   |   4  |
| 6       |      0     |   8   |   -  |
+---------+------------+-------+------+

As you can see, the card bonuses and turn bonuses allow you to chain together a long sequence of cards before you have to stop.

My first instinct turned out to be correct, but it went south from there.  I figured out the best thing to do is play any cards with a turn bonus first.  That would certainly have no negative effect on the potential final score.  From there I tried varying strategies, from playing the cards with the highest card bonus, to playing the highest score when you're down to your last turn, to a recursive brute force algorithm.  None worked for even the small input.  I ended with 0 points.

Round 1B turned out much better.  I just about jumped out of my chair when I saw Problem A.  It asked for a fairly simple RPI calculation.  I've written lots of code like this for various personal projects, such as writing an algorithm designed to be "Better than the BCS" and decide the best team in College Football and any sport.  At the 32:03 mark, I had full credit for the small and large input.  I wondered if that would be enough to advance, but I suspected it might not.  I read the next problems and took a quick break to think about which one I could do best.

Problem B looked most plausible to solve quickly, so I went for it.

Last year, several hot dog vendors were lined up along a street, and they had a tricky algorithm to spread themselves out. Unfortunately, the algorithm was very slow and they are still going. All is not lost though! The hot dog vendors have a plan: time to try a new algorithm!

The problem is that multiple vendors might be selling too close to each other, and then they will take each other's business. The vendors can move along the street at 1 meter/second. To avoid interfering with each other, they want to stand so that every pair of them is separated by a distance of at least D meters.

Remember that the street is really long, so there is no danger of running out of space to move in either direction. Given the starting positions of all hot dog vendors, you should find the minimum time they need before all the vendors are separated (each two vendors are at least D meters apart from each other).

My solution wasn't quite optimal, so it worked for the small input, but failed for the large input.  In fact, I let my solution on the large input run much longer than the allotted 8 minutes.  After an hour, I finally stopped it, still with no solution.  My first naive solution was to move in increments of 0.5s, start with the leftmost vendor, and move everyone 0.5m to the left, as long as they would not get closer than D meters to the vendor to the left.  In that same 0.5s, I did the same thing starting from the right and looping to the left, moving everyone to the right as long as they wouldn't get too close.  I refined the solution a bit before attempting the large input, but still it took too long to run.

With my time expired on Problem B and not enough time to think out a solution on Problem C, I was down to scoreboard watching.  I saw my rank drop slowly from 561, down to 999th with 19 minutes to go.  When it hit 1009 with 18 minutes to go I knew I had to get out of the house for a bit before I went crazy.  I ran 2 quick errands and returned about 45 minutes after the end of the contest, and saw I finished in 910th place, good enough to advance.  This happens because Google gives an "optimistic" score during the competition, so anyone who submits a solution for the large input gets credit until the correctness of the solution is revealed at the end.  My large input solution for Problem A was correct, and enough other solutions were incorrect to vault me back into the top 1K.

For the 3rd consecutive year I've made the top 3000.  I'm hoping I can get one step further this year and hit the top 500 to make it to Round 3, but I'm pretty happy with how far I've gotten already.