Contents

2014 Qualification Round

I found this round easier than the previous year’s. I originally tried the problems in C. Magic Trick is easiest by far, though I still managed to mess up my original solution in C (a parsing bug involving a premature break causing it to get out of sync).

Minesweeper Master was relatively easy to solve, but hard to code, while Deceitful War was the opposite.

I feared my solution Cookie Clicker Alpha was too simple, probably because of past bad experiences. Had I overlooked a floating point issue? For the large input, were we supposed to derive a closed formula for the series? No and no. It really is a nice easy problem.

Magic Trick

Haskell’s intersect function makes short work of this problem.

import Jam
import Data.List

main = jam $ do
  b1 <- getsn 5
  b2 <- getsn 5
  let f rs@(r:_) = words $ rs!!read r
  return $ case f b1 `intersect` f b2 of
    [x] -> x
    [] -> "Volunteer cheated!"
    _  -> "Bad magician!"

Cookie Clicker Alpha

Unspent cookies earn no interest, thus if we intend to buy a farm, we should do so as soon as possible.

Given a rate r, we see if it’s quicker to simply get x cookies (which takes x/r seconds), or if it’s quicker to buy one more farm (c/r) then get x cookies (x/(r + f)). If the former is quicker, then we’re done, otherwise we recurse to see if it’s worth getting more farms.

import Jam
import Text.Printf

main = jam $ do
  [c, f, x] <- getdbls
  let g r t | x/r < c/r + x/(r + f) = t + x/r
            | otherwise             = g (r + f) (t + c/r)
  return $ printf "%.7f" $ g 2 0

Minesweeper Master

We solve this with a straightforward but tedious approach.

import Jam
import Data.List

main = jamLn $ do
  [r, c, m] <- getints
  let
    d = replicate
    n = r * c - m
    g r c = let
      draw [n]    = [d n '*' ++ d (c - n - 1) '.' ++ "c"]
      draw (n:ns) = (d n '*' ++ d     (c - n) '.') : draw ns
      draw _ = []
      in draw $ if n == 1 then d (r - 1) c ++ [c - 1] else f r c
    f 1 c = [m]
    f 2 c | n > 2 && m `mod` 2 == 0  = let h = div m 2 in [h, h]
          | otherwise                = []
    f r c | n `elem` [2, 3, 5, 7]    = []
          | a == r - 3 && b == c - 1 = d a c ++ [b - 2, 1, 1]
          | a >= r - 2               = let (h, j) = divMod (m - (r - 2) * c) 2
            in if j == 0 then d (r - 2) c ++ [h, h]
                         else d (r - 3) c ++ [c - 3, h + 2, h + 2]
          | b == c - 1               = d a c ++ [b - 1, 1] ++ d (r - a - 2) 0
          | otherwise                = d a c ++ [b] ++ d (r - a - 1) 0
      where (a, b) = divMod m c
    pic = if r <= c then g r c else transpose $ g c r
  return $ if null pic then "Impossible" else init $ unlines pic

Deceitful War

In the normal version of the game, each turn, after Naomi reveals the weight of her block, Ken’s optimal move is the following:

  • If he has no block heavier than Naomi’s, then Ken plays his lightest block.

  • Otherwise he plays the lightest of his blocks that are heavier than Naomi’s.

No matter what order Naomi plays her weights, the resulting score will be the same, and optimal for Ken.

In Deceitful War, order matters. Each turn, Naomi plays her lightest block.

  • If it’s lighter than all of Ken’s blocks, Naomi induces Ken to play his heaviest block by naming a weight just below it.

  • Otherwise she names a weight above Ken’s heaviest block, inducing him to play his lightest block.

We could compute this with recursion. Or, we could notice an amazing symmetry: each turn, Ken either plays his lightest block, and Naomi beats it by playing her lightest block that outweighs it, or he plays his heaviest block against Naomi’s lightest block.

Going back to the honest variant of the game, we may order Naomi’s moves so that Ken plays his blocks from lightest to heaviest. If we do this, and swap Ken’s and Naomi’s names around, we see we have recreated Deceitful War. In other words, playing Deceitful War is the same as playing the original game, except Ken goes first!

Thus we can compute the score for both routines using the same algorithm. We use a simple recursion, and imagine we’re playing the honest game: each iteration, we remove Naomi’s lightest remaining block. If it’s heavier than Ken’s remaining blocks, then add the number of remaining blocks to her score, as she wins the rest. Otherwise, remove the lightest of Ken’s blocks that is heavier than Naomi’s and increment Ken’s score.

import Jam
import Data.List

main = jam $ do
  gets
  ns <- sort <$> getdbls
  ks <- sort <$> getdbls
  return $ show (length ns - f ks ns 0) ++ " " ++ show (f ns ks 0)

f [] [] acc = acc
f (n:ns) ks acc = let (ka, kb) = break (> n) ks
  in if null kb then acc + length ks else f ns (ka ++ tail kb) acc
Contents
Ben Lynn blynn@cs.stanford.edu 💡