10720 - Graph Construction

[_.B._]

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!

[QulinXao]

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>t-1 then c:=false;

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

until false;
end.

[vedex]

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

[sohel]

unfortunately, this problem can be solved using 'greedy approach' .

[vedex]

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]

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]

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

[tanvir]

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<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]

http://online-judge.uva.es/board/viewtopic.php?t=6464

You may find the Erd

[tanvir]

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]

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 Erdos-Gallai in the following link:
http://www.math.rutgers.edu/~sujith/eg.pdf

[yiuyuho]

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]

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]

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]

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.