Challenge24 2014 writeups

Preliminary Electronic contest - R. Seating order

Task design background

Motivation

We needed a simple task with 8 bit gray scale PNG input and competitive scoring (we used to call this scaled). Another important aspect was to expose the 10 megabyte submission upload limit.

Our solution

Probably the simplest possible solution is to implement a bubble-sort like algorithm on a per line basis, writing one swap per line on the output. While this won't optimize for the number of swaps, it'd at least solve most of the inputs. The format starts to be problematic at input 9 and 10, because of the 10 megabyte submission upload limit. There are trivial ways to reduce file size without any change in the actual swaps: putting more swaps in the same sequence, solving multiple lines by a single sequence, etc.

More complex, and potentially better solvers would also rely on vertical swaps.

In reality...

It turns out that our made-up supposed-to-be-funny background story is not that irrelevant: a theater in Italy is implementing and testing a system for solving the same problem (in a different way).