GRSEQ - Graphic Sequence
Given an integer sequence d = (d1, . . . , dn) determine if there exists a graph G with permutation of d as its sequence of degrees.
The input consists of a sequence of lines. In the first line you are given t<100 - the number of sequences to analyze. The description of each of the sequences consists of two lines: in the first line you are given one number n<=100000 (the length of the sequence) and in the second line you are given n nonnegative integers (the sequence elements, all of these numbers are smaller than 100000).
For each of the sequences print in a separate line one of the two words: POSSIBLE if such a graph might exists and IMPOSSIBLE in the opposite case.
Input: 4 3 1 2 2 4 3 2 3 2 5 2 2 4 2 2 4 0 0 0 0 Output: IMPOSSIBLE POSSIBLE POSSIBLE POSSIBLE
Input data sizes
t maxn l 1 10 0.4s 2 100 0.4s 3 1000 0.4s 4 10000 0.4s 5 100000 0.4s t - testcase number maxn - the maximum length of the sequence l - time limit
Using the Erdős–Gallai Theorem you will be able to implement a linear time algorithm.
You could try also Social Network Existence - very similar problem with smaller inputs.
@kuszi I checked for the case you mentioned but still getting wa for 1 and 2. Can you please check?
@s1d_3 Please check the case mentioned previously:
@kuszi: I tried Havel Hakimi, and Erdos Gallai. I keep getting WA on 1 and 2. Can you check?
@Jared Deckard Please consider the case:
I got WA on test cases 1 & 2, but AC on 3, 4, & 5. Can n=1?