2008 Round 1A

Minimum Scalar Product

This problem is an old friend from before. We rewrite our solution to use our Jam module, showing off a little with sequence and replicate.

import Data.List
import Jam

main = jam $ do
  [_, xs, ys] <- sequence $ replicate 3 getints
  return . show . sum $ zipWith (*) (sort xs) (reverse $ sort ys)

Milkshakes

The problem is equivalent to finding a assignment to variables to satisfy an expression in conjunctive normal form, such as:

(a | b | c) & (a | ~d | e) & ...

Truth corresponds to unmalted; variables assigned false values correspond to malted milkshakes.

Fortunately there’s one additional proviso that makes this problem trivial: each clause has at most one negated variable. This means we can:

Look for a singleton clause. If none exist, then we can assign the remaining variables to true, and output a solution.
Otherwise, the variable in the singleton clause must be assigned a certain value to satisfy the expression. We add the assignment to an accumulator list, remove all clauses that contain the same literal, and remove any occurrences of the negated literal from the remaining clauses.
If any of the clauses are now empty, then there is no solution. Otherwise go back to step 1.

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

main = jam $ do
  [[n], [m]] <- getintsn 2
  let
    showSol sol = unwords $ show . flip (M.findWithDefault 0) sol <$> [1..n]
    f sol cs | [] `elem` cs = "IMPOSSIBLE"
             | otherwise    = maybe (showSol sol) g $ find ((1 ==) . length) cs
             where
               g [[x, y]] = f (M.insert x y sol) $
                 delete [x, 1 - y] <$> filter (notElem [x, y]) cs

  f M.empty . map (chunksOf 2 . tail) <$> getintsn m

Numbers

I spent a long time on the wrong path because my first instinct was to attempt to solve the question for any number of the form a + b sqrt(5).

Eventually I realized there was something special about the choice of 3 and sqrt(5). I was lucky sqrt(5) was chosen, because it triggered a memory of Binet’s formula. Recall the second term is always less than 1, so we can evaluate the formula by finding the integer closest to the first term.

This led me to consider:

f n = (3 + sqrt 5)^n + (3 - sqrt 5)^n.

This is always an integer because all the terms involving sqrt(5) cancel out. Furthermore, 3 - sqrt(5) < 1, so the answer is simply:

(f n - 1) `mod` 1000

Since 3 + sqrt(5) and 3 - sqrt(5) are the roots of x² - 6x + 4, we can describe f(n) with the recurrence f(n) = 6 f(n-1) - 4 f(n-2) and f(0) = 2, f(1) = 6.

Using repeated squaring, we can compute the nth power of the 2x2 matrix [[6, -4], [1, 0]] modulo 1000 and apply it to [6, 2] to find f(n).

import Control.Monad
import Data.List
import Text.Printf
import Jam

m = [[6, -4], [1, 0]]

mul [[a, b], [c, d]] [[x, y], [z, w]] =
  map (map (`mod` 1000)) [[a*x + b*z, a*y + b*w], [c*x + d*z, c*y + d*w]]

pow m 0 = [[1, 0], [0, 1]]
pow m 1 = m
pow m a | mod a 2 == 1 = mul m2 m
        | otherwise    = m2
        where m2 = join mul $ pow m $ div a 2

main = jam $ do
  [n] <- getints
  return $ printf "%03d" (let [[a, b], _] = pow m (n - 1) in
     (a*6 + b*2 - 1) `mod` 1000 :: Integer)

We use a little trick. If f has type a → a → a, then thanks to the Reader monad:

join f x = f x x

Ben Lynn blynn@cs.stanford.edu 💡

2008 Round 1A

Minimum Scalar Product

Milkshakes

Numbers

Contents