10524 - Matrix Reloaded

Alexander Kozlov · Post by **Alexander Kozlov** » Fri Jul 04, 2003 3:37 pm

Please, can somebody give an example of input and output for this problem?

anupam · Post by **anupam** » Fri Jul 04, 2003 8:06 pm

print 6 digits after decimal point.
a space between element of the same line.
and nothing more

Alexander Kozlov · Post by **Alexander Kozlov** » Fri Jul 04, 2003 9:07 pm

Thank you very much!

It's very important that output contains 6 digits after decimal point!

I got AC!

Lamas · Post by **Lamas** » Sun Jul 06, 2003 5:28 pm

What I want to ask is What is the limit of n?

I can't imagain how people can do it such quick and use 64k only?

If I am not wrong. To find the inverse of a matrix,
It must first find the determinants of the matrix, and then find the element of the inverse by found out the cofactor of the element in that matrix.

It is a complex process.

I can't believe it.....

Larry · Post by **Larry** » Sun Jul 06, 2003 7:08 pm

There's a easier way by reduce row echleon form..

Moni · Post by **Moni** » Sun Jul 06, 2003 7:43 pm

Lamas wrote:What I want to ask is What is the limit of n?

I can't imagain how people can do it such quick and use 64k only?

If I am not wrong. To find the inverse of a matrix,
It must first find the determinants of the matrix, and then find the element of the inverse by found out the cofactor of the element in that matrix.

It is a complex process.
I can't believe it.....

You may see in the "Numerical Methods" for more information.......it's easy I think!

Dominik Michniewski · Post by **Dominik Michniewski** » Mon Jul 07, 2003 9:44 am

Is any faster method to solve it than Gauss-Jordan elimination method ??
Could anyone tell me (help from contest creators would be nice

) ?

Best regards
DM

Dominik Michniewski · Post by **Dominik Michniewski** » Fri Jul 11, 2003 8:29 am

Could anyone tell me any special cases ?
I use Gauss-Jordan Elimination with pivoting, and I think, that my outputs should be correct ... I print output with 6 digits after decimal point but I always got WA. Someone who get Accepted could help me ?
I don't want to post code, but I can send it.

Best regards
DM

Per · Post by **Per** » Mon Jul 14, 2003 5:21 pm

Dominik: In general, there is no faster method than Gauss-Jordan elimination. For special cases (such as tridiagonal matrixes) it is possible to calculate the inverse in O(n^2).

For I/O, you could try the following:

Code: Select all

10
9.5013 6.1543 0.5789 0.1527 8.3812 1.9343 4.9655 7.2711 7.9482 1.3652
2.3114 7.9194 3.5287 7.4679 0.1964 6.8222 8.9977 3.0929 9.5684 0.1176
6.0684 9.2181 8.1317 4.4510 6.8128 3.0276 8.2163 8.3850 5.2259 8.9390
4.8598 7.3821 0.0986 9.3181 3.7948 5.4167 6.4491 5.6807 8.8014 1.9914
8.9130 1.7627 1.3889 4.6599 8.3180 1.5087 8.1797 3.7041 1.7296 2.9872
7.6210 4.0571 2.0277 4.1865 5.0281 6.9790 6.6023 7.0274 9.7975 6.6144
4.5647 9.3547 1.9872 8.4622 7.0947 3.7837 3.4197 5.4657 2.7145 2.8441
0.1850 9.1690 6.0379 5.2515 4.2889 8.6001 2.8973 4.4488 2.5233 4.6922
8.2141 4.1027 2.7219 2.0265 3.0462 8.5366 3.4119 6.9457 8.7574 0.6478
4.4470 8.9365 1.9881 6.7214 1.8965 5.9356 5.3408 6.2131 7.3731 9.8833

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Output:

Code: Select all

-0.070885 0.190366 -0.064787 -0.466908 -0.007342 0.132556 0.393284 -0.254181 0.106229 0.074244
0.106282 0.072758 -0.055644 -0.107017 0.006025 -0.143474 0.032887 0.017552 -0.003056 0.132946
-0.158503 0.248147 0.074397 -0.508077 -0.171241 0.390370 0.506520 -0.257356 0.004178 -0.179324
-0.158219 0.072117 0.018435 -0.126107 -0.073899 0.204100 0.305098 -0.170877 -0.001857 -0.091075
0.038540 0.060938 -0.058235 -0.168922 -0.065009 0.306328 0.203311 0.011262 -0.160097 -0.158063
0.026725 -0.086133 -0.081818 0.146694 0.111831 -0.137008 -0.228790 0.202612 0.059928 0.065387
0.111459 -0.174757 0.048315 0.512156 0.230113 -0.438043 -0.603087 0.271165 0.009040 0.107617
0.074352 -0.538201 0.230776 1.059830 0.164412 -0.692107 -0.874827 0.362630 0.179767 0.055162
-0.037257 0.248516 -0.040264 -0.435959 -0.229971 0.508425 0.460295 -0.241112 -0.128389 -0.153880
-0.027344 0.037008 -0.028874 -0.178656 -0.028274 0.168767 0.114784 -0.051993 -0.071996 0.058601

Not possible

(Note that I have a presentation error

)

Dominik Michniewski · Post by **Dominik Michniewski** » Tue Jul 15, 2003 7:59 am

Second input my program resolve correct, but In first ..... hmmm I've got the same results on diagonal, but completly different other values ..... hmmm that's intresting ....

Thanks Per for this input ....

)
I try to find where I have a bug

Best regards
DM

scythe · Post by **scythe** » Tue Jul 15, 2003 8:15 am

I have been trying to debug my actually correct source code because of your incorrect output.

Why do you post incorrect examples ?! Be more careful next time, because people actually read this stuff!!

My AC Output is:

-0.070885 0.393284 0.074244 -0.466908 0.106229 0.190366 0.132556 -0.007342 -0.254181 -0.064787
0.111459 -0.603087 0.107617 0.512156 0.009040 -0.174757 -0.438043 0.230113 0.271165 0.048315
-0.027344 0.114784 0.058601 -0.178656 -0.071996 0.037008 0.168767 -0.028274 -0.051993 -0.028874
-0.158219 0.305098 -0.091075 -0.126107 -0.001857 0.072117 0.204100 -0.073899 -0.170877 0.018435
-0.037257 0.460295 -0.153880 -0.435959 -0.128389 0.248516 0.508425 -0.229971 -0.241112 -0.040264
0.106282 0.032887 0.132946 -0.107017 -0.003056 0.072758 -0.143474 0.006025 0.017552 -0.055644
0.026725 -0.228790 0.065387 0.146694 0.059928 -0.086133 -0.137008 0.111831 0.202612 -0.081818
0.038540 0.203311 -0.158063 -0.168922 -0.160097 0.060938 0.306328 -0.065009 0.011262 -0.058235
0.074352 -0.874827 0.055162 1.059830 0.179767 -0.538201 -0.692107 0.164412 0.362630 0.230776
-0.158503 0.506520 -0.179324 -0.508077 0.004178 0.248147 0.390370 -0.171241 -0.257356 0.074397

Not possible

Per · Post by **Per** » Tue Jul 15, 2003 1:07 pm

Scythe: My output is correct. Just paste the matrix into Matlab or any other program capable of matrix inversion and check the answer. If you do that, you'll see that my output is correct whereas yours is incorrect (and if that output gave you AC, well, then the judge has way too easy input). Please, verify your own output before accusing others of posting incorrect data.

Dominik: two things:
Which element do you choose as pivot?

At first I had some trouble "undoing" all the pivots in the end, the rows and/or columns got mixed up. If you've got the diagonal right this is probably not the problem, but you could still check if you've got the right values in the wrong places.

Dominik Michniewski · Post by **Dominik Michniewski** » Tue Jul 15, 2003 1:52 pm

As pivot I choose first element which have non-zero value in given row.
I use this code to create inverse matrix: (maybe it's wrong ? - I found it in net ...) ....

N - rank of matrix
M - matrix to inverse
I - matrix with 1 on diagonal, rest 0 (I don't remember it's name)
[c]
spoiler ....
[/c]

Best regards
DM

Per · Post by **Per** » Tue Jul 15, 2003 2:30 pm

It looks ok.

Since we're dealing with floats, what's a non-zero element? 1e-99? If you want better numerical stability, you should choose the maximum element as pivot, not just the first non-zero (I actually consider a matrix singular if I cannot find a pivot element whose absolute value exceeds 1e-12). Also, I pivot on both rows and columns.

anupam · Post by **anupam** » Wed Jul 16, 2003 2:42 pm

I am very sorry for a stupid mistake during typing. I have to thank Alam Sir for picking the fault.
You are given the Order of the matrix not the rank of it.
Rank means different than orders.
Simply, you are given the dimension of the matrix.
Sorry for the mistake and Thanks to Sir again.
Sorry for my poor english