Round 1B’s problem B, “Subtransmutation”, puts us in the alchemist role once again. This time we’re to find the least mineral such that we can transmute it to a given distribution of other minerals, using repeated application of a simple spell.

For any \(N\), said spell takes a unit of mineral \(N\) and splits it into a unit of two lesser minerals, \(N-A\) and \(N-B\). \(A\) and \(B\) are constant per test set, and notably do not depend on the mineral being transmuted.

The easy test set uses \(A=1\) and \(B=2\). In this restricted case, it’s easy to see solving the problem is always possible: with enough units of mineral \(N\), we’re able to produce as many units of mineral \(N-1\), or the double units of mineral \(N-2\). Coarsely speaking, minerals “grow” at a geometric rate greater than \(\sqrt 2\) per mineral rank.

There may be a clever way to construct the least mineral that works bottom-up from the given distribution. But with that geometric sequence, we’re confident it won’t need to go very high, so we can just search for it, linearly.

This entails implementing a verification function: “can I produce the distribution from this starting mineral?”

A greedy algorithm appears to do the trick: starting with a stock of one, repeatedly transmute the highest ranking element, reserving the amount needed when such ranks are passed.

• It’s never a bad idea to be transmuting a mineral higher than the distribution’s highest: there is literally no other use for it.
• With no reserving, no mineral will be missed, all of them from the starting one down to mineral 1 will be “hit”.
• Starting high enough, we can establish a lower bound of how many units we want to have at any rank thanks to the geometric progression.

So it’s solved, conceptually. The most mineral we can ever need is 20 units of each mineral from 1 to 20. \(20×20=400\) units of mineral 20 only are (more than) enough to cover that. 1 unit of mineral \(20+\left\lceil\log_\sqrt 2 400\right\rceil+1 = 39\) covers that.

Really, a quadratic algorithm—linear search with a linear test—on that order of magnitude for a worst case is Very Safe.

Now to the more general case, when \(A\) and \(B\) are free. We have two hurdles:

1. Can we still hit every number in the distribution?
2. Does the linear approach still work?

It’s kind of obvious it can’t always work. Either by spotting the “IMPOSSIBLE” case in the additional sample output, or by just considering (2,4), who fit the requirements, yet only ever cover numbers that share parity with the starting mineral.

Formally, we can reach any number that can be expressed as \(x - \lambda A - \mu B\), for \(\lambda\) and \(\mu\) positive.¹ This looks a lot like Bézout’s identity, doesn’t it?

\[\forall (a,b)\in\mathbb N^2,\quad\exists(\lambda,\mu)\in\mathbb Z^2,\quad\lambda a + \mu b = a \wedge b\]

The key difference is that alchemy coefficients must be positive, whereas Bézout’s don’t care. The other is that we’re counting down from the starting mineral, instead of up from zero. Can we still get any number from 1 to 20?

We can easily get any multiple of the GCD (still as a difference from the starting mineral), by simply multiplying the entire equation. But that won’t help if one of the coefficients is negative.²

By adding or removing \(ab\over{a\wedge b}\) to both terms, we can fudge the coefficients around until the negative one, say \(\lambda\), is at a distance to zero no more than \(\left|{b\over{a\wedge b}}\right|\). But then by summing \(ab\) to some integer times the GCD, we can get positive coefficients. This works for an integer between 0 and \(b\over{a\wedge b}\). But that upper bound is itself a multiple of \(a\), so we can start over. So above a certain thresholh, every multiple of the GCD can be obtained with positive cefficients.

Are numbers other than multiples of the GCD reachable? Bézout’s theorem is more directly applicable here: no, an integer linear combination of A and B, of which a positive linear combination is a strict subset, is necessarily a multiple of the GCD.

Back to counting down from minerals, this translates as “the distance between any needed mineral and the starting one is a multiple of the GCD.” They’re still obviously of lower rank.

That’s a great step towards a solvability test, but there’s still the small part of proving abundance of minerals. Some form of the geometric argument used for (1,2) probably still applies, but I’m too tired to expand it here. Let’s say it’s left as an exercice to the reader!³

The biggest “stride” we can encounter is the maximum GCD we can have between any integers between 1 and 20, so exactly 20 (between 1 and 20). A quadratic algorithm is still safe.

We can implement at peace.

The core of the matter is the test—the function that verifies a given starting mineral covers a given distribution.

valid :: Int -> Int -> IntMap Int -> Int -> Bool
valid a b us n = go us (IMap.singleton n 1) where
  go n s
    | IMap.null n = True      -- no metal need → success
    | IMap.null s = False     -- no metal in stock → failure
    | w < nmax    = False     -- heaviest needed is heavier than stock → failure
    | w > nmax    = go n s''  -- heaviest stock isn't needed → transmute it
    | nw < unmax  = False     -- not enough heaviest metal produced → failure
    | otherwise   = go n' s'' -- reserve and transmute
    where
      (nmax,unmax) = IMap.findMax n            -- heaviest needed metal
      Just ((w,nw),s') = IMap.maxViewWithKey s -- heaviest in stock
      cons | w == nmax = min nw unmax          -- consumed quantity
           | otherwise = 0
      -- quantities after consumption and transmutation
      s'' = IMap.unionWith (+) s' $
            IMap.fromList [ (c,nw-cons) | c <- [w-a,w-b], c > 0 ]
      -- needed quantities after consumption
      n' = IMap.delete nmax n

It’s a bit of a mouthful⁴ so here’s a reading guide:

• The core of the algorithm is the two transmuting lines that recurse.
• The rest is essentially “ensuring the variables are well-defined and meaningful before they are used”. That’s the part that would be rewritten for a longer-lived application.
• N for needed, S for stock, W for, err… “most Weightful”.

The general solver follows directly:

solve :: Int -> Int -> [Int] -> Maybe Int
solve a b us = guard (all ((== 0) . (`mod` gcd a b)) δs) *>
               find (valid a b us') [0..]
  where δs = map =<< subtract . head $ IMap.keys us'
        us' = IMap.filter (> 0) $ IMap.fromList $ zip [1..] us

It could be optimized to only seek on multiples of the GCD, but… why bother?

The protocol wrapper for completion:

main :: IO ()
main = do
  t <- readLn
  forM_ [1..t] $ \i -> do
    [_n,a,b] <- map read . words <$> getLine
    us <- map read . words <$> getLine
    putStrLn $ "Case #" ++ show i ++ ": " ++
      maybe "IMPOSSIBLE" show (solve a b us)

This concludes this puzzle’s solution. The full code is on GitHub. See you soon with this round’s final problem!