10720  Graph Construction
Moderator: Board moderators
Frozen.
Greetings!
Can anyone tell me the logic on a negative degree of a vertice?
Will it be a valid input for this problem?
Thanks in advance!
Can anyone tell me the logic on a negative degree of a vertice?
Will it be a valid input for this problem?
Thanks in advance!
_.
What wrong?
var c:boolean;e,i,m,s,t,v:longint;
begin
repeat
read(v);
if v=0 then break;
s:=0;c:=true;m:=0;t:=0;
for i:=1 to v do begin read(e);
if e<0 then c:=false;
if e>0 then inc(t);
if e>m then m:=e;
s:=(s+(e mod 2))mod 2;
end;
if t>0 then if m>t1 then c:=false;
if c and (s=0) then writeln('Possible') else writeln('Not possible');
until false;
end.
begin
repeat
read(v);
if v=0 then break;
s:=0;c:=true;m:=0;t:=0;
for i:=1 to v do begin read(e);
if e<0 then c:=false;
if e>0 then inc(t);
if e>m then m:=e;
s:=(s+(e mod 2))mod 2;
end;
if t>0 then if m>t1 then c:=false;
if c and (s=0) then writeln('Possible') else writeln('Not possible');
until false;
end.
10720  Graphic Sequence  WA
I don't uderstand why I have WA. I use Erdos and Gallai (1960) theorem. At first I check if the sum is odd, if there is element bigger than n or if there is a negative element.
Than I sort the degree sequence and used two index trees to implement Erdos and Gallai (1960) theorem. Help me please Or at least give me some tests
Than I sort the degree sequence and used two index trees to implement Erdos and Gallai (1960) theorem. Help me please Or at least give me some tests
Code: Select all
const ogr = 16383;
const ogr2 = 10000;
var a, tree1, tree2 : array[0..ogr] of longint;
otg : array[0..ogr2] of byte;
s1, s2, r, s, fl, i, j, k, l, o, p, m, n, vr : longint;
procedure qsort(l, r : longint);
var i, j, x : longint;
begin
i := l; j := r; x := a[(i + j) div 2];
repeat
while a[i] > x do inc(i);
while a[j] < x do dec(j);
if i <= j then
begin
k := a[i];
a[i] := a[j];
a[j] := k;
inc(i);
dec(j);
end;
until i > j;
if i < r then qsort(i, r);
if j > l then qsort(l, j);
end;
procedure insert(k, b, c, fl : longint);
var m : longint;
begin
m := b + (c div 2);
if m = k then
begin
if fl = 1 then inc(tree1[m])
else if fl = 2 then inc(tree2[m], k);
exit;
end
else if k < m then
begin
if fl = 1 then inc(tree1[m])
else if fl = 2 then inc(tree2[m], k);
insert(k, b, c div 2, fl);
end
else insert(k, m, c div 2, fl);
end;
procedure delete(k, b, c, fl : longint);
var m : longint;
begin
m := b + (c div 2);
if m = k then
begin
if fl = 1 then dec(tree1[m])
else if fl = 2 then dec(tree2[m], k);
exit;
end
else if k < m then
begin
if fl = 1 then dec(tree1[m])
else if fl = 2 then dec(tree2[m], k);
delete(k, b, c div 2, fl);
end
else delete(k, m, c div 2, fl);
end;
function less(k, b, c, fl : longint) : longint;
var m : longint;
begin
m := b + (c div 2);
if m = k then
begin
if fl = 1 then less := tree1[m]
else less := tree2[m];
exit;
end
else if k > m then
begin
if fl = 1 then less := tree1[m] + less(k, m, c div 2, fl)
else less := tree2[m] + less(k, m, c div 2, fl);
end
else less := less(k, b, c div 2, fl);
end;
procedure clear;
var i : longint;
begin
for i := 0 to ogr do
tree1[i] := 0;
end;
begin
repeat
read( n);
fl := 0;
s := 0;
if n = 0 then break;
inc(vr);
for i := 1 to n do
begin
if i < n then read(a[i])
else readln(a[i]);
s := s + a[i];
if (a[i] >= n) or (a[i] < 0) then fl := 1;
end;
if (n = 1) and (a[1] > 0) then fl := 1;
if fl = 1 then otg[vr] := 1
else
begin
qsort(1, n);
s1 := 0;
s2 := 0;
for i := 1 to n do
begin
insert(a[i], 0, ogr + 1, 1);
insert(a[i], 0, ogr + 1, 2);
end;
for r := 1 to n  1 do
begin
s1 := s1 + a[r];
delete(a[r], 0, ogr + 1, 1);
delete(a[r], 0, ogr + 1, 2);
s2 := 0;
s2 := less(r, 0, ogr + 1, 2);
l := 0;
l := less(r, 0, ogr + 1, 1);
k := (n  r)  l;
k := k * r;
s2 := s2 + k;
if s1 > r * (r  1) + s2 then fl := 1;
end;
delete(a[n], 0, ogr + 1, 1);
delete(a[n], 0, ogr + 1, 2);
if fl = 1 then otg[vr] := 1;
end;
until false;
for i := 1 to vr do
if otg[i] = 1 then writeln('Not possible')
else writeln('Possible');
end.

 Learning poster
 Posts: 91
 Joined: Tue May 31, 2005 2:01 pm
 Location: Russia
i use the ErdosGallai theorem. Simple check conditions of ErdosGallai theorem does not work. Then i has added next condition
And it has worked!
Code: Select all
if((SumOfVertex % 2)(SumOfVertex > NonNullVertex*(NonNullVertex  1)))

 New poster
 Posts: 5
 Joined: Sun Jan 30, 2005 2:27 pm
10720 WA
Could anyone tell me the content of the erdosgallai theorem? thanks.
10720  wanna great help against the holy word WA
im so much frustated that i just droped my code here.
i check all the critical inputs found in the board all r right but still
getting the holy word WA. for lucky(!) 7 times.
#include<stdio.h>
long number,i,num[20000],ver[20000],carry,p;
void main()
{
while(scanf("%ld",&number),number!=0)
{
for(i=0,p=0;i<number;i++)
{scanf("%ld",&num);ver=0;
if(num<0)
p=1;
}
if(p==1(number==1&&num[0]>0))
{printf("Not possible\n");continue;}
for(i=0;i<number1;i++)
{
if(ver>num)
{
carry=vernum;
ver=num;
}
else if(ver==num[i])
{
carry=num[i];
}
else
{
carry=num[i]ver[i];
}
ver[i+1]+=carry;
ver[i]+=num[i];
}
if(num[i]==ver[i])
printf("Possible\n");
else
printf("Not possible\n");
}
}
plz check my code.
im here just distributing the edges among the nodes and checking the last node.
i check all the critical inputs found in the board all r right but still
getting the holy word WA. for lucky(!) 7 times.
#include<stdio.h>
long number,i,num[20000],ver[20000],carry,p;
void main()
{
while(scanf("%ld",&number),number!=0)
{
for(i=0,p=0;i<number;i++)
{scanf("%ld",&num);ver=0;
if(num<0)
p=1;
}
if(p==1(number==1&&num[0]>0))
{printf("Not possible\n");continue;}
for(i=0;i<number1;i++)
{
if(ver>num)
{
carry=vernum;
ver=num;
}
else if(ver==num[i])
{
carry=num[i];
}
else
{
carry=num[i]ver[i];
}
ver[i+1]+=carry;
ver[i]+=num[i];
}
if(num[i]==ver[i])
printf("Possible\n");
else
printf("Not possible\n");
}
}
plz check my code.
im here just distributing the edges among the nodes and checking the last node.

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
dear tanvir,
I dont seem to understand your algorithm clearly (or why it should work). But I believe your code does not pass the following input
3 2 2 2
2 1 1
Your o/p:
Possible
Not Possible
Corect o/p:
Possible
Possible
It seems that your code has some kind of initialization problem
You can find an easy description of ErdosGallai in the following link:
http://www.math.rutgers.edu/~sujith/eg.pdf
I dont seem to understand your algorithm clearly (or why it should work). But I believe your code does not pass the following input
3 2 2 2
2 1 1
Your o/p:
Possible
Not Possible
Corect o/p:
Possible
Possible
It seems that your code has some kind of initialization problem
You can find an easy description of ErdosGallai in the following link:
http://www.math.rutgers.edu/~sujith/eg.pdf
Where's the "Any" key?
What's a "degree sequence degree sequence"?Erdos and Gallai (1960) proved that a degree sequence degree sequence {d_1,...,d_n} is graphic iff the sequence obeys the property ....
Does the sequence needs to be sorted?
Also, to compute sum(min(r,d), i=r+1..n), is there a sort cut to get amortized O(1) ? If not, then wouldn't the whole thing be O(n^2)? If that's the case one might as well use sorting (we can sort in linear time here).

 New poster
 Posts: 24
 Joined: Sun Nov 12, 2006 3:38 pm
Solution to this case
Can someone show me a graph for the case below?
10 3 3 3 3 3 3 3 3 3 3
(the first number is the number of vertices)
I'm trying to solve using my own method, but I can't see why the above case is possible (it was posted on the first page of this topic).
Thanks.
10 3 3 3 3 3 3 3 3 3 3
(the first number is the number of vertices)
I'm trying to solve using my own method, but I can't see why the above case is possible (it was posted on the first page of this topic).
Thanks.