Overall Strategy

The solution consists of two phases. In the first phase, we try to discover an approximate path with low cost. Cells dug in this phase are far apart. In the second phase, we connect the houses and water sources using the path discovered in the first phase, but making small adjustments. In the second phase, cells we dig are consecutive.

Optimal MST

The optimal spanning tree that connects all the houses to some water sources can be calculated in \(O(n^2 3^{h+1})\) (\(h\) is the number of houses) using Steiner Tree bitmask dp. However, this turns out to only outperform the following simple greedy by a small margin.

Repeatedly, pick a pair of (house without water, cell with water) with the lowest cost path, and connect them.

Considering the runtime factor of \(3^{h+1}\), I decided to not make use of steiner tree or any approximation in the solution. Instead, both phases will be based on this greedy.

First phase

Fix a grid size \(K\) which is an even number (I mostly took \(K=18\)). We take a diamond grid of size \(K\): Consider all cells \((x,y)\) which have both \(x,y \equiv 0 (\mod K)\) , or both \(x,y \equiv \frac{K}{2} (\mod K)\). We will try to dig only these vertices to discover a MST connecting the houses and water. These are called key cells.

We maintain an estimated cost of each key cell. Initially, all key cells optimistically have near 0 estimated cost. We will perform path finding on this subgraph consisting of only key cells and houses and water sources.

We decide the next cell to dig as follows: Find the pair of (house without water, key cell with water) with the lowest estimated cost. Then, attempt to dig the first non-crushed cell on this path, using some fixed power \(P_1\). If this does not crush the cell, we increase the estimate of this cell by \(P_1\). Otherwise, we multiply the estimation of this cell by some factor \(c\) (usually \(c= 0.6\)) and this estimation stays.

In either case, we calculate a new shortest path after each dig. I have used SPFA to achieve this, but using any shortest path algorithm should not exceed time limit.

Second phase

After the first phase, we obtain a provisional spanning tree that consists of key cells. We call key cells involved in this spanning tree critical cell.

We say a cell \((x,y)\) is relevant if there is some critical cell \((i,j)\) satisfying \(|i-x|\leq \frac{K}{2}\) and \(|j-y| \leq \frac{K}{2}\). The final spanning tree will only consists of relevant cells.

We will dig these relevant cells consecutively. Every relevant cell is given an estimated cost: it is the weighted average of adjacent cells that we have information for. A crushed cell that is mahattan distance \(d\) nearby will have a weight of \(c^d\) (\(c= 0.65\) usually). Key cells have are given a different constant factor in weight.

The exact digging is similar to first phase. We find the pair (house without water, relevant cell with water) with the closest estimated distance, and dig the first cell along this path without water.

Power Choice

If \(E\) is the current estimation of the cell , the first attempt will be \(a \times E\) (\(a\) is something between \(0.6\) to \(1.4\) depending on \(C\)). Afterwards, each dig will be of a fixed power \(P_2\).

Updating Cost

If the first attempt using power \(P\) is successful, then we set the cost to some \(k_1P\), (\(k_1\) is somewhere between \(0\) and \(0.5\)). Otherwise, the cost will be the actual power spent plus a fixed number \(P_z\).

Implementation

If the above are implemented without inefficiencies, I estimate this to give a solution about 30-th place. Half of my gains have been from optimising small inefficiencies , for example, not digging out water sources that have not been used.

Here is another one such small optimisation. A diagonal edge between two key points in the first phase have a slightly lower cost (about \(0.9\) times). This is because diagonal paths have more adjustment opportunities in the second phase .

Parameter Search

A key part of the gain is from optimising the parameters: All variables mentioned above have been taken as parameters. These parameters have to be separately optimised for different \(C\) , as different \(C\) have very different characteristics.

In the final solution, there are \(18\) parameters, \(14\) of which are very important. A key task is to find the best sets of parameters.

My solution is not implemented particularly efficiently. There are many calls to SPFA. It takes on average one second to run a test case. On my 10-core machine, this means I can only afford to run about 36k cases every hour.

However, to optimise the parameters we must run a large amount of test cases. If we only test a parameter change on small number of test cases (40 to 100), then the results will not generalise. A direct evaluation on anything less than 1000 cases (for each \(C\)) is simply not solid.

To balance the two issues above, I come up with the following simulated annealing-like approaches. I tuned the parameters based on \(S\) test cases. \(S = 40\) initially, but slowly increases as time goes on, ending at \(S=640\) at the end. We accept the fact that there are some randomness of taking only \(40\) cases, but this seems to be just right for a simulated annealing. This seems to be effective enough. I got a few percent score increase from this.

Due to time constraints and computation power, I only managed to run this process one hour each on 6 of the 8 sets of parameters. This would have been an easy place to get a higher score, if I have more computation power.

Reflection

Even though the time limit is not an issue, it seems like having a quick solution is important as it allows much quicker tuning of parameters.

There are a few extra places that I could have taken as parameter. I also didn’t experiment with which exact parameter form is the most useful. There are still many optimisations possible.

This is my first serious heuristics contest. I am happy to have a great performance in my first contest.