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

- little joey
- 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`

- little joey
- 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.

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

(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

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

Ciao!!!

Claudio