For inputs and outputs see the 2012 archive.
The problem was about finding the size of the maximum independent vertex set (invited ponies) of a forest (simple graph without cycles).
This problem is NP-hard in general graphs, but in a forest a single depth first search is enough (it's a simple example of dynamic programming).
During the traversal the maximum independent set size is calculated
for the subgraph below the currently visited vertex.
Two cases are considered: the current vertex is in the max independent
set of the subgraph (max size is yes[vertex]) or not
(max size is no[vertex]).
The result is the sum of max(yes[root], no[root])
for each root vertex.
The dfs with pseudo code:
function visit(i): yes[i] = 1 no[i] = 0 for j in non-visited neighbors of i visit(j) yes[i] += no[j] no[i] += max(yes[j], no[j])
Soundplot was a simple signalprocessing problem.
The signal of both channels is a sine wave with varying frequency, so at a given time the frequency can be determined by counting samples between zero crossings (or peeks).
To make the image readable subsample precision is needed which can be achieved by averaging consecutive wave periods. (So the sequence of the period counts should be run through a moving average filter).
In other words: in a wav encoded at 44100 Hz sampling rate, having a sine wave with 4410 Hz period will have a glitch-free representation. Because of integer representation of the sampling rate, 4300 Hz will not have the same clean representation. Using moving average, if the input signal was shifting from one glitch-free frequency to another, in-between frequencies could be estimated. An alternative way would be to measure the total wave length of multiple waves to decrease the per wave error - but this is just another wording for moving average at the end.
This task could be solved with analog electronics. There are cheap frequency-to-voltage converters widely available. Interfacing them to the output of a sound card should be easy with an opamp. The output of the converter could be scaled with further opamps and the result fed to an analog scope set to X-Y mode. We are not aware of anyone solving the problem this or similar way.
Squares was an optimization problem where various heuristics could be used.
An interesting approach is to allow only 1 pixel wide lines instead of rectangles. For this modified problem the optimal solution can be obtained.
For each black pixel calculate the longest vertical and horizontal line going through it. Then an optimal cover of the black pixels is the minimum vertex cover of the bipartite graph in which the black pixels are the edges connecting the horizontal and vertical lines. This solution uses at most 4 times more lines than the best solution using rectangles and can be calculated efficiently (using a bipartite matching algorithm).