ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1766. Humpty Dumpty

Posted by chhung6 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 ?
Re: Precision?
Posted by Burunduk1 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 :)
Re: Precision?
Posted by chhung6 11 Apr 2010 18:43
Thanks for your reply. :)

I used Gaussian Elimination. Seems it's very difficult to handle the precision...
Re: Precision?
Posted by FZU_O_O 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-_-
Re: Precision?
Posted by Nikita Glashenko [Samara SAU] 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;
Re: Precision?
Posted by Chmel_Tolstiy 11 Apr 2010 21:37
I used Gauss. But with BigDecimal.
Re: Precision?
Posted by Kenny_HORROR 11 Apr 2010 21:39
Thanks, it helped me =).
Re: Precision?
Posted by Victor Barinov (TNU) 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?
Re: Precision?
Posted by [ONU]Sfairat 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.
Re: Precision?
Posted by bsu.mmf.team 23 Apr 2010 23:22
I tried to solve it as you said. TL #3 ...
Re: Precision?
Posted by [ONU]Sfairat 28 Apr 2010 22:35
QR - decomposition is only a bit slower than Gaussian elimination, and it's also O(n^3)
Re: Precision?
Posted by bsu.mmf.team 4 May 2010 21:24
Could you expalin what is the QR-decomposition? Maybe, I didn't understand you very well.
Re: Precision?
Posted by bsu.mmf.team 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.
Re: Precision?
Posted by dAFTc0d3r [Yaroslavl SU] 6 May 2010 10:29
I don't understand too. :-[
Re: Precision?
Posted by Sergey Lazarev (MSU Tashkent) 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.
Re: Precision?
Posted by 2rf [Perm School #9] 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
Re: Precision?
Posted by mouse_wireless2 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