OJ Board

though the problem has not yet come to the set, I'd like to discuss about it a bit.

the problem asks for exp(A), and gives a complicated definition using Jordan cells and ....
but from mathematics we also know that exp(A) = 1+A/1!+A^2/2!+....
even for matrices. So, I simply summed up that series untill the entries of exp(A) converged to with 1e-8. and printed out the answer to three decimal places and got a WA.
can some one tell me what was wrong with my approach?


bye
abi

What is expected result for this test case?

1
8
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5

I get 29423158354627500.000 (64 times), but I doubt that this is accurate enough.

I checked teh output for this case using scilab's Exp(A) function and my program
the outputs matched to three decimal places.
btw, I do the iterations till the entries converge to 1e-8 of their value. I also tried once by iterating 5000 times. both gave me WA.
the answer from my program:

29423158354627452.000

Both mine and yours answers are wrong. The right is:
29423158354627499.051

I used bc with precision 1000 and 1000 iterations. Scilab is obviously using doubles or long doubles, which are not accurate enough.

I believe there's something wrong with this problem. I wrote some code to handle high precision arithmetics and it gives me perfect results (no rounding errors at all), but still gets WA.

Krzysztof Duleba wrote:I believe there's something wrong with this problem. I wrote some code to handle high precision arithmetics and it gives me perfect results (no rounding errors at all), but still gets WA.

Can you send me your source code? I can check if everything is OK.

I just got AC. Everything is fine with the problem, I had a terrible typo and displayed small numbers in a wrong way. Big thanks to Semyon Dyatlov who helped me with that.

Krzysztof Duleba wrote:What is expected result for this test case?

1
8
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5

I get 29423158354627500.000 (64 times), but I doubt that this is accurate enough.

The result is (e^40)/8.
According to windows' calculator, it's 29423158354627498.175987488843629

My AC code returns 29423158354627499.051 on the main diagonal and 29423158354627498.051 elsewhere.

Just made it... What a terrible struggle. About 2 hours playing with num_iterations vs. precision.

Ended up with round-up-error-free approach and 128 iterations (96 don't make it, neither do 128 with division at each iteration).

8.5sec, that was close...

BTW, there is no that big test of 8x8 fives. Running time showed that during my tuning efforts. Though, there is something other like that with precision tricks, but with faster "convergence" (actually fake). Attempts to wait until factorial outruns nominator by some power - all gave WA (too big gave TL). Power deltas come very close at higher iterations.

P.S: Finally I can sleep well

For the 8x8 matrix of fives, I got 29423158354627499.053 on the diagonal if I used long double and can't get AC. Only after I implemented high precision arithmetic (with at least 27 decimal digits) using some modification of my big integer implementation I got 29423158354627499.05097 and I got AC.
The algorithm that I used is based on taylor's formula with a little trick to increase precision, it took 115 iterations. With appropriate scaling, then I've reduced the number of iterations to 40.
How can people solve this one without high precision arithmetic?

I used BigInts. I don't think you can achieve required accuracy without some kind of arbitrary precision arithmetics.