ABBADiv1 (d1 easy)

The main idea here is that you should work backwards from the target string to the initial string. Almost any solution based on this idea can work. The simplest solution, conceptually, is to do a recursive backtracking search. It will run in polynomial time without any memoization at all. Why?

If it runs in exponential time, we need a branch at each step (a choice of whether to try the last move as A or B). But suppose we had the option of picking A, and we picked B. Now we can never pick B again, since the first character in the string will always be A. So that branch will be resolved in polynomial time. The total complexity is something like O(N³).

You can solve it in O(N) with KMP and prefix sums.

ChangingChange (d1 medium)

In this solution we will assume valueRemoved[i] = 1 for all i.

Let's use generating functions. Suppose ways = {1, 3, 6, 2}. Then we will view it as the polynomial 1 + 3x + 6x² + 2x³. You can show that adding a coin is equivalent to multiplying by (1 + x). So removing a coin must be equivalent to multiplying by . That's equal to 1 - x + x² - x³ + x⁴... (if you don't like calculus, work out the first few terms and you'll see it's 1, -1, 1, -1, 1...). So if numRemoved[i] = n, we want to find the coefficients of (1 - x + x² - x³ + ... ± x^D)ⁿ in linear time. You can show by induction that the signs always alternate for any value of n, so all we need is the magnitude of the coefficients of (1 + x + x² + x³ + ... + x^D)ⁿ.

How can we find those coefficients? Multiplying by that polynomial is equivalent to taking the prefix sum of the coefficients. For example, (1 + 3x + 6x² + 2x³)(1 + x + x² + x³) = 1 + 4x + 10x² + 12x³ + .... There's a combinatorics problem where the values for a given n are the prefix sums of the values for n - 1: the number of right-down paths on an n by c + 1 grid (where c is the coefficient we want). And the formula for that is .

So, here is the formula that solves the problem:

To solve it when valueRemoved[i] ≠ 1, just replace ways[D - c] with ways[D - c·valueRemoved[i]].

WarAndPeas (d1 hard)

Instead of cards and pairs, call them vertices and edges in a complete graph. Let's call the lowest-numbered vertex (the one whose owner never changes) the source vertex. Other vertices that are the same colour as the source are good. Otherwise they're bad.

The critical observation is this: suppose we know there are X good vertices. Then all distributions of the X good vertices are equally likely. This is true regardless of the number of steps. We can prove it by induction on the number of steps (clearly it's true after 0 steps, since each vertex is assigned to the two owners with equal probability). Now we make a new move and select edge E. There are a few cases; note that while the relative chances of these cases depend on the value of X, they don't depend on the distribution of the X good vertices:

• E touches the source vertex. Since all edges touching the source vertex are equally likely to be selected, this preserves the hypothesis.
• E connects a good vertex to a good vertex or a bad vertex to a bad vertex. By the induction hypothesis, all distributions are equally likely. If this outcome happens, the state of the graph is unchanged. Therefore this preserves the hypothesis.
• E connects a good vertex to a bad vertex. Suppose A's colour is overwritten by B's colour. For every distribution where A was good and B was bad, there was an equally likely distribution where B was good and A was bad. So this also preserves the hypothesis.

So, instead of 2^N states, we have N states, where state i represents the state with i good vertices. Suppose Carol's state has x good vertices. By linearity of expectation, we can find the expected number of times we enter state i, divide by , and we have the answer. Normally you would do this with a system of linear equations, but solving a general system takes O(N³). We can speed it up to O(N) (times log factor for modular inverses) by using the fact that state i can only enter state i - 1, i, and i + 1. Represent the expected value from state x as a function of the expected value from state x + 1. It turns out that the function is very simple: f(x) = f(x + 1) + c for some constant c. We can work it out starting from state 0, going to state N - 1, then working backwards and representing the function as a constant c. Add up the expected value from each state, multiplied by the chance of starting in that state, and you are done.

Probably that explanation made no sense, so here is the code: https://ideone.com/ggJ2qd.

ChessFloor (d2 easy)

Try all possibilities. The tricky case is that you can't have all tiles the same color, but it was included in samples.

ABBA (d2 medium)

Work backwards from the target state. The previous move can be uniquely determined by the last character of the string, so simulate it until the strings are the same length and then check if they're equal.

CheeseRolling (d2 hard)

Use DP with 2^N·N states, and iterate over all possibilities for the bracket. The complexity is .