Page 1 of 4
10720 - Graph Construction
Posted: Wed Sep 22, 2004 5:28 am
by abishek
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
Posted: Wed Sep 22, 2004 8:39 am
by miras
can u tell me more about your method... bcouse i keep Wa in 0.4 sec. ;-(
Posted: Wed Sep 22, 2004 9:24 am
by Per
During the contest, we got AC in 1.4 secs with a really stupid test solution which basically tried to construct the graph in O(E*log n) time.
After the contest, I looked it up and found the Erd
Posted: Wed Sep 22, 2004 10:30 am
by abishek
After the contest, I looked it up and found the Erd
Posted: Wed Sep 22, 2004 11:02 am
by Per
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?
I mainly made some mistakes in calculating sum_{r+1 <= i <= n} min(r, d_i). Well, you could try this I/O:
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
Output:
Code: Select all
Not possible
Possible
Possible
Not possible
Possible
Possible
Not possible
Possible
Possible
Possible
Possible
Possible
abishek wrote:btw: whats your team name?
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.
Posted: Wed Sep 22, 2004 11:29 am
by abishek
it cleared all of them but still WA using erdos galloi:-( dunno what to do.
Posted: Wed Sep 22, 2004 12:12 pm
by pingus
hello,
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
}
Posted: Wed Sep 22, 2004 12:32 pm
by sohel
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
}
Where did you get the 6th node. The graph is invalid.
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.
Posted: Wed Sep 22, 2004 12:57 pm
by little joey
The first number in the line (5) is the number of nodes, not the degree of the first node
Posted: Wed Sep 22, 2004 2:16 pm
by Per
sohel 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.
If by greedy you mean actually constructing the graph, how fast do you handle the case
Code: Select all
10000 9999 9999 [... and so on ...] 9999
? If not, what do you mean?
Posted: Wed Sep 22, 2004 6:01 pm
by little joey
Abishek:
From the link you mention
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.
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.
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.
Posted: Wed Sep 22, 2004 9:35 pm
by abishek
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
Posted: Wed Sep 22, 2004 10:30 pm
by anupam
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?
Posted: Thu Sep 23, 2004 5:07 am
by abishek
3. check for degree sequence degree sequence as per said
can you tell me what this is. I checked for the special case of n==1 and still got WA.
bye
abi
Posted: Thu Sep 23, 2004 3:38 pm
by CDiMa
little joey wrote:Abishek:
From the link you mention
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.
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.
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.
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