Mock CCC '18 Contest 3 S4 - A Graph Problem

View as PDF

Submit solution


Points: 10
Time limit: 0.6s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given an undirected weighted graph where there is an edge between every pair of distinct vertices of nonnegative integer weight, let a_i be the sum of the weights of the edges incident on vertex i.

Given a sequence of integers b_1 through b_N, determine if it is possible to construct a graph of n vertices such that a_i = b_i for every vertex in the graph.

Constraints

1 \le N \le 50

1 \le b_i \le 10^9

There is no opportunity for partial credit on this problem.

Input Specification

The first line contains a single integer, N.

Each of the next N lines contains a single integer, b_1 through b_N in order.

Output Specification

Output YES if it is possible to construct such a graph. Output NO otherwise.

Sample Input

3
1
1
2

Sample Output

YES

Sample Input

3
1
1
3

Sample Output

NO

Comments


  • 0
    Dan13llljws  commented on Dec. 8, 2019, 6:34 p.m. edited

    It doesnt make sense if you only have one node but you cannot make a graph