## EC Solutions

For inputs and outputs see the 2012 archive.

### A. Triangles

The most popular controversial problem of the contest.

The trick to this problem is interpreting the task description literally: 3 neighboring black pixels not lined up will form a triangle; 4 pixels in a group may form even more little triangles. It is not necessary to have any white pixel inside a triangle. This means if a single large trinagle is drawn, depending on the shape, it will end up being at least 4 but sometimes even more triangles total (because of little triangles in the corners).

When we designed the task, we overlooked this detail first as well. We had to recheck multiple times until we really could tell accurately how many triangles there are in the simplest test case.

### B. Mines

If we connect each mine with other mines within detonation radius, then we get a directed graph.

In this directed graph the mines of a strongly connected component are equivalent (detonating anyone of them has the same effect)

For each strongly connected components if their nodes are joined into one super node then the resulting graph will be a directed acyclic graph in which the source nodes (no incomming edge) have to be detonated (and this solves the problem).

Building the graph is O(n^2) if done naively, but sorting the mines along an axis can speed this up, or using a proper space partitioning data structure is probably even faster.

Finding the strongly connected components and then the sources of the DAG can be done in O(n) time. (depth first search graph traversal).

### C. Lumberjack

The solution has two parts:

• calculating the effect of each tree when it falls left and right.
• determining the best trees to cut using dynamic programming.
The naive algorithm to the first part is O(n^2) but it can be solved in O(n*log(n)) time as well.

The second part can be done with the following approach:

• either make the leftmost tree fall right
• or find all the trees which if fall left can topple the leftmost tree
Then choose from all these cases the one for which the remaining trees can be cut down with the least cuts. This recursion can be programmed using dynamic programming starting from the right end. This second part is O(n^2) when programmed naively but can be done in O(n*log(n)) time as well giving the full algorithm O(n*log(n)) complexity.

EDIT:
Team ... proposed a faster solution. Actually the former two parts can both be solved in O(n) time. The source code can be found here (<60 lines of C code). It may be difficult to see what really happens, but it can be proved that it always works and has linear complexity. Thanks for sharing the idea with us!

### D. If

Most confusion was caused by indirect addressing of input and output instructions.

There are a few very simple optimization methods which can gain a lot:

• remove code lines that do not run for any possible input
• constant optimization (reduce expressions resulting in constants to a single constant initialization)
• remove unncesarry labels and jumps

Running only these would remove at least 1/4 of most of the inputs already.

Different approaches include:

• convert the .in to C, use an optimizing c compiler that can produce parsable output (i.e. gcc) and convert the result back to the submission format; there are only 10 inputs, some manual post processing may be cheaper than coming up with a fully general converter;
• run all inputs and save outputs for each, then try to find out what the program does and rewrite from scratch

### E. Beacons

The loudness of the towers and the delays of the maximums for each tower's signal can be used for the solution.

The simplest approach is probably calculating the power of each frequency at each time with a sliding window using the Goertzel algorithm (or using band filters). Then the power values give an approximate position and then one can try all possible positions and starting phases around that area.

### F. Currency hack

This problem could be solved with generalized maximum flows (theory and algorithms).

The nodes are the currencies, the source and the sink are the initial currency. The edges are the offers with capacities and gain ratios. There are fast algorithms for solving specifically this, but it can be also formulated as a Linear Programming problem (and then using an lp solver).

A preprocessing phase is neccessary, we have to remove all currencies that are unreachable from the initial currency. Of course this also means removing all offers that convert unreachable currencies.

The linear program is this: x_i is the optimal amount of money that should be converted with the ith offer. For every x_i there are simple constraints like

```0 <= x_i <= max_i
```
And for each currency the amount left at the end should be greater than 0:
```SUM( -x_from ) + SUM( r_to * x_to ) >= 0
```
summing over all offers which convert from or to the given currency. (r_i is the conversion rate of the ith offer)

Finally the cost function that should be maximized is the amount left of the original (national) currency.

Giving these equations to a solver like lpsolve we can easily get the optimal x_i list and the maximum of the cost function.