10524  Matrix Reloaded
Moderator: Board moderators

 New poster
 Posts: 23
 Joined: Sun Jun 15, 2003 4:45 pm
 Location: Ukraine
10524  Matrix Reloaded
Please, can somebody give an example of input and output for this problem?

 New poster
 Posts: 23
 Joined: Sun Jun 15, 2003 4:45 pm
 Location: Ukraine
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.....
good algorithm is important~

 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
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.....
We are all in a circular way, no advances, only moving and moving!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Is any faster method to solve it than GaussJordan 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
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could anyone tell me any special cases ?
I use GaussJordan 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 GaussJordan 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
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
Dominik: In general, there is no faster method than GaussJordan 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

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
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
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.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
As pivot I choose first element which have nonzero 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
Last edited by Dominik Michniewski on Thu Jul 17, 2003 8:34 am, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
It looks ok.
Since we're dealing with floats, what's a nonzero element? 1e99? If you want better numerical stability, you should choose the maximum element as pivot, not just the first nonzero (I actually consider a matrix singular if I cannot find a pivot element whose absolute value exceeds 1e12). Also, I pivot on both rows and columns.
Since we're dealing with floats, what's a nonzero element? 1e99? If you want better numerical stability, you should choose the maximum element as pivot, not just the first nonzero (I actually consider a matrix singular if I cannot find a pivot element whose absolute value exceeds 1e12). Also, I pivot on both rows and columns.
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
"Everything should be made simple, but not always simpler"