Today was another ACM practice session, where the problems were of medium difficulty, and the challenge was largely finishing as many problems as possible in the alloted time. My team did relatively well, but completely missed one of the first easy problems, accidentally initially misclassifying it as hard, and never returning to it after getting stuck on other 'easier' problems. This is my penance: a full dissection of the problem and providing the correct C++ solution on Github.

Problem Statement (my wording)

There are n kingdoms (2 ≤ n ≤ 20) which all owe each other some integral amount of money. This can be represented as an anti-symmetric matrix where the entry a = (i, j) corresponds to kingdom i owing kingdom j a units of currency. When a kingdom is in the red (owes more money than it is owed) it can declare bankruptcy. This wipes out all of this kingdom's debts, but the kingdom can also not collect any of the money it is owed. For all sequences of bankruptcies, find all kingdoms which are the 'last kingdom standing' (i.e. all kingdoms go bankrupt except one).

Analysis

The key to this problem is the limit on n: at most 20. This means our algorithm can have pretty bad complexity, and we'll still get away with it. The only thing that you won't be able to get away with is a straight-up listing of all permutations (20! is just too large).

The Solution

Because n is small, I first think about the brute-force solution: DFS through the space to find all the reachable kingdoms. However, DFS will run in time n! in the naive solution (worst case) - when all kingdoms go bankrupt but one, for every single ordering. Notice, however, that the order of bankruptcy does not matter. In particular, if kingdom A goes bankrupt, then kingdom B goes bankrupt, it leads to the same state as kingdom B going bankrupt, then kingdom A going bankrupt. I can take advantage of this by implementing a visited set, which after trying a particular variation, saves the path to that variation in a set. Then when that variation is tried again, we will find it in the set, and won't need to check it. In the worst case, the set will contain all subsets of {1, ..., 20}, which will make the visited set of size 2^n. But because of this heavy pruning, the algorithm should also run in time 2^n, as each subset will be checked precisely one time. Note that since 2^10 ≈ 1000, and n ≤ 20, then 2^n ≈ 1,000,000. This is quite tractable.

Visualization

Below is a randomly-generated debt-matrix for 12 kingdoms. Because of the speed of visualisation, it's not practical to show 20 kingdoms - 1,000,000 DOM operations is just too slow in Javascript.

Now that we have a matrix, we can pick a kingdom which is in the red to declare bankruptcy. Watch what happens to the other kingdoms. Notice that the relative solvency of the kingdoms changes as a kingdom files for bankruptcy. If you don't like the current allocation of debts, feel free to change it by pressing Generate Debts.

Because the Declare Bankruptcy function above always picks the first kingdom to bankrupt, there will only ever be one result. i.e. If you bankrupt all the kingdoms except 1, then press reset, then do it again, you will get the same result. However, the order of bankruptcy matters: if you bankrupt a different kingdom first, then the final kingdom may be different. The full program takes this into account. Click the Animate button to animate the table above, and show my algorithm in action. Or click the Solve button to see the non-animated version, which will yield the same result but run much faster.

The complete C++ program is available here as a Gist. As an interesting aside, the performance of using bitset.to_string together with set<string> is about 3 times worse than using bitset.to_ulong together with set<unsigned long>. Also, I did not see any measurable speedup from disabling syncing streams.