You are not logged in. Please login at www.codechef.com to post your questions!

×

GENIND - Editorial

PROBLEM LINKS

Practice
Contest

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.

This question is marked "community wiki".

asked 26 Nov '12, 17:05

admin's gravatar image

0★admin ♦♦
15.9k347484508
accept rate: 35%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,539
×809
×14
×1

question asked: 26 Nov '12, 17:05

question was seen: 1,126 times

last updated: 26 Nov '12, 17:05