PROBLEM LINK:
Author: Sai Sandeep
Tester: Aditya Shah
DIFFICULTY:
HARD
PREREQUISITES:
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