Problem Link:
Contest
Practice
Author: amankedia1994
Tester: legend-killer
Editorialist: sumeet_varma
Difficulty:
Easy - Medium
Pre-requisites: - Bipartite Graphs
Problem: Given an acyclic graph with N nodes and E undirected edges and degree of every node is < 3, find the maximum number of edges that can be added, such that there is no cycle of odd length in the final graph.
Quick Explanation: Answer is always n^2/4 - m.
Explanation:
We want that the final graph should not have any cycle of odd length.
“A graph is bipartite if and only if it does not contain an odd cycle”.
Thus we want out final graph to be bipartite.
If a bipartite graph is divided into two pieces, say of size p and q, where p + q = n. Then the maximum number of edges is p*q. Using calculus we can deduce that this product is maximal when p = q or |p – q| <= 1, in which case it is equal to p*q = n^2/4.
Thus our final graph has upper bound of number of edges as n^2/4. So our answer has upper bound of number of edges as n^2/4 – m.
Let’s see how we can always achieve this.
For an acyclic graph with degree of all vertices < 3, the only possible shape of each component is a linear chain of vertices with size >= 1 and size <= n.
To get maximal ans, we want that |p – q| <= 1 where p and q are sizes of bipartites.
We will prove that we can get maximum ans by induction.
Initially p = q = 0.
Suppose we are processing kth chain of vertices.
Let x be number of vertices in kth chain.
Case 1: x is even.
If x is even, we can add x/2 vertices (all vertices at even positions in the chain) to p and x/2 vertices (all vertices at odd position in the chain) to q and there would be no change to |p – q|. We can do this because each edge in chain is between a vertex with even position and a vertex with odd position.
Case 2: x is odd.
In this case, we can add x/2 + 1 vertices to one part and x/2 vertices to other part. This changes |p – q| by 1. But still we can maintain |p – q| <= 1. Consider following three cases.
Case 2a: p = q.
We add x/2 + 1 to p and x/2 to q. So p – q = 1 and |p – q| <= 1
Case 2b: p – q = -1
We add x/2 + 1 to p and x/2 to q. So p – q = 0 and |p – q| <= 1
Case 2c: p – q = 1
We add x/2 to p and x/2 + 1 to q. So p – q = 0 and |p – q| <= 1
Thus after adding each chain in our bipartite we can maintain |p – q| <= 1. Also initially |p – q| = 0. Thus we can prove, after adding all chains in bipartite, |p – q| <= 1.
So we can create a complete bipartite graph with p * q = n^2 / 4 edges. So total maximum number of new edges we can add = n^2/4 – m.
Ofcourse all this is for proof. Code would be just to input n,m and print n^2/4 - m.
Kudos _/_