In round 2’s problem B “Matrygons”, we want to nest regular polygons within each other so that they all have all of their vertices on the same circle without crossing lines.

The puzzle gives a number of edges \(N\) and asks how many polygons we can squeeze in this way such that the sum of their number of edges is \(N\).

Very artificial.

Two regular polygons that nest within the same circle necessarily have a number of edges one a multiple of the other. The minimum number of edges to form a polygon is \(3\). So we are searching for the longest possible sequence of integers \(f_1, f_2 \ldots f_k\) such that:

\[ \begin{cases} f_1\ge 3 \\ \forall i>1, f_i\ge 2 \\ \sum_{k=1}^n \prod_{i=1}^k f_i=N \end{cases} \]

Solving for a given \(N\) is rather inconvenient. On the other hand, computing all of them once for later querying isn’t too complex. The process is very similar to array-based Eratosthenes sieving, though the complexity is a bit more since we can’t skip composites anymore. I find \(O(N \log N)\).

-- | Compute a solution look-up table up to N.
solve :: Int -> UArray Int Int
solve hi = runSTUArray $ do
  ns <- newArray (1,hi) 0
  let go sides polygons s = do
        let sides' = sides+s
            polygons' = polygons+1
        when (sides' <= hi) $ do
          n <- readArray ns sides'
          let n' = max polygons' n
          writeArray ns sides' n'
          mapM_ (go sides' polygons') [2*s,3*s..hi-sides']
  mapM_ (go 0 0) [3..hi]
  pure ns

The go helper recursively computes the matrygon settings for a given inner content, summarized as an (outer polygon edge count, polygon count) pair.

The wrapper follows. It takes advantage of lazyness to have the same program able to answer on both test set sizes.

main :: IO ()
main = do
  t <- readLn :: IO Int
  let cacheSmall = solve 1000
      cacheLarge = solve 1000000
  forM_ [1..t] $ \i -> do
    n <- readLn
    let cache | n <= 1000 = cacheSmall
              | otherwise = cacheLarge
    putStrLn $ "Case #" ++ show i ++ ": " ++ show (cache ! n)

This concludes today’s problem. The same code is on GitHub as per usual. See you soon!