Q1) Given a line of n (up to 51) rooms separated by gates of up to 16 different types, a game is to be played. One of the (non-end) rooms is the ‘target’ room, where both player 1 and player 2 want to get to. Player 1 starts in room 0, and player 2 starts in room n-1. Each player (starting with player 1) takes turns removing all gates of a specific type. At any time if someone can reach the target room, they have won. If both can reach the target room the game is considered a draw. Assuming optimal play return how quickly player 1 can win (if they can), or how quickly player 2 can win (if they can), or ‘draw’.
A1) This is a simple memotized recursion, using the bitset of gates removed as its state. At each stage of the recursion first check if the given bitset is a p1 win, p2 win or draw. If it is one of these 3 states, return 1, -1 or 0 – swapping the first two if the popcount of bitset is odd (cache the result of course). If it is not a win for either player and not a draw, recurse on each bit which is not in the bitset, and select the closest negative number to 0, 0, or largest number of all recursion options and return that (after caching it).
While this approach is fast enough (50*2^16 worst case), a greedy implementation actually works. If you divide gate types into left, right, or both compared to the target room, then player 1 wins if left + both <= right, player 2 wins if right + both < left and in all other cases its a draw. Number of turns is 2*(left + both)-1 in the former, and 2*(right + both) in the later. Giving an O(n) solution, which works regardless of the number of gate types.
Q2) Given two parallel rows of n dots, where some specific dots in row 1 are already connected to specific dots in row 2, determine the expected number of pairwise crosses formed if each remaining dot in row 1 is joined to a random remaining dot in row 2. Every dot in both rows will have exactly 1 line connecting it to another dot in a valid randomly generated situation. Limits: n is up to 10000 and count of specific starting joins is up to 50.
A2) Summation of the expectation value of crossing for a specific pair over each pair of dots in row 1 will give the answer. However with n=10k n^2 is not fast enough. We can divide the problem into 3 cases.
- 2 non-specified dots. Expectation value for all of these pairs is exactly 0.5, so we can sum all of these quickly. (O(1) time even.)
- 2 specified dots. 1 or 0, we know whether they cross. The 50*49/2 pairs to consider is easily executed.
- 1 specified dot and 1 non-specified dot. At 50*10k, this could be brute forced, with probability defined by the ratio of non-specified locations to the left/right of the specified location in row 2, flipped if the specified dot in row 1 is to the left instead of right of the non-specified dot. However every non-specified dot is going to have the same ratio, only depending on whether it is left or right of the specified dot in row 1. Therefore by knowing how many specified dots there are to the left/right of each end of each specified dot pair, this can be performed much faster.
Q3) Given a map, up to 50×50, with up to 4 pairs of towns which want a road built between them, determine the minimum cost to build the up to 4 roads required. Roads are free to build, and can go anywhere, except through a rock. Rocks are a side to side connected set of square tiles for which the entire set can revert to being normal ground for a specific cost. There are up to 62 rocks, and no 2 rocks have the same cost. No rocks overlap with any town, nor do any towns overlap with other towns.
A3) This is a tough question. No one solved it in the competition.
A single pair of towns is trivial, you just create a directed graph where nodes are connected sets of map tiles of the same type, and side-to-side adjacency defines the graph edges. The incoming edges to rocks all have a cost equal to the cost of removing the rock, and the outgoing edges are free. Then you calculate shortest path from town to town.
Handling 4 town pairs is tricky, because you have to consider the case where the cost of a given rock is shared between more than 1 road. Looking at the solution write up, the suggested way to approach this is a dp over location and a mask indicating the towns are you are trying to join through this location, and the towns which are already joined. For each mask and position you consider each possible way of breaking the mask into 2 submasks. The cost for that combination is then the sum of the 2 sub mask costs minus the cost of getting to this node if both of the submasks have one or more lone towns out of the town pairs. The reason for the subtraction is if the submasks have a lone town then both of them have already incurred the cost of destroying this rock to get here, and so we need to refund it.
So far so good, however we have not handled anything to do with the cost between between nodes yet. For a given mask and location, we need to minimise its cost by considering we could come from another location with the same mask. If the mask has only pairs, it is already fully connected, so there is no road being built and we freely minimise everything. This lets us combine any road with another when we build up the mask to a higher bit count. If it does have a lone town, we have to pay the shortest path cost between the two vertexes (if it has multiple lone towns, we only have to pay the cost once!). This second case requires n^2 steps to ensure minimisation is complete. (The former can be performed in n steps, but it isn’t a significant performance boost.)
The final problem is that n^2 is kind of expensive considering we have to do it for most of the up to 256 masks. A particularly nasty arrangement of rocks can result in ~800 nodes in the graph. However, excluding the empty space nodes, there can only be at most 70 nodes ( 8 towns and 62 rocks). Every empty space node can be eliminated by connecting its incoming edges to its outgoing edges, since the incoming edges always have 0 cost, you basically just throw away that edge. Number of edges will increase significantly in some scenarios, but still all points shortest path will easily run in time with the lesser number of vertexes, and the overall algorithm benefits hugely from the decreased vertex count.
An interesting algorithm, certainly beyond my abilities to create on the fly.