For inputs and outputs see the 2012 archive.
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.
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).
The solution has two parts:
The second part can be done with the following approach:
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!
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:
Running only these would remove at least 1/4 of most of the inputs already.
Different approaches include:
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.
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_iAnd for each currency the amount left at the end should be greater than 0:
SUM( -x_from ) + SUM( r_to * x_to ) >= 0summing 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.