Contents

2010 Round 1B

File Fix-it

We already solved this recommended beginner problem.

Picking Up Chicks

There are two types of chicks, those that could never make it even if they were running by themselves, and those that could if only the way were clear. Let’s call these slow and fast chicks respectively.

We can forget about trying to help slow chicks make it to the barn.

If a fast chick catches up to a slow chick, we must lift the slow chick if we want them to make it to the barn. Otherwise, if a fast chick catchs catches up to another fast chick, then both will still make it to the barn even running at the slower of the two speeds.

Thus the solution is to find the k fast chicks closest to the barn, and lift all the slow chicks that block them.

import Data.List
import Jam

main = jam $ do
  [_, k, b, t] <- getints
  xs <- getints
  vs <- getints
  let
    isFast x v = b - x <= t * v
    f ((a, cost), b) True  = ((a + 1, cost + b), b)
    f ((a, cost), b) False = ((a    , cost    ), b + 1)
    cs = map fst $ scanl f ((0, 0), 0) $ reverse $ zipWith isFast xs vs
  pure $ maybe "IMPOSSIBLE" (show . snd) $ find ((k ==) . fst) cs

Your Rank is Pure

For the small input, we examine all subsets of [2..n], and see if n is pure:

import Data.List
import Data.Maybe
import Jam

main = jam $ do
  [n] <- getints
  let
    f 1 _ = 1
    f n s = maybe 0 ((`f` s) . (+ 1)) $ elemIndex n s
    a = map (\n -> sum $ f n <$> subsequences [2..n]) [2..25]
  pure $ show $ a!!(n - 2) `mod` 100003

For the large input, suppose we want to construct a set where n is pure. Say n is the k`th member. If `k > 1, then k must also be pure, so let k be the `i`th member.

This suggests a method for recursively constructing the desired sets. First construct a set where k is pure and also the largest member. Then add in any subset of [k + 1..n - 1] of size k - i - 1, and finally add n.

Memoizing this recursion with Data.MemoTrie gives a fast solution:

import Data.List
import Data.Maybe
import Data.MemoTrie
import Jam

main = jam $ do
  [n] <- getints
  let
    m = (`mod` 100003)
    mch _ 0 = 1
    mch 0 _ = 0
    mch n k = m $ ch (n - 1) (k - 1) + ch (n - 1) k
    ch = memo2 mch
    mf _ 1 = 1
    mf n k = m $ sum [m $ f k i * ch (n - k - 1) (k - i - 1) | i <- [1..k-1]]
    f = memo2 mf
  pure $ show $ m $ sum $ f n <$> [1..n-1]

Unfortunately, the first time around I implemented n choose k as:

ch = n * ch (n - 1) (k - 1) `div` k

which breaks when we apply a modulus. We should multiply by the inverse of k modulo 100003 instead, but it’s easier to switch to an additive formula and memoize. Another solution is to avoid the reduction until the last minute. It might also be better to use an existing library to compute binomials, such as Math.Combinatorics.Exact.Binomial.choose from the exact-combinatorics package.

Contents
Ben Lynn blynn@cs.stanford.edu 💡