February 2011 Contest Problem Editorials

Our Tester for the month was Subrahmanyam

BOGOSORT (Written by Ivan Mistranu)

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

______________________________________________________________________________________________________

THREECLR (Written by Zac Friggstad)

Basically, the problem is asking you to come up with a proper coloring of a graph using the fewest number of colors possible. The only other trick is that you are guaranteed the graph can be colored with 3 colors. The existence of a polynomial-time algorithm that is

guaranteed to three color such graphs would still imply P = NP. Oddly enough, the existence of a polynomial time algorithm that is guaranteed to color a 3 colorable graph using only 4 colors would also imply P = NP as well [1].

A heuristic many people employ when coloring graphs is to color the nodes greedily (i.e. use the first available color when considering a

node) in decreasing order of degree. The idea is that high-degree nodes are ``harder'' to color if we color many other nodes before them, so we should color them first. In the case of 3 colorable graphs, another very interesting heuristic can be exploited. For a node v, let N(v) denote the graph consisting of only nodes that are adjacent to v plus all of the edges between these nodes. Then for any node v in a three colorable graph, N(v) is bipartite. The nice thing about bipartite graphs is that we can properly color them with 2 colors in linear time. So, a stronger heuristic would be to pick a high degree node v, color ALL neighbors of v using only two colors (you have to be careful that the colors used are not already used on neighbors of nodes in N(v)), and then color v with one additional new color.

For worst-case approximation guarantees, there is the following algorithm. Phase 1: while there is a node v with at least sqrt(n) uncolored neighbors in N(v), color the remaining nodes in N(v) with 2 new colors and color v with yet another color. Phase 2: now all nodes v have no more than sqrt(n) uncolored neighbors. Greedily color them with the heuristic mentioned at the start of the previous paragraph. Some thought reveals that this heuristic uses only O(sqrt n) colors so it is at least asymptotically better than the trivial algorithm that assigns a unique color to each node. There are obvious practical improvements to this heuristic, but it's a neat starting idea. This seems like a weak bound, but the best known is not much better. In polynomial time, the best known algorithm only guarantees that at most O(n^0.2072) colors are used when coloring a 3 colorable graph [2]. A more in-depth (but quite technical) survey of the theoretical results concerning coloring 3 colorable graphs can be found in [3].

[1] V. Guruswami and S. Khanna. On the hardness of 4-coloring a 3-colorable graph. In IEEE Conference on Computational Complexity, pages 188–197, 2000.

[2] E. Chlamtac. Approximation algorithms using hierarchies of semidefinite programming relaxations. In FOCS ’07: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 691–701,Washington, DC, USA, 2007. IEEE Computer Society.

[3] http://www.cs.cmu.edu/~anupamg/adv-approx/lecture15.pdf

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

______________________________________________________________________________________________________

TERM (Written by Tanaeem)

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

______________________________________________________________________________________________________

GLASS (Written by Anshuman Singh)

This problem asks you to find out the Frobenius number for given n values. In mathematical terms, we need to find the greatest number M which does not have a solution to the following equation :

Sum(ai*xi ) = M with ai>=0, ai belongs to the integer set.

There are many ways to find the Frobenius number, but probably an easier and reasonably efficient solution is to model this problem into a shortest path problem. Lets denote the minimum of xi's as X. We build a graph with X number of vertices where vi denotes the set of numbers y with y%X = i. For any pair (vi,vj) , there is a directed edge between vi and vj if for some k, (vi + xk)%X = vj with the weight of the edge being equal to xk.

We can see that if we consider any path with v0 as start vertex and weight w, it can only end at one vertex ( no matter the combination of edges taken )  =  vertex numbered as w % X.

Let Sv denote the weight of any shortest path from 0 to v in this graph. Suppose that M ≡ v (mod X ). Then we assert that M is representable as Sum(ai*xi) if and only if M ≥ Sv . We know that v ≡ Sv (mod X ). If M ≥ Sv , then M is representable in terms of A because M = Sv + ba1 for some nonnegative b.

The largest nonrepresentable integer congruent to v (mod X ) is Sv − X. Hence, we can take MAX(Sv-X) for all vertex v to get the largest number not representable as Sum(ai*xi).

Also notice that with the shortest path calculation, we can answer any query for some M in O(1) now. We just check if M>=S(M%X), if yes, then its possible to be represented as Sum(ai*xi) else no.

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

______________________________________________________________________________________________________

MSTONES (Written by Tomaz Hocevar)

The key to solving this problem is to use the fact that it is possible to cover all milestones/points with just 7 roads/lines. By pigeonhole principle, this gives us a lower bound on the answer m=n/7. Let's have a look at a non-deterministic(Monte Carlo) approach. Pick two random points (A, B) and count how many points lie on the line AB. If we repeat this several times, we are unlikely to miss the optimal solution. But just how unlikely are we?

The probability of choosing a pair of points which both lie on the optimal line is (m/n)^2 = 1/49. We won't hit the right solution after k iterations with probability (48/49)^k. But remember that you have to pass all 30 test cases, which gives us the probability of finding the right solution: (1-(48/49)^k)^30. You don't stand a chance with 100 iterations but you are well above 99% with 500.

However, many competitors took a different approach. Assume that we're dealing with 50 points or more. In this case, the solution we're looking for has to correspond to one of the original 7 lines. Pick some starting point A and sort all other points Bi by the angle of the line going through points A, Bi. If there is a sequence of more than 7 collinear points, you've found one of the original lines going through A. Now you can exclude all points on this line from choosing them as possible starting points in the future. Note that there will be at least one point left on the optimal line even if you exclude all other points due to intersections between lines. This way you can solve the problem by having to consider less than 50 starting points.

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

______________________________________________________________________________________________________

RUSHHOUR (Written by Duc)

One model solution uses the IDA* (iterative deepening a-star ) algorithm (see http://en.wikipedia.org/wiki/IDA*). The running time depends heavily on how good the heuristics being used is. Recall that one needs to define an admissible heuristic function f(s), which is no greater than the minimum cost from s to the goal state. For RUSHHOUR, the solution's heuristic tries to compute the number of cars that must move. For example, those cars which obstruct the path from the president car to the exit gate need to move. In order for those cars to move, some other cars may need to move as well... There is a variety of conditions can be employed to provide a heuristics on which car to move.

You can view the solutions here:

Problem Setter Solution

Problem Testers Solution

______________________________________________________________________________________________________