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

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

10720

Post by schindlersp » Thu Sep 23, 2004 5:32 pm

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:

Post by anupam » Thu Sep 23, 2004 9:20 pm

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

Post by anupam » Thu Sep 23, 2004 9:29 pm

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

Post by schindlersp » Thu Sep 23, 2004 11:18 pm

sorry, forget say ... :lol:

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:

Post by anupam » Thu Sep 23, 2004 11:44 pm

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. :lol:
"Everything should be made simple, but not always simpler"

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

10720

Post by Riyad » Thu Sep 23, 2004 11:49 pm

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

Post by anupam » Thu Sep 23, 2004 11:56 pm

Riyad wrote: [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 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"

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

Post by Riyad » Fri Sep 24, 2004 7:53 am

thanx anupam bhai for u help , i got it ac . :D . 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
Riyad
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

Post by miras » Fri Sep 24, 2004 10:01 pm

i made it using simply Brute Force Solution...
:lol: :oops:
Remember Never Give Up
Regrads
Miras

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

may be poor judge data.

Post by sohel » Sat Sep 25, 2004 10:15 am

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

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:

Post by marius135 » Thu Sep 30, 2004 11:51 pm

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

Post by Frostina » Wed Oct 06, 2004 9:26 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]
Thanks for your help ! ;)

matrix2
New poster
Posts: 19
Joined: Wed Jul 21, 2004 11:14 am
Location: Suceava, Romania
Contact:

Post by matrix2 » Fri Oct 08, 2004 12:39 am

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

Post by Per » Fri Oct 08, 2004 8:13 am

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

Post by muvee » Mon Nov 01, 2004 1:44 am

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.

Post Reply

Return to “Volume 107 (10700-10799)”