Collusion on Two Wheels

This problem gives us a set of points on a manhattan grid and asks us to divide the points into two groups such that the diameter of the graph is minimized.

Most division algorithms will be somewhere around n^3. If we instead take the decision problem, we ask whether we can divide the graph such that no points in either set are more than a fixed k apart. If we draw edges between all nodes that are <=k apart, this is equivalent to finding two cliques which cover the whole graph. Alternatively, if we take the INVERSE graph, and draw edges between nodes which are further than k apart, we only have to ensure that this graph is bipartite, i.e. If two nodes share an edge that is too long, they MUST be on the opposite sides of the division. It then becomes trivial to 2-color the graph to determine whether it is bipartite and there is a solution for the given k.

Binary search to find k.