Jam 2013 Round 1B
Posted on 26th April 2015
As ever, links to: Official Contest Analysis and my code on GitHub.
I did this under timed conditions, and would have just qualified. A silly error was all which stood between B large and me...
Problem A, Osmos: Start with A and \( (x_i)_{i=1}^N \) integers. You can absorb one of the \( x_i \) if it's smaller than A, and then A grows by \( x_i \). Help Armin to be able to absorb all the numbers by adjusting the initial set:
- You can add any new number;
- You can remove a number.
What is the least number of moves to get a valid set?
- Order so that \( x_1 \leq x_2 \leq \cdots \leq x_N \) as optimal case is to absorb from small to large.
- If Armin is trying to absorb \( x_i \) but can't then A is too small, so add in a new number \( A-1 \). Maybe repeat this step a few times.
- Now consider removing numbers: it only makes sense to remove the largest number (if you can't deal with a smaller number, then removing it just makes the next larger number ever harder to deal with!)
- So compare removing the last
k terms with how many "additions" these k would take up, and find the smallest overall number of moves.
- My code actually checked if there was any k whereby removing k terms was better, removed them, and then iterated. I now don't see why this works...
- Corner case: if A=1 initially, Armin can never absorb anything, and the optimal solution is just to remove all numbers.
Problem B, Falling Diamonds: The diamonds form this sort of triangular pattern:
* * * -
* * * * - -
* * * * * * * * -
* * * * * * * -
* * * * * * * * * *
The final picture shows one possible "half-way" point, with - marking slots to be filled in future. Each new diamond takes a 50/50 split at the top, and falls down one side.
- So test if the coordinates X Y can ever be the centre of a diamond.
- Work out which "layer" the Nth diamond will fall in. If X Y are in the a previous layer, the probability is 1.0; if X Y is in the next layer, it is 0.0
- Otherwise, we have to work out or simulate the probability. Consider [a b] to indicate that the left pile contains a diamonds, the right b diamonds. With n = 0, 2, 4, 6, ... the layer height, then the transition probabilities are:
- If a, b <= n then 50/50 chance of going to either [a+1 b] or [a b+1]
- If a==n then move to [a b+1], and if b==n then move to [a+1 b]
- A little paper analysis shows that you get a variant of Pascal's triangle (where later rows are "truncated"). Alternatively, just naively compute the probabilities, which is what I did. (Stupid mistake was not to notice that there are in general 2 ways to get to [a b] on the next step, so a dictionary is a better data structure than a list...)
Problem C, Garbled Email: I initially tried a DFS with pruning (aka backtracking) algorithm. This worked, but was too slow, even for the small case. So I cheated, and my Python code is just an implementation of the suggested route (elements of which you can see in my initial attempt!) which is a Dynamic Programming solution combined with cunning precalculation. (Don't walk the dictionary, but rather look up in it!)