# 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

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 kth member. If k > 1, then k must also be pure, so let k be the ith 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.

Ben Lynn blynn@cs.stanford.edu 💡