2010 Round 1B
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 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.