10720 - Graph Construction

[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

[miras]

can u tell me more about your method... bcouse i keep Wa in 0.4 sec. ;-(

[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

[abishek]

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

[Per]

- 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

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]

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

[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
}

[sohel]

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]

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

[Per]

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]

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.

[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

[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?

[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

[CDiMa]

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