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

Code: Select all

```
Case #1:
1.500
0.250
0.500
infinity
infinity
0.000
0.000
0.000
```

**Moderator:** Board moderators

I handled self-loop and multiple edges. Is it necessary?

Is my output correct for this case:
My output:
[EDIT:] Just solved. It was my logical fault.

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

Code: Select all

```
Case #1:
1.500
0.250
0.500
infinity
infinity
0.000
0.000
0.000
```

Does the solution involve solving a system of linear equations.

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

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

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

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

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

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

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?

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.

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

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

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

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