Because Covid, the Infinite House of Pancakes seems closed for business this year, so instead of pancake sorting we get reversorting, which is basically the same thing from another angle.

So how does Reversort work? Allow me to paraphrase the pseudocode:

    Reversort(L):
      for i := 1 to length(L) - 1
        j := argmin L[i..length(L)]
        Reverse(L[i..j])

How artificially iterative. Let’s reword for recursion:

As long as the section of the list under scrutiny is not known to be sorted, locate the minimum element and bring it to the front by reversal; then sort the rest of the list.

“Known to be sorted” is code for “of length 1 or less”. It’s really important to note that this specific reversal is never performed. The algorithm would work all the same if we did, and with an simpler definition too. But no.

It’s trivial to prove this it is indeed a sorting algorithm. It’s unstable, but that doesn’t matter because we’ll only ever be handling permutations of [1..N].

From this algorithm we define an algorithm cost—the number of items that undergo reversal (this is why it was important to note we’re not reversing 1-lists)—and two problems for the qualifier round:

• problem A performs the algorithm: it gives us a list and asks for the cost.
• problem C reverses¹ the algorithm: it gives us a cost and asks for the list.

What order of magnitude can that cost value take?

The smallest it can be is when all reversals are as small as possible: one element. This happens whenever the smallest sought element is first of its sublist. In other words², if the list is already sorted. The total cost in that case is \(N-1\).

The largest it can be, since the number of iterations is predetermined, is when all reversals are as large as possible. On the first iteration, that’s \(N\) elements, which happens when the smallest element is at the end. On the second iteration, that’s \(N-1\), which happens when the smallest remaining element is at the end of the remaining (reversed) list, which tranlates to the beginning of the initial list. Subsequent iterations reverse \(N-k\) elements, until the last two, which reverse \(2\) elements then \(0\) elements. The total cost in that case is:

\[ \sum_{i=1}^{N-1} (N-i+1) = \sum_{L=2}^{N} L = {(N-1) (N+2) \over 2} \]

How is this useful? Well, the problem statement gives a handful set of constraints: there are 100 tests or fewer, and the lists are 100 elements or shorter.

So assuming a linear reversal, solving problem A using a straightforward transcription of the algorithm would perform in \(O(TN^2)\) which is perfectly reasonable to have done in ten seconds.

The marginally tricky³ part of implementing it in Haskell is to locate the sublist minimum in a single pass. I did it like this:

-- | Extract a (minimum,sublist before,sublist after) triplet from a list.
minSplit :: [Int] -> Maybe (Int,[Int],[Int])
minSplit [] = Nothing
minSplit (x:t)
  | Just (m,h',t') <- minSplit t, m < x = Just (m,x:h',t')
  | otherwise                           = Just (x,[],t)

In plain English: an empty list has no minimum; else the result depends on how the list’s head compares to the list’s tail’s minimum. If the tail’s minimum “wins”, the result triplet is that minimum and the same post-minimum sublist, and the current item prepended to the sublist’s pre-minimum sublist. If the list’s head is a better minimum, we return it with an empty known prefix and the tail as a suffix.

Now we can implement the algorithm almost as specified:

-- | Reversort a list of ints.
reversort :: [Int] -> Writer (Sum Int) [Int]
reversort xs = case minSplit xs of
  Just (m,h,t) -> do
    tell (Sum (1 + length h))
    (m :) <$> reversort (reverse h ++ t)
  Nothing -> pure xs

I’m instrumenting with a Writer monad to count the reversal lengths without disrupting the algorithm flow. So problem A can be solved with a simple getSum . execWriter . reversort invocation.

Now for problem C. We’re given a cost, and are tasked with generating a permutation of [1..N] that would match costs when reversorted. I’ll call that a (controlled) revershuffle operation. It takes a sorted list and shuffles it, striving to consume an exact reversal budget.

    Revershuffle(N,C) returns L:
      let L = [1..N]
      for i := N-1 downto 1
        { invariant: L[i] = N }
        let P = some_amount_to_be_determined
        Reverse(L[i..i+P-1])

Each reversal is intended to have cost P.⁴ So the total cost is going to be the sum of each step’s costs. Can we pick a distribution of them that sums to C while remaining compatible with the array bounds?

At each step, P has to be 1 or more, since that was the case for reversort: all reversals necessarily reversed at least one element. At step \(i\) (remember they count down), we’re bounded by the end of the list, so \(i+P-1\) cannot be greater than N, so \(P \le N-i+1\).

As discussed above, a list of N elements necessarily reverses \(N-1\) or more elements, so we can trivially dismiss those cases as impossible. We can also virtually discount them from our budget: this way we won’t have to worry too much about keeping enough budget to be able to complete the algorithm. Remove \(N-1\) first, then count all reversals as consuming as much budget as the sublist’s length without counting the minimum.

Transcribing that back to P constraints, we’ll have \(0 \le P \le N-i\).

The remaining problem is merely to consume enough of the remaining budget before reaching the end. That’s a rather easy problem to solve: we can simply greedily consume as much as is available per step, until the algorithm completes. This will make for an easy check of success: the remaining budget has fallen to zero. We won’t even need to ensure our earlier computation of maximum cost is correct.

-- | Shuffle [1..n] for an exact cost of c, if possible.
revershuffle :: Int -> Int -> Maybe [Int]
revershuffle n c = go (n - 1) [n] (c - n + 1) where
  go _ _ b | b < 0 = mzero
  go 0 l b = guard (b == 0) *> pure l
  go i l b =
    let p = min (n - i) b
        (before,after) = splitAt p l
    in go (i - 1) (reverse (i : before) ++ after) (b - p)

It’s expressed recursively, so it reads a bit different to the pseudocode, but it really works the same. The go helper takes and maintains the same i and L parameters, and an additional B one for the remaining budget. The recursion starts with \(i=N-1\) and ends when \(i=0\), either with a successfully revershuffled list, or in error if the whole budget wasn’t consumed. The other error case is overspending the budget.⁵

This concludes the qualifier’s problems A and C solutions. The complete code with I/O handling is on my github.

See you soon for problem B!

Post-scriptum: the round editorial mentions that

I beg to differ. I did the bounds analysis and agree it qualifies as math, but implementing the common sense algorithm doesn’t. The upper bound doesn’t need to be pre-checked for feasibility: it’s enough to iterate, pass it, and recognize the failure.