I previously wrote about the Bay Bridges Challenge, hosted at CodeEval. In my last post, I showed that the problem could be modeled as a minimum vertex cover problem, and wondered if we can do better than iterating through the power set of bridges, and picking the highest cardinality subset that is feasible. I said that most likely,
there is additional structure inherent in the problem, that can be exploited to make the problem more tractable.
Spurred by some helpful recent comments, I spent some more time on the problem. As it turns out, we can do better than an exhaustive search. But first, remember that a feasible solution is any set of bridges with no intersections. Our task is to find an optimal solution, which is simply the largest such feasible solution (note that there can be more than one).
Claim 1: If there is no feasible solution with \(k\) bridges, then there cannot be a larger feasible solution.
Proof (by contradiction): Assume that there is a solution with \(l = k + 1\) bridges. The removal of any bridge from this solution should still be a set of non-intersecting bridges, i.e., a feasible solution, but of size \(k\), which is a contradiction. By induction, we can see that this is also true for higher values of \(l\). QED.
With this claim in hand, let us partition the power set of \(n\) bridges so that \(p(i)\) represents the set of all sets of bridges of length \(i\). We can then make the following observation about the \(n\) partitions (we can safely ignore the empty partition \(p(0)\)):
If any set in \(p(n/2)\) is feasible, the optimal solution is in one of the partitions \(p(n/2)\) through \(p(n)\). Otherwise, it is in one of the partitions \(p(1)\) through \(p(n/2 - 1)\).
In other words, we can do a binary search on the partition index \(i\) until we find the partition with the optimal solution. While this seems very promising, the partition size \(|p(i)| = {n \choose i}\) unfortunately has a maximum at \(i = n/2\) (note that \(|p(n/2)| = {n \choose n/2} \approx 2^n\)). So, in the worst case, we still need to search an exponential number of bridge sets.d But in practice, this should still be significantly better than exhaustively searching each partition.
Anyway, I didn’t really feel like coding up this binary search, so I tried submitting a simpler, more naive solution: Search each partition \(p(i)\), starting with \(p(n)\), in decreasing order of \(i\), until you find the first feasible solution \(f\), and return \(f\). Because of Claim 1, it is easy to see that \(f\) will be an optimal solution to our problem. It turns out that this approach was enough to get a score of 100 (with a ranking of 86). So, now I am even less inclined to implement binary search.
Also, I should really post the code for all of my solutions to github, which I hope to do soon.
Update: I have checked in solution code for the Bay Bridges challenge and other codeeval challenges at github. Check it out at my github.