1. Calculate all distances assuming no repairs (takes at most 50 ms and there are several ways to do it, I used my own weird algorithm, but full dijkstra is just as fast)

2. Gather information about the relation between edges. It works like this:

   • For 2 or 3 seconds pick two random vertices. Generate the shortest path between them with A*.

   • For each edge on that path, assume the edge is not there and re-generate the (slightly longer) path (because 1 edge is gone)

   • Each edge on the graph has a relation-score with each other edge on the graph. Positive means they should not both be in repair on the same day and negative means they are encouraged to be in repair on the same day.

   • For each random path and each excluded edge on that path: compare the original path and the new path. Each edge that occurs in the original but not in the new path gets negative relations with the excluded edge and positive if it’s only in the new path. The positive score discourages repair on the same day, the negative score encourages it. Usually I got to around 50-100k iterations (paths). Which means around a million times an edge was updated compared to another edge.

3. Run simulated annealing for the rest of the time, to minimize the total relation score ( all edges related to all other edges ). This means that edges get in eachothers way as little as possible, because alternative paths do not get blocked.

I could run an SA iteration around 500k to a million times this way if I remember correctly. Each time I swap one edge to a different day and check if the graph is still connected.

I update the total relationscore by checking all its relations with the other edges in repair on that day. This does take some optimization to get it to run fast. You don’t want to have to do a loop of 3000 each time you do an update.

I had a uint64_t[47] bitboard for this (47*64 > 3000) and did a bunch of & to get as few active bits as possible, then used a while loop with builtin_ctz to loop faster. There are two such updates. One to remove an edge from the current day and one to add an edge to the new day. It works similarly.

I did well, got to 6th on tuesday. After that all my new ideas failed and I did not improve much.