Google codejam Qualification Round analysis

this is just a reblog post from this blog. I sincerely request you to visit the main blog page if you are seeing this….

Google Code Jam 2014 Qualification Round Analysis

The Qualification Round this year just ended. As I realized when competing for the first time last year, this round is really meant to distinguish those who know how to program (at all) from those who don’t, and to introduce people to the system. You just needed to score 25 points to advance, out of a possible 90 points, and you have slightly over a full day to do it. I worked on the problems last night shortly after they came out (but during dinner and such, so not rushing through them in full time-trial mode), and ultimately finished 606th among those who got all 90 points.
A. Magic TrickThis was basically a warmup puzzle. With only a small input worth 6 points, it wasn’t worth much, but these points could be important, because combined with the 8 points from B small and either 11 or 14 from C or D small, you could qualify with just 3 confirmed small answers.

The problem statement pretty much tells you what to do. Given two layouts of cards, and the fact that the chosen card is in a particular row of each layout, either identify the card if it is unique, or emit specific messages for the cases where there is no such card or more than one.

B. Cookie Clicker Alpha

First off, from the example, observe that the cookie gain is continuous, and if you are gaining 2 cookies per second and need 7 cookies, you will have them after 3.5 seconds (rather than after 8 seconds with one cookie left over). This simplifies things greatly and makes an algebraic solution to the problem feasible.

However, the farms are discrete. You’re going to buy some whole number of them, and you can calculate the required time for each possible number of farms. At the start you gain cookies at 2 per second, so if you don’t buy any farms, it takes X/2 seconds to finish. If you buy one farm, it takes C/2 seconds to buy it, leaving you with a balance of 0 cookies, and then X/(2+F) seconds to finish. And if you buy 2 farms, you need C/2 seconds to buy the first one, C/(2+F) seconds to buy the second, and X/(2+2F) seconds to finish. this leads to a general formula, if you buy k farms, of C(1/2 + 1/(2+F) + … + 1/(2+(k-1)F)) + X/(2+kF).

Yuck! The sum of the reciprocals of an arithmetic sequence. That doesn’t look like something that can be easily replaced with a simple formula.. However, the numbers aren’t too big, so maybe we can just brute-force sum the numbers. How many farms might you have to buy, anyway?

The key to answering that question is realizing that you are in a diminishing returns situation. When you buy farm k, you are saving (X-C)/(2+(k-1)F) – X/(2+kF) seconds. This becomes
((X-C)(2+kF) – X(2+(k-1)F))/((2+(k-1)F)(2+kF))
(2X+kFX – 2C – kFC – 2X – kFX + FX)/((2+(k-1)F)(2+kF))
(FX – 2C – kFC)/((2+(k-1)F)(2+kF))
The denominator is always a positive number, strictly increasing with k. The numerator decreases with k. This means that this savings always decreases with more farms, and by setting this to zero and solving for k, you can see that after (FX-2X)/FC farms, it decreases to no savings at all. What is the largest this could be? It gets larger tha smaller C is, so set C to the minimum of 1. Then it becomes X – 2/F which is always less than X, which is no more than 100,000 even in the large case. So you never have to add more than 100,000 terms for each of up to 100 test cases, and you can easily do that within the time limit. You can also use this expression to determine when to stop adding farms.

C. Minesweeper Master

This turned out to be the hardest problem of this round, with more than half of those who attempted a small case solution never getting it right, while 90% or more who attempted the other small cases got them right. Also, fewer people even attempted this problem than there were correct answers for both small and large inputs for all the others.

We’re not playing Minesweeper in any normal sense, but it will help you to understand this problem if you have played it. We are just asked whether it is ever possible, for a Minesweeper game on a given size board with a given number of mines, to win the game with a single click, based on the game behavior where if you click a “0” – a space not adjacent to any mines – the game treats it as if you had clicked all the adjacent spaces as well. To win, you have to reveal (click, explicitly or implicitly) all the non-mines. This means that all the non-mine spaces need to be in a contiguous group, and all the 0s have to be contiguous, and all the non-zero numbers must be next to a zero. And you need to have at least one 0, unless there is only one non-mine space, which you naturally click to win. [Special case #1]

There were two likely ways to go about this. In the brute force approach, which would work for the small case, you consider all possible arrangements of mines on all the differently sized boards up to 5×5. That’s 2^25 or about 33 million boards for the 5×5 case, about a million for 5×4, and less than a million for all the other sizes combined. On each board, compute the number corresponding with each non-mine space, and then see if when you click one of the 0s, whether that would reveal all the non-mines. Save an example for each case that works, and make a note that the rest are impossible. There are only 25 cases on the 5×5, 20 cases on the 5×4, etc.; not very many at all. Then read the input file and spit out the known solutions for each case, or “Impossible”.

To solve the hard input, you need to actually understand a bit more about what the group of cells revealed by a single click can look like; of course, we need the size of this group to equal the number of non-mines on the board. It’s possible you might start with the brute force approach and browse your solutions to begin to figure this out, but I went straight to this step. If you click a nonzero, you only get that space revealed, so you can always win if there is only one non-mine. In the general case where there is more than one non-mine, you have to click a zero, but from here the game splits into three cases: board which are one square wide (one row and/or one column), boards which are two squares wide (2 in one dimension and 2 or more in the other), and other boards.

    • If the board is only one space wide, and all the mines are at one end, then clicking any of the 0s will reveal all the non-mines, so you always win such boards. [Special case #2]
    • If the board is two squares wide, then clicking a zero always reveals an even number of spaces, at least 4, because the two squares in each row have the same neighbors, and are either both 0 or both nonzero. In each two-space row, if there is a mine, then both squares in the row next to it are next to a mine and hence both nonzero. This means that if there is a row with only one mine, it is going to have a nonzero in its row which is not next to any 0 in an adjacent row, and this means you can’t win in one click on those boards. To win in one click, there have to be an even number of mines located on a number of complete rows of 2 at one end of the board, and at least two rows of non-mines (so that you can have a zero to click). [Special case #3]
    • In the normal case with boards at least 3 in each dimension, if you click a zero, always at least 4 spaces are revealed, and that happens only when you click in a corner, and there is only one zero. (So 2 or 3 non-mines is always impossible.) If there is a zero on an edge, at least 6 spaces are revealed. And if there is a zero in the interior, at least 9 spaces are revealed. For other numbers, you have to combine these (keeping in mind that the revealed areas overlap). If you only have 0s on the edge and corners, always an even number of spaces is revealed. Each additional 0 in the group adds 2 more revealed spaces, except when you add a corner to a group that already has an adjacent edge or when you add the next-to-last or last edge square after going all the way around the board; those other cases add no revealed squares. So if you are going to have an odd number of revealed spaces, it must be at least 9. (So 5 and 7 are also always impossible.) It turns out that you can make every other case. One way to do this is to start with the kind of group I described previously to get every even number of revealed spaces up to a border two units wide around the board. For odd numbers, also add one 0 one space diagonally away from a corner where you’ve already got the other three spaces in the 2×2 in that corner as 0s; this cuts away a single mine diagonally adjacent to the selected space. And for larger numbers, you can keep adding more 0s, cutting away one square at a time from the central group of mines.

Now that is a constructive proof, what you need to solve the problem. It is a bit complicated to program that particular solution for the normal case, and you might do something different. (I actually did, though it wasn’t any simpler, really, in the end. Mine was that if the number of empty spaces is at least two whole rows plus two spaces, put all the empty spaces at the beginning – some number of full rows plus a partial row – unless this leaves a single empty space at the start of the last row, in which case you pull down one empty space from the penultimate row to put two in the last row. If there fewer empty spaces, make them into the smallest possible 3 x N rectangle in the top three rows, leaving out the last one or two spaces of the third row if needed. This works for 6 and 8 to the cutoff for the other solution. Finally, 4 is a special case. And in all my cases, I clicked on the first square at the upper left.)

So this was hard because of all these special cases, but I actually had all of the special cases right. I had a wrong submission because of errors in my solution drawing routine. But what actually took me the longest was to realize that I had written “Impossible!” with an exclamation point when the problem actually wanted “Impossible” with no punctuation. I blame problem A, which included exclamation points. But this is the kind of stupid failure to read carefully what the problem is asking for that will cost me dearly if I do it in the later rounds. I didn’t actually realize my error until revisiting the problem in the morning.

D. Deceitful War

Ken’s basic War strategy is not too hard to figure out. He just plays the greedy strategy: If he can beat Naomi’s block, he does so as cheaply as possible, and if he can’t, he throws his worst block. The question is, though, how often does he win or lose using that strategy, and whether Naomi play her blocks in an order to affect that result. After a bit, I convinced myself that the answer was given by the following algorithm:

    • Sort all the blocks from heaviest to lightest.
    • Go through the list, keeping a score which is the number of Naomi’s blocks encountered minus the number of Ken’s blocks encountered.
    • The maximum value of this score at any point during the traversal is the number of times Naomi will win, regardless of the order in which Naomi plays her blocks.

Naomi always wins at least this many times (call it N), because considering only the heaviest so many blocks up to the first point where she was ahead by N, Naomi has N more than Ken, and so no matter how he chooses his blocks, he must lose at least N times among his responses to these blocks.

Given that, let this be Ken’s “ideal” play: Ken plays his worst N blocks on Naomi’s best N, and among the remaining ones, Ken plays his worst on Naomi’s worst, second worst on her second worst, etc. Although his actual play may vary from this depending on the order in which Naomi presents her blocks, it always does so in a way that benefits Ken. First off, note that this play does indeed let Ken win all but N of the points. Because N was the largest Naomi’s excess reached in that traversal of the ordered block list, we know that Ken’s best block is always heavier than Naomi’s N+1st, Ken’s 2nd heavier than Naomi’s N+2nd, etc. For the same reason, when Naomi plays her N+kth best block, Ken will either play his kth best block (which is heavier), or he will play a lighter block (but still heavier than Naomi’s), leaving him with a heavier one than he actually needs. If Naomi plays one of her N best blocks and Ken beats it, he won a turn he didn’t need to, at the cost of losing one turn later, when she plays, say, her N+1st block and Ken can’t beat it.

My first thought about Naomi’s strategy for Deceitful War turned out to be invalidated by the sample input. I thought that Naomi would lie about her worst M blocks, saying each was just under the weight of one of Ken’s heaviest blocks, to make him use those up, and once all her blocks were heavier than all Ken’s remaining blocks, just tell the truth from there on out, and win all but M, where M is the number of losses necessary to reach that state. But that would have her win 6 times for the last sample input, where it claims she wins 8 times.

After a bit more thought, I came up with Naomi’s actual best strategy. As above, she has a certain number of unavoidable losses, but with this strategy, it’s the minimum number of losses she must experience under any sequence of play by both players. For the cases she is going to win, she starts with the lightest of these, and she lies and says it is heavier than any of Ken’s blocks. This causes Ken to throw his lightest block, which loses. Then she does the same with the second-lightest of the ones she is going to win, etc. Finally, she plays the ones she must lose, and if she plays these last, she can tell the truth about them. She can still play them earlier, but she must lie about them in order to make Ken play his best blocks on them. The number of unavoidable losses is calculated in the same way as Ken’s number of unavoidable losses in the regular War game, except it’s the most that Naomi was ever behind in the count, rather than ahead. As a result, it can be calculated at the same time you are calculating the other, keeping track of both the minimum and maximum of Naomi’s blocks – Ken’s blocks as you traverse the sorted list of all blocks.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s