Railway Station Solution by nikaj

It’s clear that it doesn’t make sense to build a station if it’s not connected to another with rails (except for the very first one, of course).

Therefore, stations form connected components. It’s also clear that these components should be trees.

The problem is quite difficult, we need to simplify lots of things to make it feasible.

Always maintain single connected component (not a forest). This may not always be optimal but counterexamples should be rare. This means that the whole process is just about building new stations and connecting them to existing.

There are multiple ways to connect. The trivial case is when station is built on the rail and we don’t need to do anything. Otherwise, we will make another simplification and pick the closest one (manhattan distance) and try to connect to it. There is another possibility, though. We could alter existing rail paths connecting two other stations, changing it slightly without affecting anything else. If the altered path passes through our new station, we don’t have to build any rails. Checking this possibility isn’t difficult: pick two orthogonal directions, find first non-empty squares in those directions (starting from target square) and if they are connected by rails, their path can be altered.

In summary, it’s a 3 step process:

• Check if it’s on rail (0 rails needed)

• Check if it’s on possible modified path (0 rails needed)

• Check if it can be connected to closest station (distance-1 rails needed)

Now we get to another point: how to connect one station to another with rails. We will simplify again and only consider the shortest paths. We can just run DFS (much faster than BFS) on empty squares in one or two desired directions. But what if some paths block every access? We could try altering those paths.

C..
┌─A
B..

C wants to connect to B, but rails from A to B block it. We can perform path augmentation process (similar to Max Flow algorithm) and steal part of the path and delegate finding remaining path to another station.

C..
|─A
B..

Now A is again looking for shortest path to B and succeeds.

C..
|┌A
B┘.

This delegation can happen up to 3 times (see below for new station E) but in practice it doesn’t need more than 1.

─┘.B
E┌A┘
.C└D

In summary, connecting works like this:

• Looks for empty path with DFS

• Find augmenting path instead with modified DFS

How to build whole tree? Naturally, one by one adding new stations and for that you could try Beam Search. The evaluation function should probably include current time, money, daily income, the simplest being just idle score. Some commuter will have one connection station, which is much better than none and that could also be part of it. In the end I built simple NN (2 hidden layers up to 7 nodes each) based on these features and trained on final solutions.

But for harder cases (large M) beam search isn’t doing well.

We follow up with SA on the best found solution. Transitions change the station list:

• Remove station from the list

• Swap two neighbours

• Insert new station

Both in beam search and SA when looking for new station we consider those that include commuters that already have one connection. If there are no such commuters, we consider all of them.

There is one more thing. Just knowing the order of stations (and rails, since they are determined based on stations) isn’t enough, we should also decide to build rails before building previous station to save time in the long run. The optimal building order can be found by dynamic programming, with following state: [time][stations][rails] -> money. Transitions are (each increase time by 1, money changes accordingly):

• Wait

• Build station (stations increases by 1, rails decreases by the corresponding number used by this station)

• Build rail (rails increases by 1)

Some of the operations needed in the solution can be sped up (using bitmasks in some cases), but solution is still overall quite slow and far from optimal (more than 2% away from local best and probably more.

The main improvement to this solution would come from making SA faster, representing the state as a tree instead of list of stations. This would have significant impact on testcases with large M.