Jam 2015 Round 1C

Posted on 10th May 2015

Urgh, so failure! Some silly (stupid) errors meant my good start of getting problem A out in 16 minutes didn't get me anywhere, as a silly not checking the boundary conditions killed problem B, and not thinking on paper long enough got to problem C. 3 hours and less stress, and it would have been 100/100, but I guess everyone says that about exams. (Of course, given the competition, Round 2 was going to be the end anyway).

As ever, links to: Official Contest Analysis and my code on GitHub.

Problem A, Brattleship: It's in your brother's interest to drag the game out for as long as possible: once he says "hit" we move to a 2nd phase which can only end more quickly.

  • So the worst case is when the brat says "miss" until he has no choice but to say hit.
  • You want to chop the board up into regions where the ship cannot hit: so strips of width W-1. So we hit points W, 2*W, 3*W, ...
  • Do each row, and then in the final row, at the final point, brat must say "hit" and we move to a 2nd algorithm of finding the ship.
  • So we have "?????#????" where the first block of "?" is of length W-1 and the end perhaps of shorter length. As soon as you have narrowed the space down to length W then it's game over, so it's in brat's interest to drag this out.
  • Notice that if the known "hit" is at the edge, then we know where the ship is, and we win in W-1 further goes.
  • Otherwise, we can't win in W-1 goes, as our next choice can always consistently be a "miss". We can win in W further goes though (and so this is optimal). We just explore in one fixed direction (left or right). The first time brat says "miss", we know the end of the ship, and we win. As there can only be one further "miss", we do use just W goes.

Problem B, Typewriter Monkey: Monkeys choose uniformly at random from letters (maybe with repeats) for S goes. You pay them one Banana per copy of the target word (multiple copies can overlap, so if target is "AA" then "AAA" contains 2 copies). You bring the maximum number of Bananas you might need: what is the expected number of bananas you'll have left after payment?

  • In the small case, you can quickly generate all possible outputs and associated probabilities, and then brute-force calculate the maximum and expectation. In the end, I did this.
  • Let \( A_S \) be the random variable of how many copies of the target word a string of length S contains. We need \( \mathbb P(A_S = k) \) for various k. For example, the largest value of k with this non-zero is the maximum number of bananas needed. We also need \( \mathbb E(A_S) = \sum_k k \mathbb P(A_S=k). \)
  • Remember a trick from probability: if \( X \) is an integer-valued random variable, then \( \mathbb E(X) = \sum_{n\geq 0} \mathbb P( X \geq n ). \)
  • My solution uses dynamic programming to calculate \( \mathbb P(A_S \geq k ) \) by considering how to build a valid string of length S from one of length S-1. This seems to require asking that the string of length S-1 ends in a certain way, so we need to keep track of this as well (what I call the postfix in the code).
  • Got wrong the boundary conditions (check for count <= 0 not count == 0) and also forgot that if using the Python functools.lru_cache then we need to clear the cache (the dictionary of letter probabilities is global, for efficiency, and because dictionaries cannot be hashed by default).

Problem C, Less Money, More Problems: Given a set of denominations of money D, a variable C which the maximum number of times we can use any coin of one denomination, and V, we wish to make all values up to and including V. What is the minimum number of additional demoninations we need to add to D to make this happen?

E.g. C=1, D=[3,5], V=8 then initially we can make 3, 5, 3+5=8 only. If we add 1 we can now make 1, 3, 4, 5, 6, 8 (and 9, but don't care). Now add 2 and we can make everything, so here the answer is 2.

  • My initial brute force attempt had the following bug: in an ordered list of everything we can make, I checked there were no gaps, but not that we got everything up to V. Stupid...
  • The proper answer (or a proper answer) is very easy though. Suppose we can make 1,2,...,k but not k+1. Then we can add a coin of denomination 1, 2, ..., k+1 (assuming they are not in D already) to allow us to make k+1. However, the set of new possibilities increases with the value of the coin we add, so the best solution is to add k+1 itself.
  • We can now make 1,2,...,k, k+1, k+2, ..., k+k+1, 2*(k+1), ..., C*(k+1) + k so we have a whole "initial interval" we can form. If n <= C*(k+1) +k is also in D and we're not yet using it, then we can additionally make all the numbers up to C*n + C*(k+1)+k.
  • So each time we add a new denomination, we end up with an "initial interval" of numbers we can form from a certain "used subset" of D, and the remainer of D consists of larger numbers. We just repeatedly add denominations.
  • The worst case is something like adding 1, 2, 4, 8, ... and each time we have to scan over D, so the complexity is something like O( |D| * log2(V) ).
Categories
Recent posts