PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
The problem breaks down into checking cycles of even length and cycles of odd length in different ways. Cycles of even length are easy once the following fact is established. Say a cycle C is bad if the sum of the f(v) values of nodes in the cycle exceeds floor(|C|/2). Then we have that no cycle of even length is bad if and only if no cycle of length 2 is bad. One direction is obvious so let’s assume we have a bad cycle v _ 1, v _ 2, …, v _ k of even length. That is, assume the total of the f(v _ i) values exceeds k/2. Consider the edges (v _ 1,v _ 2), (v _ 3, v _ 4), …, (v_ {k-1}, v _ k). There are k/2 edges and the total weight of the f(v _ i) values exceeds k/2, so then there must be edge (v _ i, v _ {i+1}) with f(v _ i) + f(v _ {i+1}) > 1 so that edge is bad. Thus, we only have to check f(u) + f(v) for edges u,v to see if there are any bad cycles of even length which takes O(m) time (discounting the cost of fractional arithmetic, though using floating point numbers would probably be safe enough for this problem).
Finding bad cycles of odd length takes a bit more effort. Once we have verified that f(u) + f(v) <= 1 for each edge e = (u,v), let’s add weights to the edges of G where edge e = (u,v) gets weight g(e) = 1-f(u)-f(v) (which is non-negative). Let C = v _ 1, v _ 2, …, v _ k be an odd length cycle and notice that the weight of the edges in C is k - 2 * (f(v _ 1) + f(v _ 2) + … + f(v _ k)). If C is a bad cycle then the sum of the f(v _ i) values exceeds (k-1)/2 so the sum of the edge weights of C is strictly less than k-2 * (k-1)/2 = 1. On the other hand, if C is a good cycle then the sum of the edge weights of C is at least 1. So, we have reduced the problem of finding a bad odd length cycle to that of finding an odd length cycle whose total edge weight is strictly less than 1.
Now, form a bipartite graph B with a copy of each node in V on each side. For an edge e = (u,v) with weight g(e), connect u on the left to v on the right and also connect v on the left to u on the right with a weight g(e) edge. It isn’t too hard to argue the following. For any node v, there is an odd length cycle in G of total edge weight strictly less than 1 if and only if the shortest path from the copy of v on the left of B to the copy of v on the right of B is strictly less than 1. So, we just have to compute the length of the shortest path between the two copies of each node using Dijkstra’s algorithm which, when using the standard implementation of Dijkstra’s in contest settings, is n calls to an O(m * log m + n) algorithm.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.