COPR16E: Editorial

PROBLEM LINK:

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

DIFFICULTY:

MEDIUM

PREREQUISITES:

Sorting, Binary Search, Erdos-Gallai 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 Erdos-Gallai’s theorem, A seqeuence of non-negative 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{(k-1)} \ + \ \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.

COMPLEXITY

O(nlogn)

AUTHOR’S SOLUTION:

Author’s solution can be found here.