← All solutions

Shortest judge solution: 1224 bytes. Shortest team solution (during contest): 1955 bytes.

Let us translate the problem into graph theoretic language. We have a simple graph G which contains at least one cycle. We want to find all numbers k, such that the edges of G can be colored with k colors, so that each simple cycle contains the same number of edges of every color. Obviously k will have to divide the length of every simple cycle in G. The author expected some of the contestants to believe this was a sufficient condition without sufficient analysis, and fail.

First consider any edge e in G which is a bridge (that is no simple cycle passes through e). Then the answer to the problem in G is the same as in G with e removed — we may give e any color, and it will not occur in any simple cycle, so it will not change the correctness of the solution. Thus we may begin by removing all bridges from G, from now on we will assume G is bridgeless.

Now consider the following relation on edges: we say two edges e and f are related, removing both e and f from G increases the number of components. This is clearly an equivalence relation. It can be proved that k is a good solution if and only if the size of every equivalence class is divisible by k. (The “only if” part is easy to prove, and the “if” part a bit more work – this is left as an exercise.) Thus the problem is equivalent to finding the greatest common divisor of the sizes of all equivalence classes.

Note that the contestants need not prove the characterization above, just gain enough intuition about the problem to become sure it is true.

The sizes of the equivalence class containing an edge e can be computed by removing that edge and then checking how many bridges there are in the resulting graph (and adding 1 to the result). Since bridges can be found in linear time using DFS, this gives an O((|V| + |E|)²) solution.