Page 2 of 4
10720
Posted: Thu Sep 23, 2004 5:32 pm
by 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 
Posted: Thu Sep 23, 2004 9:20 pm
by anupam
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.
Re: 10720
Posted: Thu Sep 23, 2004 9:29 pm
by anupam
schindlersp wrote:
what is the init value of vImp?
what sort have you used?
10720
Posted: Thu Sep 23, 2004 11:18 pm
by 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;
}
Posted: Thu Sep 23, 2004 11:44 pm
by 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.
10720
Posted: Thu Sep 23, 2004 11:49 pm
by 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
Re: 10720
Posted: Thu Sep 23, 2004 11:56 pm
by anupam
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.
Posted: Fri Sep 24, 2004 7:53 am
by 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
Posted: Fri Sep 24, 2004 10:01 pm
by miras
i made it using simply Brute Force Solution...
may be poor judge data.
Posted: Sat Sep 25, 2004 10:15 am
by sohel
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.
Posted: Thu Sep 30, 2004 11:51 pm
by 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
Posted: Wed Oct 06, 2004 9:26 am
by 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]
Posted: Fri Oct 08, 2004 12:39 am
by 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?
Posted: Fri Oct 08, 2004 8:13 am
by Per
It means no multiple edges, and no loops.
Run time for Havel Hakimi
Posted: Mon Nov 01, 2004 1:44 am
by 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.