The last month was a very busy one, with the ACM ICPC regionals taking place last week. This post is based on a problem on the competition, "Crusher's Code". You can see the full list of problem statements here.

First, a brief explanation of the problem:

Two sort algorithms are given. Both take an input array $A$ of size $n$ as input. Algorithm Monty chooses random numbers $i$ and $j$ with $0 \le i, j < n,$ swapping them if necessary to ensure $i < j$ and then swaps $A[i]$ and $A[j]$ if $A[i] > A[j].$ Algorithm Carlos on the other hand picks a random $i$ with $0 \le i < n -1$ and swaps $A[i]$ and $A[i+1]$ if $A[i] > A[i+1].$ Both algorithms continue until the array is sorted. How many iterations are each expected to run for before terminating?

My solution to this problem started with coming up with a recurrence for the expected number of iterations in each case. For Monty we reduce the problem to a "smaller" problem as soon as we randomly come across a a pair $(i, j)$ that form an inversion of the array. Let's say the set of inversions of $A$ is denoted by $I(A).$ Then choosing a pair $(i, j)$ at random has a total of $n^2$ possibilities, of which exactly $2|I(A)|$ result in an inversion. Hence this can be seen as a Bernoulli process with success rate $p = \frac{2|I(A)|}{n^2}.$ The expected number of trials before a success is therefore simply $\frac{n^2}{2|I(A)|}.$

This gives us the following recursion for the expected number of iterations of Monty:

where by $A_{i,j}$ here I mean the array $A$ with its $i$ and $j$ indices swapped. The $\frac{1}{|I(A)}$ is the probability that any particular inversion is the one that we get to first during the sort.

Following a similar line of thought, for Carlos we can let $I'(A)$ denote the set of indices $i$ such that $A[i] > A[i+1].$ Then we get the following recurrence for the expected number of iterations of Carlos:

Of course, there are a lot of overlaps in the recurrence, so memoizing the values are key to a fast enough algorithm. During the competition I achieved this in Java by first getting the inversion sequence of the array, and the representing the inversion sequence as a base $n$ number, and then using this representation as a key for a hash-table to be used as a cache.

In Python, this can be done much simpler by just hashing with the array itself as the key, converted to a tuple. Here is an implementation in Python for the above algorithm. Note that $I(A)$ and $I'(A)$ are implemented as separate functions and passed to the main driver as parameters. The "cost" functions are also passed as parameters similarly, allowing for a simple driver function to calculate both numbers.

from __future__ import division
from sys import stdin


def expected_iterations(A, cache, candidates, cost):
    n = len(A)
    h = tuple(A)
    if h in cache:
        return cache[h]
    E = 0.0
    C = candidates(A)
    if C:
        for (i, j) in C:
            A[i], A[j] = A[j], A[i]
            E += expected_iterations(A, cache, candidates, cost)
            A[i], A[j] = A[j], A[i]
        E += cost(n)
        E /= len(C)
    cache[h] = E
    return E


def inversions(A):
    return [(i, j)
            for i in xrange(len(A) - 1)
            for j in xrange(i + 1, len(A))
            if A[i] > A[j]]


def adj_inversions(A):
    return [(i, i + 1)
            for i in xrange(len(A) - 1)
            if A[i] > A[i + 1]]


monty_cost = lambda n: n * n / 2.0
carlos_cost = lambda n: n - 1


def process_test_case(A):
    carlos_cache = {}
    monty_cache = {}
    m = expected_iterations(A, monty_cache, inversions, monty_cost)
    c = expected_iterations(A, carlos_cache, adj_inversions, carlos_cost)
    print 'Monty {:.6f} Carlos {:.6f}'.format(m, c)


def main():
    T = int(stdin.readline())
    for __ in xrange(T):
        A = [int(x) for x in stdin.readline().split(' ')]
        # ignore the first element since is is length of the array
        process_test_case(A[1:])


if __name__ == '__main__':
    main()