ZorbaTHut stays aliveby schveiguy,
The wildcard round proved to be as exciting as everyone had hoped. The 6 runners up started off with a pretty
standard easy problem that involved a search and could be solved depth of breadth first. With one exception, all
coders scored similarly on the first problem. lars and haha both opted to skip the medium problem, in favor of a
hard problem, hoping that no one would solve all 3. The rest of the coders moved on to the medium, and Zorba was
able to submit it for an impressive 457 points. Over the remainder of the coding phase, everyone but lars, who
skipped the medium, submitted the 500 point problem.
WordPuzzleThis problem maps to a simple BFS to find the shortest path. Perhaps the most difficult part is to define the edges. The easiest way to do this is to define a function isAdjacent(string s1, string s2), which should return true if the two strings are connected by an edge. Then, we can use bfs starting at the beginning word to determine the shortest path. The next part of the problem is to break any ties that may occur. Since all the strings are the same length, this job is made much simpler. One easy way to guarantee that a path is lexicographically smallest is to sort the words before running the BFS. Then you always use the lexigraphically smallest sequence first. Of course, you must make sure that you figure out which indexes the end and beginning strings are at before running the BFS. RussianDollsThis problem is pretty straightforward to solve with recursion. We define our recursive function as f(N, hidden, visible), which returns how many ways we can arrange a set of N dolls with hidden dolls behind the cardboard and the dolls in visible being outside the cardboard. We can define our recurrance relationship in terms of f(N1 hidden+x, visible). The four possible cases are:
long f(N, hidden, visible) { // check for invalid conditions if(hidden < 0  hidden > N) return 0; if(N == 0) // base case, no dolls return 1; if(visible.contains(N)) // envelop one of the hidden dolls return f(N  1, hidden + 1, visible) * (hidden + 1) // do not envelop, place it by itself + f(N  1, hidden, visible); // not in visible, place behind the cardboard else // envelop one of the hidden dolls return f(N  1, hidden, visible) * hidden // do not envelop, place it by itself. + f(N  1, hidden  1, visible); } With the recurrance relationship defined, we can use memoization with the number of dolls and the number of hidden dolls to make sure a timeout does not occur. Alternatively, you could start with 0 dolls and build the data up from there using DP. OpenBlackjackBlackjack is one of the only casino games where it is possible to have better odds than the dealer. However, it is still very possible to lose a lot of money really quickly. In this problem, you are trying to figure out how much money you really could have made if you had played all your hands perfectly. I will leave the explanation of the game of blackjack up to the problem statement. To solve this problem, we need to simulate play. Like the medium problem, the play can be defined with a recursive function, and can then be memoized against the current position in the deck and the money you have. One misconception that is proven false with some of the later examples is that you only need to store the maximum money earned at a given card in the deck. However, the rules of when you stop playing make this assumption false. If you win by blackjack, you win 1 and 1/2 times your bet, offsetting your winnings by 1/2 your bet. If you then lose all your money, you will potentially walk away with more or less money than if you didn't get blackjack. This nuance forces you to try sequences of card playing where you actually have less money at some points than with other sequences, but have more at the end. Each call of the recursive play function will play a single round of blackjack. Since the dealer's play is predefined, all the function can decide is what cards you take, and whether you double down or not. Surprisingly, these simple rules are difficult to write into code. Once the round is over, you are back to the beginning of the play function at a different position in the deck, and with a potentially different amount of money. Some corner cases to look for are doubling down only when it is allowed, scoring the current cards correctly, not allowing a hit on a score of 21, and what to do when you run out of cards. 
