Round 2’s problem B, “Minimum Sort”, is yet another twist on this year’s theme: sorting integers in convoluted ways.

In this instalment, we have two operations:

• swapping two elements, for free
• locating the minimum element of a contiguous range, for a cost inversely proportional to the range length.

I’ll be honest. I could only think of one natural way to sort using those two operations: selection sort. But that’s way too easy for a round 2 problem, isn’t it? So let’s rule it out using math.

Selection sort works like this:

1. Identify the smallest element.
2. Move it to the front.
3. Recursively sort the elements after the front one.

So if \(L\) is the sequence’s length, the minimum operation is carried out for a cost of \(10^8\over L\). A free swap will bring it into place, then we repeat for the remaining \(L-1\)-element long sequence. It will take at most N iterations, so the total cost will be:

\[ \sum_{L=1}^N{10^8\over L} \le \left\lceil10^8 ln N\right\rceil \approx 4,6×10^8 \]

Unfortunately, we’re only allowed \(6×10^8\) coins, so we’re going to have to refine a bit.

Wait, what?

We’ve got enough coins. It’ll pass.

import Control.Monad
import System.Exit
import System.IO

main :: IO ()
main = do
  hSetBuffering stdout LineBuffering
  [t,n] <- map read . words <$> getLine
  replicateM_ t $ do
    forM_ [1..n-1] $ \i -> do
      send $ "M " ++ show i ++ " " ++ show n
      m <- get
      when (m > i) $ do
        send $ "S " ++ show i ++ " " ++ show m
        1 <- get
        pure ()
    send "D"
    1 <- get
    pure ()

send :: String -> IO ()
send = putStrLn

get :: IO Int
get = do
  n <- readLn
  when (n < 0) exitSuccess
  pure n

That was easy. Too easy. More on that later.

The full code is above, but it’s also on my GitHub if really you like the syntax highlighting there better for some reason.

See you soon for problem B!