You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 26 Mar '16, 02:17

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 29 Mar '16, 16:14

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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