10720  Graph Construction
Moderator: Board moderators
10720  Graph Construction
hi,
i used the havel hakimi theorem and got ac in 6 secs. Then i tried the erodos galloi theorem.
but i am getting WA? can anyone tell me if there is a special case to handle with the erdos galloi theorem. I use the version found here
http://mathworld.wolfram.com/GraphicSequence.html
thanks
abi
i used the havel hakimi theorem and got ac in 6 secs. Then i tried the erodos galloi theorem.
but i am getting WA? can anyone tell me if there is a special case to handle with the erdos galloi theorem. I use the version found here
http://mathworld.wolfram.com/GraphicSequence.html
thanks
abi
I mainly made some mistakes in calculating sum_{r+1 <= i <= n} min(r, d_i). Well, you could try this I/O:abishek wrote: the theorem is a great soure for potential offbyone errors.
may be this is what i am doing?? can you give me more hints towards a possible error, if you had made the same?
Code: Select all
4 0 3 2 3
3 2 2 2
2 1 1
3 1 1 0
5 1 4 3 3 3
1 0
1 2
2 0 0
10 0 0 0 0 0 0 0 0 0 0
10 3 3 3 3 3 3 3 3 3 3
6 4 4 4 3 2 1
8 6 6 5 5 4 3 2 1
0
Code: Select all
Not possible
Possible
Possible
Not possible
Possible
Possible
Not possible
Possible
Possible
Possible
Possible
Possible
Typically the base name is Monkey. Ideally it is Threeheaded, but it varies depending on whether people have other things to do or not.abishek wrote:btw: whats your team name?
Where did you get the 6th node. The graph is invalid.pingus wrote: Why the test case:
5 3 2 3 2 1
is not possible
It is not a valid graph ?
{
1>2, 1>3, 1>4, 1>5, 1>6
2>3, 2>4,
4>5
}
And why is everyone using complex algorithms. I applied greedy and got it AC in 0.35 seconds. Infact our team was the first to solve it. It took aprx. 20 minutes.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
If by greedy you mean actually constructing the graph, how fast do you handle the casesohel wrote:And why is everyone using complex algorithms. I applied greedy and got it AC in 0.35 seconds. Infact our team was the first to solve it. It took aprx. 20 minutes.
Code: Select all
10000 9999 9999 [... and so on ...] 9999

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Abishek:
From the link you mention
Also don't try to shortcut the second summation (the one with the min() function) with something like SUM2(r+1) = SUM2(r)  min(r,d_(r+1)); although it looks tempting on first sight, it's wrong. You can of course shortcut the first summation by using SUM1(r+1) = SUM1(r) +d_(r+1), but it will only gain you a couple of milliseconds.
From the link you mention
But I get WA when I use that. Only after checking the full range I get Accepted. But maybe I misunderstood the quote, and it means: only check if r==1 or if d_r != d_(r1). Anyhow, it hardly saves any time.Tripathi and Vijay (2003) showed that this inequality need be checked only for as many r as there are distinct terms in the sequence, not for all 1 <= r <= n1.
Also don't try to shortcut the second summation (the one with the min() function) with something like SUM2(r+1) = SUM2(r)  min(r,d_(r+1)); although it looks tempting on first sight, it's wrong. You can of course shortcut the first summation by using SUM1(r+1) = SUM1(r) +d_(r+1), but it will only gain you a couple of milliseconds.
actually the only shorcut in the second summation i use is as follows
i sorted the degree sequence and then when i find d>r, i just add
(ni+1)*r to the second sum.
i tried without that too,but that got a tle.
so i think i must be doing some very trivial mistake some where.
sohel:
what is this greedy algorithm? The havel hakimi theorem tries to do this only, but doing that took me a whooping 6 secs in the judge. I think i must have gone very bad in implementing it.
bye
abi
i sorted the degree sequence and then when i find d>r, i just add
(ni+1)*r to the second sum.
i tried without that too,but that got a tle.
so i think i must be doing some very trivial mistake some where.
sohel:
what is this greedy algorithm? The havel hakimi theorem tries to do this only, but doing that took me a whooping 6 secs in the judge. I think i must have gone very bad in implementing it.
bye
abi
Hi abishek, I used Erdos and Gallai theorem to get AC and got the place just after U
What I did (check yours):
1. sort the input
2. there is no negative value
3. check for degree sequence degree sequence as per said
4. if(n==1 && a[1]>0){printf("Not possible\n");continue;}
5. checked the theorem of Erdos and Gallai
6. Got AC
check your algorithm whether you missing any step. btw, I am also interested in the greedy method. Sohel, will you describe more?
What I did (check yours):
1. sort the input
2. there is no negative value
3. check for degree sequence degree sequence as per said
4. if(n==1 && a[1]>0){printf("Not possible\n");continue;}
5. checked the theorem of Erdos and Gallai
6. Got AC
check your algorithm whether you missing any step. btw, I am also interested in the greedy method. Sohel, will you describe more?
"Everything should be made simple, but not always simpler"
I got accepted using Tripathi and Vijay (although it saves you very little time). It seems that you check the first d_r of a group of equal terms, while Tripathi and Vijay say you have to check the last one.little joey wrote:Abishek:
From the link you mentionBut I get WA when I use that. Only after checking the full range I get Accepted. But maybe I misunderstood the quote, and it means: only check if r==1 or if d_r != d_(r1). Anyhow, it hardly saves any time.Tripathi and Vijay (2003) showed that this inequality need be checked only for as many r as there are distinct terms in the sequence, not for all 1 <= r <= n1.
Anyway there's another improvement that significantly enhanced my runnnig time (a cut of about 40%). I expected that input data could easily induce worst case performance on qsort. So I dropped qsort and there you go...
Ciao!!!
Claudio