10524 - Matrix Reloaded
Posted: Fri Jul 04, 2003 3:37 pm
Please, can somebody give an example of input and output for this problem?
print 6 digits after decimal point.
a space between element of the same line.
and nothing more
Page 1 of 3
Posted: Fri Jul 04, 2003 8:06 pm
Posted: 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!
It's very important that output contains 6 digits after decimal point!
I got AC!
Posted: 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.....
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.....
Posted: Sun Jul 06, 2003 7:08 pm
There's a easier way by reduce row echleon form..
Posted: Sun Jul 06, 2003 7:43 pm
You may see in the "Numerical Methods" for more information.......it's easy I think!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.....
Posted: 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
Could anyone tell me (help from contest creators would be nice
) ?Best regards
DM
Posted: 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
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
Posted: 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:
Output:
(Note that I have a presentation error )
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
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
Posted: 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
Thanks Per for this input ....
)I try to find where I have a bug
Best regards
DM
Posted: 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
Posted: 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: 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.
Posted: 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
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
Posted: 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.
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.
Posted: 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
