## 10720 - Graph Construction

Moderator: Board moderators

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

### 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

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
can u tell me more about your method... bcouse i keep Wa in 0.4 sec. ;-(
Remember Never Give Up
Miras

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 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
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.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 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
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
}

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
The first number in the line (5) is the number of nodes, not the degree of the first node

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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?

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

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.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
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:
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?
"Everything should be made simple, but not always simpler"

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 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
little joey wrote:Abishek: