Contents

2010 Qualification Round

Snapper Chain

After trying a few examples, we realize the chain of Snappers is a binary counter. The light bulb is on if and only if all n bits are one, which happens every 2^n iterations, when the coutner reads 2^n - 1:

import Jam
import Data.Bool

main = jam $ do
  [n, k] <- getints
  pure $ bool "OFF" "ON" $ (k + 1) `mod` 2^n == 0

For this problem, it may be better to head straight to a smart solution. Writing a brute force simulation means we have to simulate a binary counter:

import Jam
import Data.Bool

main = jam $ do
  [n, k] <- getints
  pure $ bool "OFF" "ON" $ and $ iterate snap (replicate n False)!!k

snap [] = []
snap (x:xs) = (x /= and xs) : snap xs

Fair Warning

The GCD of two numbers divides their difference. The difference between any two times is unaffected by adjusting both by the same offset, thus we simply take the GCD d of all the differences between all pairs of times, then calculate how fare we are from the next multiple of d:

import Jam
import Data.List

main = jam $ do
  (_:ts) <- getintegers
  let d = foldl1' gcd $ (-) <$> ts <*> ts
  pure $ show $ (d - head ts) `mod` d

We take advantage of built-in arbitrary precision arithmetic in Haskell.

We’ve wastefully computed the difference for both orderings of every pair, as well as the difference between every time and itself, but this factor of 2 is unimportant even for the large input.

Theme Park

We simulate each ride to solve the small input.

If everyone in the queue can fit in the roller coaster, then the problem is simple. Otherwise, the cycle function fits nicely with the way people rejoin the queue, and calling scanl1 (+) on the queue gives a cumulative sum.of the number of people who have ridden the roller coaster so far.

We break this list into chunks such that each chunk is as large as possible and that the cumulative sum at the end of one chunk differs from cumulative sum at the end of the previous chunk by at most k.

Then we simply print the cumulative sum at the end of `r`th piece.

We zip a list to a displaced version of itself to give us handy access to the previous chunk’s cumulative sum:

import Data.List
import Jam

main = jam $ do
  [r, k, _] <- getints
  gs <- getints
  let
    csum = scanl1 (+) $ cycle gs
    f q = dropWhile ((<= snd (head q) + k) . fst) q
    brute = snd . head $ iterate f (zip csum (0:csum))!!r
  pure $ show $ if sum gs <= k then r * sum gs else brute

For the large input, we memoize: before each ride, we record the group at the front of the queue, the number of times i0 the roller coaster has run, and number of people t0`who have ridden so far. Then just before the `i`th run, if we see the same group at the front of the queue again, and there have been `t total people who have ridden the coaster so far, we compute:

(quot, rem) = divMod (r - i0) (i - i0)

and fast-forward by quot * (i - i0) runs, that is, with rem runs remaining, the total number of people who have been on the roller coaster so far is:

t0 + (t - t0) * quot

We use brute force simulation for the remaining rem runs.

To recognize a group we’ve seen before, we label them [0..n - 1] and zip the labels to the cumulative sums. For fun, we use const to generate the right number of labels, rather than rely on the n given in the input, which we ignore completely.

import Data.List
import qualified Data.Map as M
import Jam

main = jam $ do
  [r, k, _] <- getints
  gs <- getints
  let
    step q = dropWhile ((<= snd (head q) + k) . fst) q
    csum = scanl1 (+) $ cycle gs
    f m i xs@(x:_)
      | snd x `M.member` m = t0 + (t - t0) * quot +
        snd (head $ iterate step (fst <$> xs)!!rem) - t
      | otherwise          = f m' (i + 1) $
        dropWhile ((<= t + k) . fst . fst) xs
      where
        m' = M.insert (snd x) (i, t) m
        t = snd $ fst x
        (i0, t0) = m M.! snd x
        (quot, rem) = divMod (r - i0) (i - i0)
  pure $ show $ if sum gs <= k then r * sum gs else f M.empty 0 $
    zip (zip csum $ 0:csum) $ cycle $ zipWith const [0..] gs
Contents
Ben Lynn blynn@cs.stanford.edu 💡