## 10720 - Graph Construction

Moderator: Board moderators

schindlersp
New poster
Posts: 28
Joined: Tue Aug 03, 2004 8:11 pm
Contact:

### 10720

hi

1:

do 1 to N
v = input;
if (v % 2) vImp = (vImp + 1) % 2;
if (v < 0 || v >= n) negativo = true;

2:

if (vImp == 1 || negativo || (n == 1 && v[1] > 0))
puts("Not possible"); next case;

3:

sort v
check erdos
print result
next case

I hope help u. I get ac in 0.186s

Schindler

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Per wrote:it has to be non-increasing, and its sum has to be even.
What I did for that,
checked the case where the sum is not even.
sort the values in non-increasing order using O(n^2) alg.
Then checked the Erdos and Gallai alg.
and nothing more.
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

### Re: 10720

schindlersp wrote: what is the init value of vImp?
what sort have you used?
"Everything should be made simple, but not always simpler"

schindlersp
New poster
Posts: 28
Joined: Tue Aug 03, 2004 8:11 pm
Contact:

### 10720

sorry, forget say ...

1:

vImp = 0;

2:

use qsort(v+1,n,sizeof(v[0]),comp)

// v + 1 if C or C++ array

int comp (const void* a, const void* b)
{
return *(type*) b - *(type*) a;
}

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Thanks schindlersp. Got AC in 0:00.219s. I had used all the steps u said except vImp which I checked after addition of all the inputs. That is the only reason I think to get such a huge runtime.
"Everything should be made simple, but not always simpler"

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 10720

hi ,
i am getting WA in this . my code passes the tests given by Per . may be i am
doing some thing stupid ...This is What i Did::

[cpp]int d[10002];
int i , r , n ;
int sum , sum2 ;
bool flag , flod;

while(scanf("%d",&n)==1 && n){
sum = 0 ;
flag = flod = false ;
FOR(i,1,n){scanf("%d",&d);if(d < 0 || d>= n){flod=true ;}sum+=d;}

if(flod){printf("Not possible\n");continue ;}

if(sum==0){printf("Possible\n");continue ;}

if(n==1 && sum > 0){printf("Not possible\n");continue ;}
// if(n==1 && d[1]==0){printf("Possible");continue ;}
if(sum&1){printf("Not possible\n");continue ;}
qsort(d,n,sizeof(d[0]),compare);

//than check for Erdos and Gallai algo.

}

[/cpp]
am i missing some thing ??
Regards
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

### Re: 10720

while(scanf("%d",&n)==1 && n){
flod = false ;//flod no need
FOR(i,1,n){scanf("%d",&d);
if(d < 0 || d>= n){flod=true ;}//no need
sum+=d;}

if(flod){printf("Not possible\n");continue ;}//no need

if(sum==0){printf("Possible\n");continue ;}//no need

if(n==1 && sum > 0){printf("Not possible\n");continue ;}

if(sum&1){printf("Not possible\n");continue ;}
qsort(d,n,sizeof(d[0]),compare);// I think it will be d+1
//then check for Erdos and Gallai algo. (you may miss here)
}

[/cpp]
check these.
"Everything should be made simple, but not always simpler"

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
thanx anupam bhai for u help , i got it ac . . i made the mistake in calling the qsort function .
[cpp]
while(scanf("%d",&n)==1 && n){
flod = false ;//flod no need
FOR(i,1,n){scanf("%d",&d);
if(d < 0 || d>= n){flod=true ;}//no need
sum+=d;}

if(flod){printf("Not possible\n");continue ;}//no need

if(sum==0){printf("Possible\n");continue ;}//no need

if(n==1 && sum > 0){printf("Not possible\n");continue ;}

if(sum&1){printf("Not possible\n");continue ;}
qsort(d,n,sizeof(d[0]),compare);// i made the silly mistake here, it will be d+1
//then check for Erdos and Gallai algo. (No Prob)
}[/cpp]

Regards
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
i made it using simply Brute Force Solution...
Remember Never Give Up
Miras

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### may be poor judge data.

Per wrote: If by greedy you mean actually constructing the graph, how fast do you handle the case
Code:
10000 9999 9999 [... and so on ...] 9999
? If not, what do you mean?
My algorithm is something close to O(n^2) and theoritically it should not pass the time limit. but what I did was :
- first sort the degrees in descending order.
- then I greedily assign, for each node, values to the next consecutive nodes.
- and then sort the remaining nodes in nlog(n) time.

that means my algo takes O(n^2log(n) ) time.

I guess the judge data was shallow and there was no data to the limit.
No wonder why everyone is not thinking of the obvious.

marius135
New poster
Posts: 1
Joined: Thu Sep 30, 2004 11:46 pm
Location: Bucharest Romania
Contact:
well i took tons of WA
and the reason was that i misunderstood the theroem and understood the sum in the right is dum of min(d,i])
i changed that and i still got WA i took the thing with fewer steps and put the program to work till n-1 and finally after 1h.30 i got ac in 0.200 you should be carefull do what you are told no smarstuff except countsort and that's all

Frostina
New poster
Posts: 23
Joined: Mon Dec 15, 2003 5:21 am
why do i always get wa?
i've tried all the test data above and got the same answer..

[c]#include <stdio.h>
#include <stdlib.h>
#define NN 10000
int comp(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int main(void) {
int not, j, tmp, big;
int i, n, sum, v[NN];
while (scanf("%d", &n)==1) {
if (!n) break;
for (i=sum=not=0;i<n;i++) {
scanf("%d", &v);
if (v<0||v>n)
not = 1;
sum+=v;
}
/* the sum should always be even */
if ((sum&1)||(n==1&&sum)||(not)) {
puts("Not possible");
continue;
}
/* if sum = zero, it surely is a graph */
if (!sum) {
puts("Possible");
continue;
}
/* sort it */
qsort (v, n, sizeof(int), comp);
/* Erdos and Gallai's algorithm */
for (i=tmp=0;i<n-1;i++) {
tmp+=v;
if (v>i) big = (n-i-1)*(i+1);
else big = sum-tmp;
if (tmp>i*(i+1)+big) {
not = 1;
break;
}
}
if (not) puts("Not possible");
else puts("Possible");
}
return 0;
} [/c]

matrix2
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:
In this problem we are talking about simple graph which does not have same endpoints for more than one edge, and also does not have edges with the same endpoint.
what does it mean?
Is the graph directed?
Things are simple, but we make them complex.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
It means no multiple edges, and no loops.

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

### Run time for Havel Hakimi

Abi, don't know how you implemented the Havel Hakimi but I'm getting ACC using Havel Hakimi in 0.5 sec and there is even room for some optimization.