×

# COPR16E: Editorial

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

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.

O(nlogn)

# AUTHOR'S SOLUTION:

Author's solution can be found here.

6★likecs
3.7k2380
accept rate: 9%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,679
×2,595
×593
×32
×1

question asked: 26 Mar '16, 02:17

question was seen: 371 times

last updated: 29 Mar '16, 16:14