Обсуждение @ 1766. Шалтай-Болтай @ Timus Online Judge

quick(YarSU) give me hint [2] // Задача 1766. Шалтай-Болтай 20 апр 2010 17:56

chhung6 Precision? [17] // Задача 1766. Шалтай-Болтай 11 апр 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] // Задача 1766. Шалтай-Болтай 11 апр 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? // Задача 1766. Шалтай-Болтай 11 апр 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] // Задача 1766. Шалтай-Болтай 11 апр 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] // Задача 1766. Шалтай-Болтай 11 апр 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? // Задача 1766. Шалтай-Болтай 11 апр 2010 21:39

Thanks, it helped me =).

2rf [Perm School #9] Re: Precision? // Задача 1766. Шалтай-Болтай 17 июн 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? // Задача 1766. Шалтай-Болтай 11 апр 2010 21:37

I used Gauss. But with BigDecimal.

Victor Barinov (TNU) Re: Precision? // Задача 1766. Шалтай-Болтай 11 апр 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] // Задача 1766. Шалтай-Болтай 13 апр 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] // Задача 1766. Шалтай-Болтай 23 апр 2010 23:22

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

[ONU]Sfairat Re: Precision? [5] // Задача 1766. Шалтай-Болтай 28 апр 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] // Задача 1766. Шалтай-Болтай 4 май 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] // Задача 1766. Шалтай-Болтай 5 май 2010 01:01

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

bsu.mmf.team Re: Precision? [2] // Задача 1766. Шалтай-Болтай 6 май 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] // Задача 1766. Шалтай-Болтай 6 май 2010 10:29

I don't understand too. :-[

Sergey Lazarev (MSU Tashkent) Re: Precision? // Задача 1766. Шалтай-Болтай 6 май 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? // Задача 1766. Шалтай-Болтай 7 мар 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] // Задача 1766. Шалтай-Болтай 5 апр 2013 23:35

Zefick WA 16 // Задача 1766. Шалтай-Болтай 1 июн 2010 12:06

AdyghSU TEAM13: Kasparyan, Siunov No subject [1] // Задача 1766. Шалтай-Болтай 11 апр 2010 15:58

OpenGL Question [1] // Задача 1766. Шалтай-Болтай 14 апр 2010 14:55

Обсуждение задачи 1766. Шалтай-Болтай