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 off-by-one 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 Three-headed, 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.
![:)](./images/smilies/icon_smile.gif)
-
- 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 mis-understood the quote, and it means: only check if r==1 or if d_r != d_(r-1). 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 <= n-1.
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
(n-i+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
(n-i+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 ![:D](./images/smilies/icon_biggrin.gif)
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![:)](./images/smilies/icon_smile.gif)
check your algorithm whether you missing any step. btw, I am also interested in the greedy method. Sohel, will you describe more?
![:D](./images/smilies/icon_biggrin.gif)
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
![:)](./images/smilies/icon_smile.gif)
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 mis-understood the quote, and it means: only check if r==1 or if d_r != d_(r-1). 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 <= n-1.
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...
![8)](./images/smilies/icon_cool.gif)
Ciao!!!
Claudio