PROBLEM LINK:Author: Bhuvnesh Jain Tester: Bhuvnesh Jain Editorialist: Bhuvnesh Jain DIFFICULTY:MEDIUM PREREQUISITES:Sorting, Binary Search, ErdosGallai Theorem, Prefix Sums PROBLEM:Given the degrees of the vertices, fins whether it is possible to construct a simple undirected graph from it or not. EXPLANATION:By ErdosGallai's theorem, A seqeuence of nonnegative integers $d_1 \geq d_2 \geq \cdots \geq d_n$ can be represented as the degree sequence of a finite simple undirected graph on n vertices iff $\sum_{i=1}^{n} {d_i}$ is even and the following inequality holds for all k in $1 \leq k \leq n$. $\sum_{i=1}^{k} {d_i} \leq k{(k1)} \ + \ \sum_{i=k+1}^{n} {min(d_i, k)} $. The above inequality can be implemented easily using Prefix sums and binary search after the sequence is sorted in descending order. Here is the logic behind my implementation. The LHS of the inequality can be found using prefix sums in O(1). The first part of the RHS can be found using simple multiplication in O(1). For the second part in RHS, we use a mix of binary search and prefix sums. First we find, using binary search the largest value just smaller than k. Now for all the indices below it, they will contribute a sum equal $\sum {a_i}$ which can again be found using prefix sums. All the remaining numbers i.e. greater than equal to $a_i$ will contribute k to the sum i.e. a total of k . x, where x is the number of numbers greater than equal to k. COMPLEXITYO(nlogn) AUTHOR'S SOLUTION:Author's solution can be found here. asked 26 Mar '16, 02:17
