10524 - Matrix Reloaded

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

10524 - Matrix Reloaded

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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
"Everything should be made simple, but not always simpler"

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

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
New poster
Posts: 13
Joined: Sun May 25, 2003 12:36 pm
Location: Hong Kong
Contact:

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? :o

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~

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

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

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

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

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? :o

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!
ImageWe are all in a circular way, no advances, only moving and moving!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
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)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
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)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
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)

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

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

:evil:
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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
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)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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 :oops: :oops:
"Everything should be made simple, but not always simpler"

Post Reply

Return to “Volume 105 (10500-10599)”