2011 EC Solutions

Outputs are available in the 2011 archives.

A. Equilateral

task description

Trying every possible connection of the rods is exponential, so bruteforcing every input cannot solve the problem.

With dynamic programming it can be solved in polynomial time of the sum of the rods:

First consider the 2 equal rods case: Fill in a table with

 T[i][d] = max{ X | X - Y = d }

where X >= Y are rod sizes built up using only the first i rods, S1,..,Si. so if two rods can be built with with difference d then T[n][d] will give the largest such rod pair, if there is no such pair then T[n][d] = -inf

T[i][] can be filled based on T[i-1][]:

 T[i][d] = max{ T[i-1][d+Si], T[i-1][d-Si]+Si, T[i-1][d] }

actually only two arrays are needed (T[i] and T[i-1]) with length max{d} = S1+S2+..+Sn. After table T is filled in, the size of the largest rod pair is T[n][0].

Solving the 3 equal rods case:

 T[i][d1][d2] = max{ X | X - Y = d1, X - Z = d2 }

where X >= Y >= Z are built from S1,..,Si. The recursion is

 T[i][d1][d2] = max{ T[i-1][d1-Si][d2]+Si, T[i-1][d1][d2-Si]+Si,
                     T[i-1][d1+Si][d2], T[i-1][d1][d2+Si], T[i-1][d1][d2]  }

+bounds checks etc.

B. Spanning Tree

task description

This problem was about finding isomorphic trees.

There are known solutions for rooted trees (try searching for tree isomorphism problem). These can give a solution by using the center node of the tree as root. (The center node of a tree is the middle of the longest path in it. If the longest path contains even nodes then add one more at the middle. An alternative way to get to the center node is to discard all leaves, then repeat this until only one or two nodes remain).

One could use various heuristics as well, like sorting the degrees of the nodes (clearly such a list would be the same for two isomorphic trees). Using similar local properties of a tree can solve a few inputs, but larger inputs were designed so they are not easy to solve this way.

The following is a proper (non-heuristic) solution assigning a string to each tree in a way that two trees get the same string iff they are isomorphic.

Start from the leaves and assign '()' to each leaf, then repeat the following algorithm: discard the labelled nodes, find the new leaves, assign a leaf node the sorted strings of its children (alredy labelled nodes) inside parenthesis, so '(' + join(sort(string of children)) + ')'.

Repeat until only one or two node remains, if two node remains then sort the two strings and concatenate them, this string is the string representing the tree. After sorting the strings of all trees or putting them in a hashtable the final groups should be easy to get.

C. Gramophone

task description

We first masked out the background to only keep the track. Then it's only ahout following the track with the needle while saving the pixel values (this involves various parameter tunings and heuristics)

You don't need to care much about the rpm, just try to play back the resulting audio samples at various sample rate until you can understand the digits (sometimes it was hard..)

D. Uniq

task description

This problem had two tricks:

One does not even have to keep all <= 6 strings, the problem can be solved in multiple passes: check only strings with a given length and discarding the rest, then about 300 MB memory is enough to solve the last input. A simple solution would keep the strings in a large byte array and sort the strings in the end, then count the duplicates.

E. Labeling

task description

This was a scaled problem, our solver was a greedy one which sorted the cities based on their population then tried all 4 corners of a label when placing it, if the label couldn't be placed without covering an already placed label then skip it.

This simple algorithm can already get you a lot of scores.

Of course one could come up with more clever heuristics

F. Allocator

task description

This was a nice coding problem, where a few heuristics and backtracking could give you some solutions..