June 2010 Contest Problem Editorials

1) Graph Counting (written by Varun Jalan)

It can be shown that G has a cycle of length 5 as a minor iff G has a cycle of length >= 5 in it. So we wish to count biconnected graphs having no cycle of length >= 5.

We start by working out a few special cases for n <= 4. Now, first we show that any biconnected graph having n >= 5 vertices has a cycle of length atleast 4. Consider any nodes u and v which are not connected. Since there are atleast 2 disjoint paths between u and v (each of length >= 2), we can combine them to form a cycle of length >= 4. Hence, the only possibility is that for all u,v there is an edge between then. But in that case, the graph is a clique and has a cycle of length >= 4. Thus, all biconnected components having >= 5 vertices have a cycle.

Now we can use an ear decomposition of two connected graphs. The result basically says that we can start off with any cycle in G, and form the graph progressively by adding maximal paths (ears) to G. So we start off with a cycle having 4 nodes (one surely exists, as we have seen above). Now analysing a few cases reveals that the only way to add ears to G are between 1 diagonal, and each ear should have length exactly 2. In all other cases, we get a cycle of length >= 5. Thus, G looks like this : there are two nodes u and v, with n - 2 disjoint paths of length 2 between them. We can optionally add a direct edge between u and v if needed. Thus, the total number of edges in G are either 2*(n-2) or 2*(n-2) + 1. We can choose u and v in ncr(n,2) ways. This gives us the following result :

if n = 1, output 1 if m = 1, else 0
if n = 2, output 1 if m = 1, else 0
if n = 3, output 1 if m = 3, else 0
if n = 4, output 3 if m = 4. If m = 6 output 1, else if m = 5 output 6. else output 0
for n >= 5, output n*(n-1)/2 if m = 2*(n-2) or m = 2*(n-2) + 1. else output 0.

2) Pricing Tollbooths (written by Zac)

Approach Taken:

Determining the optimal solution is NP-hard so one has to resort to heuristics to solve the problem. The reduction showing NP-hardness is not obvious; [1] shows weak NP-hardness and [2] improves this to strong NP-hardness. There is a very simple poly-time algorithm that is guaranteed to find at least a 1/log(N*M) fraction of the optimum cost [3]. It can be described in very simple terms: for each number T of the form B_i/|t_i - s_i| (budget divided by length), set the prices of all edges to T. Use the value T that maximizes the total revenue of all clients who can afford paying T times the number of tolls they cross. This is the starting point for quite a few heuristics that can be tried. Some of the best solutions employed very interesting tools including dynamic programming approaches and using linear programming techniques.

In theory, for every constant eps > 0 one can get at least a (1-eps) times the optimum profit in time O(n^(c/eps)) for some constant c [4]. The algorithm isn't very practical in practice, but it does show that in theory we can get within any given constant factor of the optimum in polynomial time.

While the condition that the prices be integers in output for the problem might seem like a restriction, one can actually show that if all budgets are integer then there is an assignment of non-negative integer tolls to the tollbooths that achieves the maximum possible profit (so we don't need rational numbers).

[1] Single-Minded Unlimited Supply Pricing on Sparse Instances, P. Briest and P. Krysta
[2] On Profit-Maximizing Pricing for the Highway and Tollbooth Problems, K. Elbassioni, R. Ramen, S. Ray, and R. Sitters.
[3] On Profit-Maximizing Envy-Free Pricing, V. Guruswami, J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F. McSherry.
[4] Prizing on Paths: A PTAS for the Highway Problem, F. Grandoni and T. Rothvoss

3) Prime Pattern (written by Ivan)

View solution here.

4) Squirrel and Chestnut (written by AnhDQ)

View solution here.

5) Robot Game (written by Akhil Ravidas)

Solution: Tree traversal, DFS
Complexity: O(N)
Difficulty: Easy

Consider a complete binary tree T with 2^d-1 nodes, where d is the maximum depth of any of the given maps. Each city in this binary tree has a unique path from the root of T (and therefore a unique control string). For a given map, every city has a unique control string. Now each city on the map can uniquely be mapped to a city on T by following its control string on T.

To solve the problem, at each city in T, store a variable count, which denotes the number of maps which has a valid control string from root to the present city in T. Initially, all counts are 0. On adding a map, we can update the count of a city in T, by doing a depth first search (or any other traversal) on the given map and also computing the corresponding city number in T. Note that the length of the control string of any city is equal to the level of the city, assuming that root is at level-0.

Now we can just splice all the maps into T, renaming the cities in the map whenever necessary and find the required answer by looking at the count and level of each node in T. Since the total number of cities are 100*1000, we only need to consider atmost 100000 nodes in T as the rest of the cities in T will never correspond to a valid control string.


6) Tidying Posters (written by Zac)

Consider the graph whose nodes correspond to posters where two posters are connected by an edge if they share a common point.  The problem is then to find the largest independent set in this graph.  Here's the idea.

The graph is actually a "comparability graph".  That is, the edges can be directed so that if u->v and v->w are directed edges, then so is u->w.  To see this, for two posters u,v that overlap, we direct the edge from the skinnier to the larger poster.  If one remembers the property that no poster contains the corner of another, a moments thought (or a quick doodle on a scrap of paper) reveals that u->v and v->w implies u->w.

Comparability graphs enjoy the nice property that the maximum independent set size is equal to the minimum number of cliques whose union covers all nodes (this is Dilworth's theorem). Furthermore, cliques in comparability graphs correspond to directed paths and vice-versa (once the edges are oriented as implied above).  So, we have reduced the problem to computing the minimum number of paths required in a directed graph to cover all nodes.  This is solved via bipartite matching.

Build a bipartite graph B with a copy of the nodes of the original graph on both sides.  Call the original directed graph G and say it has n nodes.  Add an edge from a node u on the "left" to a node v on the "right" in B if u->v is a directed edge in G.  Then, the size of a minimum path cover in G (and, hence, a maximum independent set) is exactly n minus the maximum matching size in B.

To see this, say we have covered the nodes of G with k paths.  In total, these paths use exactly n-k edges in G.  For each u->v edge used in the path decomposition of G, we select the corresponding u-v edge in B (with u on the "left" and v on the "right").  This is a valid matching in that uses n-k edges. 

Conversely, consider a matching of size m in B.  We can construct exactly n-m paths in G whose union covers all nodes.  Also note that exactly n-m nodes on the "left" and n-m nodes on the "right" of B are not matched.  Pick any node v_1 on the "right" of B that is not matched.  Now, let v_2 be the node on the "right" that is matched to the copy of v_1 on the "left".  Let v_3 be the node on the "right" that is matched to the copy of v_2 on the "left".  Continuing in this way until we reach a node v_b whose "left" counterpart is not matched, we construct a path v_1, v_2, ..., v_b.  Furthermore, we have used exactly one unmatched node on the "left" of B (corresponding to v_b) and one unmatched node on the "right" (corresponding to v_1) and there are now n-m-1 unmatched nodes on the "left" and the "right" of B.  Iterate this process to obtain n-m paths in G which, together, cover all nodes.

Building the graph takes O(n^2) time (each pair of posters need to be checked for intersection).  Assuming the worst case of O(n^2) edges, the matching phase takes O(n^3) with the standard augmenting paths algorithm.  This can be improved to O(n^2.5) with Dinic's matching algorithm but is not necessary for the time restrictions placed on the problem.

That might seem like quite a few steps to make, but I think it is actually a little easier than the Generalized Spanning Tree problem used in the May competition (easier, but still hard).  The main idea is to see the intersection graph as a comparability graph.