10720 - Graph Construction

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Frozen.

Greetings!
Can anyone tell me the logic on a negative degree of a vertice? Will it be a valid input for this problem?

_.

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

What wrong?

var c:boolean;e,i,m,s,t,v:longint;
begin
repeat
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>t-1 then c:=false;

if c and (s=0) then writeln('Possible') else writeln('Not possible');

until false;
end.

vedex
New poster
Posts: 7
Joined: Sat Jul 02, 2005 8:31 pm

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 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
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])
s := s + a[i];
if (a[i] >= n) or (a[i] < 0) then fl := 1;
end;
if (n = 1) and (a > 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.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
unfortunately, this problem can be solved using 'greedy approach' .

vedex
New poster
Posts: 7
Joined: Sat Jul 02, 2005 8:31 pm
I know it can be solved with greedy. But I want to solve it with this theorem very very much And the only greedy I know works in
O(n.m).

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
i use the Erdos-Gallai theorem. Simple check conditions of Erdos-Gallai theorem does not work. Then i has added next condition

Code: Select all

if((SumOfVertex % 2)||(SumOfVertex > NonNullVertex*(NonNullVertex - 1)))
And it has worked!

ioriyagami
New poster
Posts: 5
Joined: Sun Jan 30, 2005 2:27 pm

10720 WA

Could anyone tell me the content of the erdos-gallai theorem? thanks.

tanvir
New poster
Posts: 22
Joined: Wed Aug 31, 2005 12:09 pm

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,ver,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))
{printf("Not possible\n");continue;}

for(i=0;i<number-1;i++)
{

if(ver>num)
{
carry=ver-num;
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.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
Where's the "Any" key?

tanvir
New poster
Posts: 22
Joined: Wed Aug 31, 2005 12:09 pm
hi solaris,
thanks for response so early.

i saw the erdos-gallai theorem
i also got WA using that.

perhaps i didnt understand the theorem quite well.

can any one give some brief about erdos-gallai theorem.

also whats the problem with my code.
i think my method is ok also.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
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

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 Erdos-Gallai in the following link:
http://www.math.rutgers.edu/~sujith/eg.pdf
Where's the "Any" key?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Erdos and Gallai (1960) proved that a degree sequence degree sequence {d_1,...,d_n} is graphic iff the sequence obeys the property ....
What's a "degree sequence degree sequence"?

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).

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
It seems that a lot of people are having trouble directly applying Erdos-Gallai, is there some special case that the theorem needs to satisfy?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Wow, I implemnted Erdos-Gallai in linear time and only got a few milliseconds improvement compare to the previous n*(n-1) algorithm. What in the world??!!

viniciusweb
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.