SRM 619: Nesting min-cost matching inside dynamic programming

Div1 250: The one with stacks

You start with up to 50 piles of stones. Two players play a game alternating turns. In a given turn, a player must pick three piles: `(a,b,c)` such that pile `a` has at least 2 stones. Pile `a` is split into two non-empty piles and their amounts are added to pile `b` and pile `c`. If a player cannot find any valid turn, they lose. Find if the first player is guaranteed to win or to lose assuming the two players play optimally.

During the match, I did a dynamic programming based on the fact that the game state can be described by two variables `(p,q)` where `p` is the number of piles with more than 1 stone and `q` the number of piles with 1 stone. This leads to an `O(n^2)` dp.

However, as it turns out, the problem can be solved in `O(1)` time. Note that every valid step will always reduce the number of piles by 1. It turns out that all cases with an even number of piles are losing states, so if the number of piles is odd AND there is at least one valid move, then the state is winning.

Need to prove that all even states are losing ones. This is obviously true for `n = 2`. So for `n >= 4`, we figure that the only losing states with `n-1` are those that consist entirely of 1s. However, it is impossible to reach such a state using any valid number of moves, because after any valid move, at least two of the piles will be greater than 1.

Div1 600: ouch

This problem's statement is very long to copy and to re-write. So I will skip to the solution.

Imagine you wanted to calculate `f(x,i)`, the minimum cost to assign skills to the sub-tree rooted at `x` if you already know that one of the skills chosen for `x` is skill `i`.

We can easily find `f(y, j)` for any child of `x` and skill `j`. Out of all the skills assigned to `x` and its children, it should be possible to make a permutation of skills. Let's focus on this permutation. There are two possibilities.

• Use `i` in the permutation, meaning that all children must use skills different to `i`.
• Use a different skill in the permutation for `x`. All children and `x` need to pick a unique skill.

Using the values of `f(y,j)` and some ad hoc stuff, you can easily build a table of costs for each case, the cost of assigning each of the employees to each skill in the permutation. Then you have a minimum-cost bipartite matching. Too difficult to implement in the little time I had after figuring this out.