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

×

HIKARU - Editorial

PROBLEM LINK:

Practice

Contest

Author: Sai Sandeep Tester: Aditya Shah

DIFFICULTY:

HARD

PREREQUISITES:

Network Flows

PROBLEM:

Given sum of degrees of each vertex of graph, check if such a weighted graph can exist, if the upper bound on weight of edge between vertices i and j is i^j ( Bitwise xor )

QUICK EXPLANATION:

Check if the sum of degrees is even.

Construct a flow network with N vertices on left and right, edge with capacity i ^ j from i th vertex on left to jth vertex on right. Add a source and sink, with capacities equal to sum of degrees of vertices on left and right. Check if the flow equals the sum of degrees.

EXPLANATION:

First of all, the sum of degrees of the graph is even. See this

From here onwards, we use $c_{ij}$ to denote i^j, $d_i$ to denote sum of degrees of i. Lets construct a flow network, with N vertices on left and N vertices on right, edge of capacity $c_{ij}$ from i on left to j on right. Add a source on left and edges of capacity $d_i$ from source to i on left. Add a sink on right and edges of capacity $d_i$ from i on right to sink.

Suppose that there is such a graph satisfying the conditions in the problem, then the maximum flow in this graph is equal to sum of $d_i$, since we can send $w_{ij}$ on the edge between i on left and j on right.

Is the converse true ? Why can't it possibly not hold ? It's because in our flow network, $e_{ij}$ and $e_{ji}$ need not be same. But we can still consider $w_{ij} = (e_{ij} + e_{ji} )/2$ and it will satisfy the sum of degrees criterion. But the problem with this is that we no longer have integral weights on the edges. It can be a fraction, but still integral multiple of 1/2.

It turns out that if the sum of degrees is even, this flow can be modified to get a flow in which we don't have these non-integral weights. For example, if there is an even cycle with non-integral weights, we can add 1/2 to alternate edges and subtract 1/2 from rest to get rid of these non-integral weights. If we have two odd cycles with non-integral flows, we can adjust the flow from one cycle to other to get rid of all the non-integral ones. See this writeup for more formal proof.

Of course, we need not code all that, we just need to check that sum of degrees is even. But to arrive at that, we need above observations.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here
Tester's solution can be found here

This question is marked "community wiki".

asked 30 Sep '16, 12:12

harrypotter192's gravatar image

6★harrypotter192
116
accept rate: 0%

edited 20 Mar '17, 22:18

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×15,852
×1,359
×374
×114

question asked: 30 Sep '16, 12:12

question was seen: 783 times

last updated: 20 Mar '17, 22:18