|
|
| Show all threads Hide all threads Show all messages Hide all messages | | easy with float128 | ~'Yamca`~ | 1766. Humpty Dumpty | 26 Mar 2025 13:08 | 1 | | | give me hint | quick(YarSU) | 1766. Humpty Dumpty | 23 Sep 2020 21:34 | 3 | Search up Markov chains. To solve this problem you have to build a state transition matrix and compute its sufficiently large power. | | Precision? | chhung6 | 1766. Humpty Dumpty | 7 Mar 2018 22:43 | 18 | 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 ? 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 :) Thanks for your reply. :)
I used Gaussian Elimination. Seems it's very difficult to handle the precision... 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-_- 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;
}
} 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 I used Gauss. But with BigDecimal. Can you explain why iterations more precize than gauss?
Why you think that it is necessary about 2^50 iterations? 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. I tried to solve it as you said. TL #3 ... QR - decomposition is only a bit slower than Gaussian elimination, and it's also O(n^3) Could you expalin what is the QR-decomposition? Maybe, I didn't understand you very well. Thanks a lot! But I don't understand how could it be useful to avoid big precision troubles with Gauss algorithm. I don't understand too. :-[ 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. Just want to mention that I kept getting WA and after changing double to long double immediately got AC. Maybe it helps | | What's the magic in #18 | Ade | 1766. Humpty Dumpty | 9 Apr 2013 14:18 | 3 | Always WA at #18
I gave it everything I have.
Resolve the formula group. Iterate to 1e-15. Still WA.
Any hints?
Thanks
Edited by author 05.04.2013 23:37 Iterative schemes are unstable (small deviations from equilibrium in neighbor nodes lead to large error in final solution), so stupid iteration is hard to get AC here.
Better reduce the problem to linear system and solve it honestly, or reduce it to matrix multiplications (even in this case you need some streetmagic to beat accuracy!) Thanks, Vedernikoff
I resolved the linear formulations, but WA#18.
Then I add some iterations afterward to 1e-14. Still failing.
I'm now planning to pure iterations. The initial state doesn't matter, I think. So I'm gonna start from 1/64 in every cell. | | WA 16 | Zefick | 1766. Humpty Dumpty | 1 Jun 2010 12:06 | 1 | WA 16 Zefick 1 Jun 2010 12:06 I solve the system by the Gauss method, but the 16-th test he passes.
Then I tried to take first the Gauss method and the results of the initial matrix method of Seidel (iterative algorithm), but it does not always converge and the result becomes invalid even before the 16-second test.
What is there a problem? | | No subject | AdyghSU TEAM13: Kasparyan, Siunov | 1766. Humpty Dumpty | 24 May 2010 19:05 | 2 | No subject AdyghSU TEAM13: Kasparyan, Siunov 11 Apr 2010 15:58 a1 и a2 - соседи? (у них есть общая вершина) | | Question | OpenGL | 1766. Humpty Dumpty | 24 Apr 2010 23:36 | 2 | What right answer on sample test data? 0.007142857143 on corners,
0.011904761905 on sides and
0.019047619048 on the center 7x7 square
Edited by author 24.04.2010 23:37 |
|
|
|
