In the next round of the Google Code Jam this year, 3686 people scored at least some points. Only the top 1000 would advance, though, which took at least 53/100 points and a fast enough time.
I first attacked
Problem B. Kingdom Rush. It has a long explanation you can see at the link, but here's a short summary:
- There are N levels to finish
- Each level can be completed with a 1 star or 2 star rating; if it is previously completed with 1 star, completing it with 2 stars only earns one additional star, and completing it with 1 star is meaningless. Thus, the maximum possible stars to earn is 2N
- There is a prerequisite number of stars to get a 1 star rating on a level, and a greater or equal prerequisite to finish the level with 2 stars.
The object is to find the fewest number of runs possible to complete all levels with 2 stars, if it's possible at all. Levels don't have to be completed in any order.
One sample input is:
0 2
0 1
meaning that there are 2 levels, and the first level has a pre-req of 0 for 1 star, and 2 for 2 stars. One example run could be finishing level 2 with 1 star (now you have 1 star), then finishing level 2 with with 2 stars (now you have 2 stars), then finishing level 1 with 2 stars in one single run because the pre-req is only 2 stars, for a total of 3 runs.
An impossible input would be
1 1
1 1
1 1
because, starting with 0 stars, there's no way to finish any level first.
Also impossible would be
0 0
0 0
0 6
because you couldn't get 6 stars before attempting 2 stars on the last level.
My first approach was to try to finish the first possible 2-star level, and if one wasn't reachable with the current level of stars, try the first possible 1 star level. This solved the test data, but my submissions for the small input kept getting rejected, so I knew there must be an additional trick. I tried to come up with solutions that broke my algorithm, and discovered one.
0 1
0 3
With this input, first I'd try all the 2-star values, and fail. Then I'd take the first 1-star value, leaving:
0 1
0 3
The next run would take the first possible 2-star value, at 1.
0 1
0 3
Next, the 2 star search would fail again, and it would take the next 0.
0 1
0 3
Then the 3, for a total of 4 runs.
0 1
0 3
But, I can see a faster way. First, take the last 0
0 1
0 3
Now that I have 1 star, I can complete the first level all at once
0 1
0 3
And with 3 stars, I can complete the second level, for a total of 3 runs
0 1
0 3
Adding the run for the final level lets this one get finished in 3 runs instead of the previous 4. So the flaw in the algorithm was in taking the first available 1-star, when instead I needed to take the 1-star associated with the highest possible 2-star value, in order to leave the others available to possibly finish both stars in one single run. I fixed my algorithm and submitted the small input, which was then correct. I submitted the large input and had to wait until the end to find out it if it was right, which it was.
Next, I attempted
Problem A. Password Problem. Again, it has a long explanation, I'll try to boil down to some bullet points.
- I have already typed A characters of my password, which is B characters wrong.
- The chances I typed each of the A previous characters correctly are given
- All future characters will be typed correctly
- My choices are
- keep typing
- backspace 1 to A characters and continue typing
- hit enter and start over.
The object is to choose the strategy to minimize the expected number of keystrokes.
Side note: I don't usually like expected value that much.
Here was the contest example:
Suppose my password is "guest" and I have already typed the first two characters, but I had a 40% chance of making a mistake when typing each of them. Then there are four cases:
- I typed "gu" without error. This occurs with probability 0.6 * 0.6 = 0.36.
- I typed the 'g' correctly but I made a mistake typing the 'u'.
Then I have two letters typed still, but the second one is wrong: "gX".
(Here, the 'X' character represents a mistyped letter.)
This occurs with probability 0.6 * 0.4 = 0.24.
- I typed the 'u' correctly but I made a mistake typing the 'g': "Xu".
This occurs with probability 0.4 * 0.6 = 0.24.
- I made a mistake typing both letters, so I have two incorrect letters: "XX".
This occurs with probability 0.4 * 0.4 = 0.16.
I don't know how many mistakes I actually made, but for any strategy, I can calculate the expected number of keys required to use it. This is shown in the table below:
"gu" "gX" "Xu" "XX" Expected
Probability 0.36 0.24 0.24 0.16 -
Keystrokes if I keep typing 4 10 10 10 7.84
Keystrokes if I press backspace once 6 6 12 12 8.4
Keystrokes if I press backspace twice 8 8 8 8 8
Keystrokes if I press enter right away 7 7 7 7 7
My first thought here was that I would need to calculate the 2^A possibilities, so if I got character 1 right or wrong, combined with if I got character 2 right or wrong, etc. Since A could be up to 99999 in the problem statement, I knew that wouldn't be feasible. Then I realized it only mattered what the odds were of typing the first x characters correct, and anything after the first wrong character didn't effect the answer to the problem. that is why the columns under "Xu" and "XX" look the same
I treated the "keep typing" case as pressing backspace 0 times, so that it fit more nicely in my code. Now there were only 2 cases to check. Pressing enter right away was easy, the answer was always the same, so the expected value was always B+2, for the first enter, the B characters of the password, and the final enter.
Since the probability could be different for each letter, I stored them in a vector with the intent to multiply the ones I needed. Then I realized that what I really needed was the cumulative probability of getting all letters right up to any given letter, so I stored the values as
p1, p1*p2, p1*p2*p3,...
resulting in a new vector
P(0), P(1), P(2), P(3)...
Now I could figure out the answer in linear time. Letting the number of backspaces be C, and looping over C from 0 to A, the expected value with C backspaces was the product of all of the probabilities of typing characters 0 to A-C correct, times 2C+B-A+1 (C backspaces, C replacement characters, the rest of the password, plus the enter key), plus 1 minus that product times 2C+2B-A+2 ( The 2C+B-A+1 from before, plus another B characters when it is rejected, and the final enter).
So the answer to each case, given A, B, and the vector of p's is:
min(B+2,P(A-C)(2C+B-A+1),(1-P(A-C))(2C+2B-A+2))
for all C 0 to A
(I really need to get LaTeX working for Blogger to write fancier equations.)
I thought I had cleverly solved this one, and submitted the small input. Unfortunately, the large was wrong because I had not planned on reading in 900,000 characters from the input file on a single line, and some code I wrote several years ago broke. This is because each case was input as:
A B
p1 p2 p3 ... pA
Where px is the probability of getting character x correct. The probabilities were in the form x.xxxxxx, so a total of 9 characters each including numbers, decimal point, and space. With A up to 99999, there were nearly 900k characters on one of the lines.
So the takeaway from this round was to fix my input reader. I finished with 43 points, placing at #1463.
On to Round 1B!