Round 1C’s problem B, “Roaring Years”, has a strong similarity with Append Sort we solved a few days ago: we are to repeatedly find the smallest number that satisfies some property. In Append Sort, the property was that a prefix of it was given. Here in Roaring Years, the property is that the number has to be “roaring”: composed by concatenating a nontrivial ascending sequence of consecutive integers.

The small test case asks for numbers over no more than a million, so we can just construct all possible roaring numbers surpassing that and search in there. As a building block, let’s first construct all roaring numbers from a given starting point:

roarFrom :: Int -> [Int]
roarFrom n =
    map fromIntegral $
    takeWhile (<= 1234567891011121314) $
    drop 2 $
    scanl append 0 [fromIntegral n..]
  where
    append a k = a * decimalWidth k + k :: Integer
    decimalWidth k = head $ filter (k <) $ iterate (* 10) 1

I’m stopping at 1234567891011121314 because it’s roaring and greater than 10¹⁸, so we’d never need to seek above it even for the large test set. I’m still operating on bigints because I still have to test going over the limit and I don’t want to have to special-case overflow detection.

brute :: Int -> Int
brute =
  let cache = S.fromList (concatMap roarFrom [1..999])
  in \i -> fromMaybe (error "Not found")
           (S.lookupGT (fromIntegral i) cache)

I’m stopping at 999 because 9991000 is (much) greater than the smallest roaring over a million.

What’s interesting about this cache is its size. It’s at 5292 for a cache that guarantees all request sizes up to a million, and wastefully include numbers much higher because my roarFrom function is forward-compatible and generates numbers up to above 10¹⁸.

The roaring numbers are sparse.

It still would be too long to generate them all: we’d need all starting positions up to half of 10¹⁸’s width, which is a lot already.

Trying from the ground up, what’s a likely roaring number over a given base?

My first instinct was to try all prefixes of that number for roaring numbers. For example, for 123000, we’d try 1, yielding 123456, 12 yielding 121314 and 123 yielding 123124, 1230 yielding 12301231, 12300 yielding 12300123001 and 123000 yielding 123000123001. Then we’d select the one induced from 123 as a winner.

But this fails for 123457: the best we’d find there is 12341235, when there’s a much better answer in 124125. We can fix this by trying each prefix’s successor in addition to itself.

And then it fails on trivial cases such as any number d in the 2–9 range, where it’d find (d|d+1) as a smallest bound, whereas 12 would be a more appropriate answer. We could hard-code 12 as a number to always check against, but we’d miss the general case: any roaring number based on 10ⁱ is to check. (Try mentally searching for the smallest roaring over 89, 910 or 9899, for example.) That’s still a very finite amount of specific numbers to check, so we’d manage.

And then there’s the weirder cases, like the smallest roaring number over 50000. It happens to be 78910: it’s got nothing in common with a prefix of 50000. But… it does have something with the 10ⁱ series: it’s a roaring number that does contain one of its members. That would entail yet more numbers to check, but still very tractable.

specials :: [Int]
specials = 
  concatMap roarFrom [ max 1 (10^i-k) | i <- [1..18 :: Int], k <- [0..18] ]

There are 622 of them.

fine :: Int -> Int
fine y = minimum (filter (> y)
                   (concatMap roarFrom (concatMap approx (tail (inits (show y))))
                     ++ specials))
  where
    approx s = let n = read s in [n,n+1]

And… this passes.

I’m sorry I don’t have a fuller strict mathematical proof here, but I’m late on schedule and it wasn’t my round. I’ve taken a peek at the analysis since writing this, and they go for much¹ more complicated approaches, so my approach may be wrong; yet it’s uncaught by the test cases.

Here’s a main wrapper to compensate:

main :: IO ()
main = do
  t <- readLn :: IO Int
  forM_ [1..t] $ \i -> do
    y <- readLn
    let solve | y <= 1000000 = brute
              | otherwise   = fine
    putStrLn $ "Case #" ++ show i ++ ": " ++ show (solve y)

This concludes today’s problem. Full code is on github. This problem, by the way, is one of those who do not have a Haskell solution on the contest’s site, so… yay, a net positive contribution to the world!