## 10828 - Back to Kernighan-Ritchie

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### 10828 - Back to Kernighan-Ritchie

I handled self-loop and multiple edges. Is it necessary?
Is my output correct for this case:

Code: Select all

``````8
1 1 1 1 1 2 1 3 1 3 1 4 4 5 5 4 6 7 7 6 8 1 0 0
8 1 2 3 4 5 6 7 8
0``````
My output:

Code: Select all

``````Case #1:
1.500
0.250
0.500
infinity
infinity
0.000
0.000
0.000``````
[EDIT:] Just solved. It was my logical fault.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Need A hint

Does the solution involve solving a system of linear equations.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### Re: Need A hint

shamim wrote:Does the solution involve solving a system of linear equations.
Yes.

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm
Hi, is your sample IO correct?

I got 1.333 for point 1, 0.167 for point 2, and 0.333 for point 3, and keep WAing..

Can you explain me more how you got those values?

Thx

Oops.. forget about self loop :S, hehe, I'll try again first

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm
Hmm.. I got that result already, but still get WA...
Any more testcase? What I did is find the value of all edges by using linear equations..
Before that I precompute the zero and infinity case.

thx

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Your approach is exactly the same as mine.
These are the test cases which I failed:

Code: Select all

``````3
1 2 2 3 3 2 0 0
3 1 2 3
5
1 2 2 3 3 2 3 4 4 5 5 4 0 0
5 1 2 3 4 5
3
1 2 1 3 2 3 3 3 0 0
3 1 2 3
0``````
Correct output:

Code: Select all

``````Case #1:
1.000
infinity
infinity
Case #2:
1.000
2.000
2.000
infinity
infinity
Case #3:
1.000
0.500
infinity``````

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm
hmm.. I got correct on your testcases...
I think I got precision error, when I use such a big testcase the results become funny :S

anyway thx

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. If we have 100 nodes, where the first 99 are all mutualy connected and also connected to node 100 (which has no outgoing edges), then there would be 99*98 + 99 = 9801 edges.
We would then have 100 + 99*((98*97)/2) = 470647 equations with 9801 unknowns.
How are we going to store that monster, let alone solve it in time?
Or am I missing something?

The easy answer would be: "there are no such cases in the input", but that would mean that the problem description is incomplete.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Forget my previous posting. I was being stupid...

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I was getting tons of WAs when I made zero comparison as
fabs(x) < 1e-15, but when I changed it to fabs(x) < 1e-8, I got AC.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
shamim wrote:I was getting tons of WAs when I made zero comparison as
fabs(x) < 1e-15, but when I changed it to fabs(x) < 1e-8, I got AC.
I assume that it is due to the fact that 1e-15 is already quite on the boundary of the precision of double. The precision error in your computations can easily be larger than that.

A good rule of thumb is to assume that the first half of the digits your floating point data type contains are correct.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I'm getting desparate ...

Can somebody look at my code and give me an input for which it fails?

Code: Select all

``````#include <stdio.h>

#define EPSILON (1.0e-8)

--- CODE DELETED ---
Finally got the red letters by setting EPSILON to 1.0e-11

``````
Last edited by little joey on Sat Sep 24, 2005 4:24 pm, edited 1 time in total.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
It may completely due to precision error. I tried to feed million of random input to yours and mine. There are many differences and here are two small input which we give different output:

Code: Select all

``````5
1 4 1 4 5 1 1 2 5 5 2 5 5 3 1 4 5 2 3 1 3 4 3 2 0 0
5 1 2 3 4 5
5
2 4 3 4 1 2 2 3 3 2 2 1 3 3 1 3 1 5 1 3 0 0
5 1 2 3 4 5
0``````

Code: Select all

``````Case #1:
1.250
0.563
0.187
1.000
0.750
Case #2:
1.250
0.750
1.312
0.687
0.313``````
My output:

Code: Select all

``````Case #1:
1.250
0.563
0.188
1.000
0.750
Case #2:
1.250
0.750
1.313
0.688
0.313``````
My output with 10 digits after decimal point:

Code: Select all

``````Case #1:
1.2500000000
0.5625000000
0.1875000000
1.0000000000
0.7500000000
Case #2:
1.2500000000
0.7500000000
1.3125000000
0.6875000000
0.3125000000``````
When I deal with floating point output, I often print the value +1e-9. If I remove the +1e-9 from my code, it will generate the same result as yours.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thank you very much, Cho.
I finally got AC, but I had to set both EPSILON and the print-correction to 1e-11 (1e-10 didn't) work.
I realy hate it when precision is so critical.