Discussion @ 1766. Humpty Dumpty @ Timus Online Judge

quick(YarSU) give me hint [2] // Problem 1766. Humpty Dumpty 20 Apr 2010 17:56

chhung6 Precision? [17] // Problem 1766. Humpty Dumpty 11 Apr 2010 18:27

It seems that the main problem is precision.
If it is so, how could we compute the answer more accurately?
e.g., set what Epsilon threshold for determining a value being 0 ?

Burunduk1 Re: Precision? [15] // Problem 1766. Humpty Dumpty 11 Apr 2010 18:35

There are some methods to solve problem.
1. Gauss. It really has troubles with precision.
2. Method of iterations. It works good, but your implementation should be fast enough and do about 2^50 iterations :)

chhung6 Re: Precision? // Problem 1766. Humpty Dumpty 11 Apr 2010 18:43

Thanks for your reply. :)

I used Gaussian Elimination. Seems it's very difficult to handle the precision...

FZU_O_O Re: Precision? [3] // Problem 1766. Humpty Dumpty 11 Apr 2010 20:15

We tried both methods but failed...
It seems that using iterations could lead to precision problem too..we calc something like mat[64][64],and do mat^(2^60),but it turns out that the value in mat overflows...
Sorry for my poor english-_-

Nikita Glashenko [Samara SAU] Re: Precision? [2] // Problem 1766. Humpty Dumpty 11 Apr 2010 21:19

Just add something like that after each multiplication.

void normalize(double a[][64])
{
    for(int i = 0; i < 64; i++)
    {
        double sum = 0;
        for(int j = 0; j < 64; j++)
            sum += a[i][j];
        for(int j = 0; j < 64; j++)
            a[i][j] /= sum;
    }
}

Kenny_HORROR Re: Precision? // Problem 1766. Humpty Dumpty 11 Apr 2010 21:39

Thanks, it helped me =).

2rf [Perm School #9] Re: Precision? // Problem 1766. Humpty Dumpty 17 Jun 2010 14:26

Thanks a lot, Nikita! This normailze function really helps!

My program needs only 2^26 iterations using it, and without this function i received WA #1 all the time.

Edited by author 17.06.2010 14:28

Chmel_Tolstiy Re: Precision? // Problem 1766. Humpty Dumpty 11 Apr 2010 21:37

I used Gauss. But with BigDecimal.

Victor Barinov (TNU) Re: Precision? // Problem 1766. Humpty Dumpty 11 Apr 2010 23:30

Can you explain why iterations more precize than gauss?
Why you think that it is necessary about 2^50 iterations?

[ONU]Sfairat Re: Precision? [7] // Problem 1766. Humpty Dumpty 13 Apr 2010 03:35

I think that there exists a good alternative to Gaussian elimination - QR - decomposition of the matrix. It's precision, I think, would be good enough because it doesn't change the condition number of the matrix.

bsu.mmf.team Re: Precision? [6] // Problem 1766. Humpty Dumpty 23 Apr 2010 23:22

I tried to solve it as you said. TL #3 ...

[ONU]Sfairat Re: Precision? [5] // Problem 1766. Humpty Dumpty 28 Apr 2010 22:35

QR - decomposition is only a bit slower than Gaussian elimination, and it's also O(n^3)

bsu.mmf.team Re: Precision? [4] // Problem 1766. Humpty Dumpty 4 May 2010 21:24

Could you expalin what is the QR-decomposition? Maybe, I didn't understand you very well.

Sergey Lazarev (MSU Tashkent) Re: Precision? [3] // Problem 1766. Humpty Dumpty 5 May 2010 01:01

http://en.wikipedia.org/wiki/QR_decomposition

bsu.mmf.team Re: Precision? [2] // Problem 1766. Humpty Dumpty 6 May 2010 01:45

Thanks a lot! But I don't understand how could it be useful to avoid big precision troubles with Gauss algorithm.

dAFTc0d3r [Yaroslavl SU] Re: Precision? [1] // Problem 1766. Humpty Dumpty 6 May 2010 10:29

I don't understand too. :-[

Sergey Lazarev (MSU Tashkent) Re: Precision? // Problem 1766. Humpty Dumpty 6 May 2010 11:41

These methods have less calculation errors than Gauss method.
But there is modification of Gauss method which more precise than QR-decomposition methods. In this modification we choose main element from all remaining elements in matrix.

You can read about methods for solving systems of linear algebraic equations in the book: А.А.Амосов "Вычислительные методы для инженеров".
Of course, there are a lot of other sources.

mouse_wireless2 Re: Precision? // Problem 1766. Humpty Dumpty 7 Mar 2018 22:43

Just want to mention that I kept getting WA and after changing double to long double immediately got AC. Maybe it helps

Ade What's the magic in #18 [2] // Problem 1766. Humpty Dumpty 5 Apr 2013 23:35

Zefick WA 16 // Problem 1766. Humpty Dumpty 1 Jun 2010 12:06

AdyghSU TEAM13: Kasparyan, Siunov No subject [1] // Problem 1766. Humpty Dumpty 11 Apr 2010 15:58

OpenGL Question [1] // Problem 1766. Humpty Dumpty 14 Apr 2010 14:55

Discussion of Problem 1766. Humpty Dumpty