2014 Round 1B

The Repeater

The obvious approach works on both inputs:

Run-length encode every string.
For this step, we ignore run-lengths and focus on the sequences of characters. If any of the sequences differ from the first, then Fegla won.
Now we focus only on the run-lengths. For each set of run-lengths, use brute force to find the optimal number of characters to minimize insertions and deletions (the least average distance).

import Jam
import Data.List

rle []     = []
rle (x:xs) = (x, length a) : rle b where (a, b) = span (== x) xs

lad xs = minimum [sum (map (abs . (-) x) xs) | x <- [minimum xs..maximum xs]]

main = jam $ do
  [n] <- getints
  aas@(a:as) <- map rle <$> getsn n
  return $ if all ((map fst a ==) . map fst) as
    then show . sum . map lad . transpose $ map (map snd) aas
    else "Fegla Won"

New Lottery Game

Brute force works on the small input:

import Jam
import Data.Bits

main = jam $ do
  [a, b, k] <- map (subtract 1) <$> getints
  return $ show $ length [undefined | i <- [0..a], j <- [0..b], i .&. j <= k]

How about the large input? Well, comparing numbers on a computer works by comparing the most significant bit and working our way down to the least significant bit. Coupled with the bitwise-AND nature of the lottery, this strongly suggests the right approach is recursing from the most signifcant bit to the least significant.

Thus our first step is to replace the input numbers with lists of 1s and 0s. The lists have the same length, and are long enough to fit the biggest number.

To get our bearings, we’ll consider a simplified version of the problem. Suppose K is an N-bit number, and A and B are simply randomly generated N-bit numbers. In other words suppose A = B = 2^N.

Let g be our recursive function on the bits of K. The base case is [], in which case we return 1: there is one way to do nothing.

Otherwise g gets a list of bits (k:ks). If k == 0 then we win the lottery if at least one of the machines generates a 0 for the corresponding bit and the rest of the generated bits AND to a number that is at most the number represented by the bits ks. There are three ways at least one machine can generate a 0 for this bit ([(0, 0), (0, 1), (1, 0)]), thus we return 3 * g ks.

If k == 1, then if both machines generate 1 for the corresponding bit then, again, we win if the rest of the generated bits AND to a number less than ks. Otherwise, at least one of the machines generated 0 for this bit, and we’re guaranteed to win the lottery no matter what either generates for the remainder of the bits. Thus we return the sum g ks + 3 * 4^length ks.

g [] = 1
g (0:ks) = 3 * g ks
g (1:ks) = 3 * 4^length ks + g ks

Let’s now attack the full problem. We’ll call our recursive function f. We’re given lists of bits of A, B, and K. The base case is [] [] [], for which we return 1.

Otherwise the inputs are (a:as) (b:bs) (k:ks). Without loss of generality, a ⇐ b, that is, if this condition fails to hold we recurse with the first two inputs swapped around so we have fewer cases to think about.

Suppose k == 0:

If (a, b) == (0, 0), then both machines must generate 0 for this bit so we simply return f as bs ks.
If (a, b) == (0, 1), then:
- we could win if the machines generate (0, 1) for bits (a, b) (as before, there are f as bs ks` ways of this happening)
- we could also win if the new machine generates 0 for bit b, in which case it may generate 0 or 1 for all its remaining bits: because it has chosen 0 for the most-significant bit when b == 1, whatever ever it chooses will result in a integer less than B. Thus for this second term we return f as (ones bs) ks, where ones is a function that replaces all elements of a list with 1 (map (const 1)); a limit of all 1s means that we allow any selection of bits.
Otherwise we must have (a, b) == (1, 1). Since k == 0, we cannot win if the machines generate 1 for both a and b. At least one of the machines must generate 0 for this bit. Then following similar reasoning to the previous case yields a sum of three terms.

Now suppose k == 1:

If a == 0, then we’re guaranteed a win, so the answer is simply v as * v (b:bs), where v returns the ways we can pick a number from 0 to the number represented by a given list of bits, namely, the number represented by the list of bits plus one.
The only remaining case is (a, b) == (1, 1), where anything goes, so to speak:
- If both machines generate 0 for this bit, then we’re guaranteed to win, and there are 2^length as * 2^length bs choices (since the lengths of the lists are the same, this is simply 4^length bs).
- If exactly one of the machines generates 0 for this bit, then again we’re guaranteed to win. The machine that generated 0 can choose any bit it pleases for its remaining bits, which is 2^length bs, while the other machine has v as choices.
- The remaining case is that both machines generate 1 for this bit. Then the answer is f as bs ks, as before.

import Jam
import Data.List

main = jam $ do
  [a, b, k] <- bitlists [[], [], []] . map (+(-1)) <$> getints
  return $ show $ f a b k

-- Converts three numbers to three lists of bits. The lists have the same size.
bitlists acc [0, 0, 0] = acc
bitlists acc abk = let
  dms = map (`divMod` 2) abk
  in bitlists (zipWith (:) (map snd dms) acc) (map fst dms)

-- Converts a list of bits to a number and adds one.
v = (1+) . foldl' (\a b -> 2*a + b) 0

ones = map (const 1)

f [] [] [] = 1
f (a:as) (b:bs) (k:ks)
  | a > b  = f (b:bs) (a:as) (k:ks)
  | k == 0 = case (a, b) of
    (0, 0) -> f as bs ks
    (0, 1) -> f as bs ks + f as (ones bs) ks
    (1, 1) -> f (ones as) (ones bs) ks + f (ones as) bs ks + f as (ones bs) ks
  | a == 0 = v as * v (b:bs)
  | True   = 4^length bs + 2^length bs * (v as + v bs) + f as bs ks

This program solves the large input quickly.

an efficient solution

Our program should actually fail, because it’s slow on inputs like 2²⁹ 2²⁹ 1. One of the cases spawns three recursive calls, meaning we’ll need about 3^N calls for suitably picked N-bit numbers. It seems the large input misses this case, perhaps because it is randomly generated.

If we truly want to solve the problem, we should be able to handle all inputs of the given sizes. We do this by writing specialized functions for when one or both of the first two inputs are all 1s. The latter case is exactly the simplified version of the problem we considered earlier that we solved with the function g:

import Jam
import Data.List

main = jam $ do
  [a, b, k] <- bitlists [[], [], []] . map (+(-1)) <$> getints
  return $ show $ f a b k

-- Converts three numbers to three lists of bits. The lists have the same size.
bitlists acc [0, 0, 0] = acc
bitlists acc abk = let
  dms = map (`divMod` 2) abk
  in bitlists (zipWith (:) (map snd dms) acc) (map fst dms)

-- Converts a list of bits to a number and adds one.
v = (1+) . foldl' (\a b -> 2*a + b) 0
f [] [] [] = 1
f (a:as) (b:bs) (k:ks)
  | a > b  = f (b:bs) (a:as) (k:ks)
  | k == 0 = case (a, b) of
    (0, 0) -> f as bs ks
    (0, 1) -> f as bs ks + f1 as ks
    (1, 1) -> g ks + f1 bs ks + f1 as ks
  | a == 0 = v as * v (b:bs)
  | True   = 4^length bs + 2^length bs * (v as + v bs) + f as bs ks

f1 [] [] = 1
f1 (a:as) (k:ks) = case (a, k) of
  (0, 0) -> 2 * f1 as ks
  (1, 0) -> 2 * g ks + f1 as ks
  (0, 1) -> v as * 2^(length as + 1)
  (1, 1) -> 2 * 4^length as + v as * 2^length as + f1 as ks

g [] = 1
g (0:ks) = 3 * g ks
g (1:ks) = 3 * 4^length ks + g ks

The Bored Traveling Salesman

Brute force dispatches the small input. For all permutations of the cities that are valid travel routes, concatenate the ZIP codes into a string. Then print the minimum such string.

There’s a small complication: does the sequence ABC mean we traveled from A to B, then to C? Or does it mean we traveled from A to B and back again before traveling to C? We see if the former is possible, then so is the latter, and in fact, the only difference is that in the latter case, we have given up our right to travel out of the city B (because we have used up the return ticket from B).

Thus in our search, we only consider the former possiblity, that is, we never take a return flight unless we must.

import Jam
import Data.List

main = jam $ do
  [n, m] <- getints
  zs <- getsn n
  es <- getintsn m
  let
    Just best = find (isPath . map (+1)) $ sortBy (comparing $
      concatMap (zs!!)) $ permutations [0..n-1]
    isPath (c:cs) = f [c] cs
    f _ [] = True
    f live (c:cs) = case break (isEdge c) live of
      (_, []) -> False
      (_, xs) -> f (c:xs) cs
    isEdge i j = elem [i, j] $ es ++ map reverse es
  return $ concatMap (zs!!) best

The large input is substantially trickier. We must have to apply a graph algorithm of some kind, but which one?

The title of the problem might suggest using a well-known dynamic programming trick for tackling the Traveling Salesman Problem, but this has a factor of 2^N in its running time, and in the large input, we might have N = 50.

On closer inspection, we see the problem is asking us to find a certain spanning tree of the graph: the starting city is the root, each outbound flight is a link from a parent to child, and the entire trip describes an in-order traversal of the tree.

The spanning tree we desire is minimum in some sense, so we might look up the Minimum Spanning Tree problem. Alas, in this well-studied problem, it’s the edges that are weighted. In contrast, this problem wants the lexicographically smallest concatenation of node labels.

However, reading up on the Minimum Spanning Tree problem is still fruitful. We learn that it can be solved with a simple greedy algorithm, which inspires us to design a greedy algorithm for this problem.

Sucessively adding nodes from start to finish feels like the right strategy. Choosing the start node is easy: it must be the city with smallest ZIP code. In general, the eariler the city in our trip, the more significant its ZIP code.

Suppose we have started our journey and we are so far on track to achieving the minimum concatenated ZIP code. If we have visited all the cities, then we are done. Otherwise let dead be the cities we have already taken return flights from, and live = a[0], a[1], …, a[k] be the sequence of cities that starts from the root location a[0] and ends at our current location a[k]; for each city in this sequence except the root, we have return tickets going to the predecessor city.

Then we find all cities x such that:

We have not visited x yet, namely, x is neither a member of live nor dead.
The city x can be reached by a direct flight from some city a[i] in live (thus we can travel to x by taking return flights until we are in a[i], then take a flight to x).
We can reach every unvisited city by taking some number of flights from x or one of the cities a[0], a[1], …, a[i].

Our next destination is the city satisfying the above conditions with the lowest ZIP code. On the one hand, our next city must satisfy the above conditions for it to be the next city, and for us to be able to complete our journey. On the other hand, among all such cities,

We apply the same principle from the small input case: if it is possible to fly to x from more than one city in live, we choose a[i] so that i is large as possible.

import Jam
import Data.List
import Data.Ord

main = jam $ do
  [n, m] <- getints
  zs <- getsn n
  es <- getintsn m
  let
    nbrs i = [x + y - i | [x, y] <- es, y == i || x == i]
    getz i = zs!!(i - 1)
    start = minimumBy (comparing snd) $ zip [1..] zs
    f acc dead live
      | length dead + length live == n = acc
      | otherwise = f (acc ++ getz b) dead1 live1 where
        Just (dead1, live1@(b:_)) = g dead live
    g dead [] = Nothing
    g dead (a:as) = let
      y = g (a:dead) as
      ns = (nbrs a \\ dead) \\ as
      bs = [n | n <- ns, reachAll dead (n:a:as) []]
      b = minimumBy (comparing getz) bs
      x = if null bs then Nothing else Just (dead, b:a:as)
      in case (x, y) of
        (Nothing, y) -> y
        (x, Nothing) -> x
        (Just (_, a:_), Just (_, b:_)) -> if getz b < getz a then y else x
    reachAll dead []     visited = length dead + length visited == n
    reachAll dead (x:xs) visited =
      reachAll dead ((((nbrs x \\ dead) \\ xs) \\ visited) ++ xs) (x:visited)
  return $ f (snd start) [] [fst start]

Because we’re using lists, we represent the live sequence backwards: it’s easier to prepend than eppend elements to Haskell lists.

Our function for returning all neighbours of a given node is inefficient, but the program still solves the large input under two minutes.

Ben Lynn blynn@cs.stanford.edu 💡

2014 Round 1B

The Repeater

New Lottery Game

an efficient solution

The Bored Traveling Salesman

Contents