SLPC 2011 - Guessing Game

Post date: Oct 12, 2011 2:30:31 AM

For this problem, Aram told me Cedric said the solution is in CLRS, so I read it up and implemented it. Here I'll try to explain the idea behind the solution. The code is available at http://pastebin.com/iqH0QLKC

The problem: given 2 lists of integers a and b, and a set of inequalities of the form a_i+b_j <= c or >= c, we want to decide whether the set of inequalities is feasible. This is a stereotypical integer programming problem, which is in general NP-hard. However, these particular constraints given to us is actually an encoding of a simple problem, which we can solve in polynomial time.

We could take b' = {-x|x in b} and change the inequalities to the form a_i <= b'_j+c or a_i >= b'_j+c. If the changed inequalities are consistent, then so are the original ones, and the problem hasn't changed.

First, let's review one part of the Bellman-Ford algorithm for finding the shortest cost of any path from a specified source vertex to any other vertex in a weighted digraph. If the cost d(v)=dist(source,v) is the minimal cost, then we have for all u such that uv is an edge in the graph, d(u)+weight(uv) >= d(v), because otherwise we could take the path with d(u) to u, and then take the edge from u to v, and get a path with a lower cost.

If we replace d(u) with b'_j, and d(v) with a_i, then we get immediately that a_i <= b'_j + weight(uv). If we replace d(u) with a_i, and d(v) with b'_j, then we get b'_j <= a_i + weight(uv), or a_i >= b'_j - weight(uv). These are just the new inequalities we got after changing b to b'.

So, if we consider the bipartite graph with the a's in one partition and the b''s in the other partition, and an edge of weight c going from b_j->a_i if there is an inequality a_i+b_j <= c, and similarly an edge of weight -c going from a_i->b_j for the inequality a_i+b_j >= c, then the inequalities hold iff there exists a path of least cost between any 2 connected vertices. We know this is true as long as the graph does not have any negative weight cycles. So, the problem reduces to detecting whether the given bipartite graph has a negative weight cycle.

The easiest way to do so is just to run Bellman-Ford on it, which is what I've done. Bellman-Ford runs in worst case O(VE). V is N+M, E is Q, so VE is 10 million which is not bad given that we have 10 seconds. If the number of test cases were a bit more though this might actually be too slow. But I also haven't exploited the fact that the graph is bipartite, which could possibly make detecting negative weight cycles easier. I haven't really though about it, so maybe if you come up with an improvement leave a comment about it.