10720 - Graph Construction

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

10720 - Graph Construction

Post by abishek » Wed Sep 22, 2004 5:28 am

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

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Wed Sep 22, 2004 8:39 am

can u tell me more about your method... bcouse i keep Wa in 0.4 sec. ;-(
Remember Never Give Up
Regrads
Miras

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Sep 22, 2004 9:24 am

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

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Wed Sep 22, 2004 10:30 am

After the contest, I looked it up and found the Erd

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Sep 22, 2004 11:02 am

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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Wed Sep 22, 2004 11:29 am

it cleared all of them but still WA using erdos galloi:-( dunno what to do.

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

Post by pingus » Wed Sep 22, 2004 12:12 pm

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
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Sep 22, 2004 12:32 pm

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. :)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Sep 22, 2004 12:57 pm

The first number in the line (5) is the number of nodes, not the degree of the first node :lol:

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Sep 22, 2004 2:16 pm

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Sep 22, 2004 6:01 pm

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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Wed Sep 22, 2004 9:35 pm

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Sep 22, 2004 10:30 pm

Hi abishek, I used Erdos and Gallai theorem to get AC and got the place just after U :D
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"

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Thu Sep 23, 2004 5:07 am


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

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Thu Sep 23, 2004 3:38 pm

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... 8)

Ciao!!!

Claudio

Post Reply

Return to “Volume 107 (10700-10799)”