I don’t recall I actually had much time left for round 2’s problem D “Retiling”. More specifically: I did read all of the statements, but this one fell very accurately in my area of non-expertise; so it’s wasn’t prioritized too high.

We are given two bichromatic grid of squares, and want to find a minimum-cost transition from one to the other. The two available operations are:

1. flip a tile (cost F)
2. exchange two adjacent tiles without flipping them (cost S for “swap”)

By repeatedly exchanging adjacent tiles, we can generalize the operation to “exchange any two tiles for cost S times their Manhattan distance”.

Zooming in a bit, any given tile is either solved or in need of flipping. Whether that flipping is realized with an F or some combination of S operation is what we have to determine.

The S operation preserves the color distribution, so if it has to be changed, flips are unavoidable.

For any unsolved tile, we have to choose between flipping it directly, or finding a close-by compatible tile to exchange it with. What’s a compatible tile? One that also needs flipping, but in the other direction.

So we can partition all unsolved tiles by wanted flip direction, and seek a minimal-cost matching between the both. Both sets necessarily have the same cardinality, so we can complete the smaller one with a few “just flip” counterparts.

Actually, if flips are cheap and exchanges expensive, there’s no saying we want to match at all costs. So we either add “just flip” counterparts to both sets, or play on the cost function to decide on its own whether a long exchange or a double flip is preferable. It’s a constant-time decision per pair, it’s affordable.

The matching can be performed with our old friend the hungarian algorithm. Complexity is fuzzy, somewhere between O(N³) and O(N⁴) according to wikipedia.¹ Input size happens to be at most 100, so it should be ok.

Let’s implement.

main :: IO ()
main = do
  t <- readLn :: IO Int
  forM_ [1..t] $ \i -> do
    [r,_c,f,s] <- map read . words <$> getLine
    src <- replicateM r getLine
    dst <- replicateM r getLine
    putStrLn $ "Case #" ++ show i ++ ": " ++ show (solve f s src dst)

The main wrapper is nothing too interesting, just read the input, convert the integers and delegate the meat to the solve function.

solve :: Int -> Int -> [String] -> [String] -> Int
solve f s src dst = cost
  where

The solve workhorse is a bit of a wrapper itself. First we’ll identify the tiling positions that need some change.

    delta :: [[Bool]]
    delta = (zipWith . zipWith) (/=) src dst

Next we’ll partition into those who start as a G and those who start as an M. The pipeline is a bit more convoluted than I’d like because it takes care of assigning coordinates on-the-fly

    gs,ms :: Set (Int,Int)
    (gs,ms) = bimap (Set.fromList . map fst) (Set.fromList . map fst) $
              partition ((== 'G') . snd) $ concat $
              zipWith3 (\i srcRow dstRow ->
                          mapMaybe (\(j,se,de) -> ((i,j),se) <$ guard de)
                            (zip3 [0..] srcRow dstRow))
                [0..] src delta

Then construct a cost map of pairs from them and hand it to the hungarian algorithm. To ensure every tile has a counterpart without too many ifs no matter how they distribute initially, I’m simply offering a “deactivated” version: the cost function will recognize two “active” opposite tiles and pair them if it makes sense, ignore two “inactive” opposite tiles, and consider an active-inactive match as an unconditional flip.

    (cost,_) = munkresI (Set.disjointUnion ms gs) (Set.disjointUnion gs ms) $
               curry $ \ case (Right g,Right m) -> min (dist g m * s) (2*f)
                              (Left _,Left _) -> 0
                              _ -> f

I’m skipping the hungarian algorithm itself, because in its current version it’s quite long, and will actually warrant a post of its own.

So there we have it. A solution to that remaining problem from round 2. It’s there with the others in the usual place on GitHub. See you soon for the round recap!