10828 - Back to Kernighan-Ritchie

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10828 - Back to Kernighan-Ritchie

Post by Cho » Tue Mar 08, 2005 9:58 am

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.

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

Need A hint

Post by shamim » Sat Mar 12, 2005 11:32 am

Does the solution involve solving a system of linear equations.

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

Re: Need A hint

Post by Cho » Sat Mar 12, 2005 5:05 pm

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

Post by ardiankp » Mon Mar 14, 2005 4:37 am

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 :P

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Post by ardiankp » Mon Mar 14, 2005 5:36 am

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

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

Post by Cho » Mon Mar 14, 2005 6:55 am

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

Post by ardiankp » Mon Mar 14, 2005 11:30 am

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 :)

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

Post by little joey » Mon Mar 14, 2005 1:59 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.

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

Post by little joey » Mon Mar 14, 2005 2:15 pm

Forget my previous posting. I was being stupid...

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

Post by shamim » Tue Mar 15, 2005 7:42 am

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

Post by misof » Wed Mar 16, 2005 5:54 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.

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

Post by little joey » Sat Sep 24, 2005 1:07 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.

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

Post by Cho » Sat Sep 24, 2005 3:10 pm

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
Your output:

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.

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

Post by little joey » Sat Sep 24, 2005 4:29 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.

Thanks again, and hope to help you back!
lj

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

Post by Cho » Sat Sep 24, 2005 4:48 pm

Help me back? I remember you helped me many times already. :D

Post Reply

Return to “Volume 108 (10800-10899)”