10720 - Graph Construction

[schindlersp]

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]

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.

[anupam]

what is the init value of vImp?
what sort have you used?

[schindlersp]

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]

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.

[Riyad]

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

[anupam]

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

[Riyad]

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
Riyad

[miras]

i made it using simply Brute Force Solution...

[sohel]

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]

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]

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]

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?

[Per]

It means no multiple edges, and no loops.

[muvee]

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.