10524  Matrix Reloaded
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
It looks like I made mistake in outputing
I realize (after changing code to take maximal element as pivot), that I have right values, but my matrix is transposed ... so I think that's my problem :oops: I am sometimes so stupid ....
Thanks all for help. there is another problem, which learn me something and I must be more carefully ...
Best regards
DM
I realize (after changing code to take maximal element as pivot), that I have right values, but my matrix is transposed ... so I think that's my problem :oops: I am sometimes so stupid ....
Thanks all for help. there is another problem, which learn me something and I must be more carefully ...
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:
Unfortunatly I've got WA many times .... I try many options, but still WA ...
Could anyone help me and post more test cases ?
Best gerads
DM
Could anyone help me and post more test cases ?
Best gerads
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, you should try this test case:
It's always the simple things...
Code: Select all
1
5

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Thanks Per again and again
This was silly mistake .... very silly .... I misunderstood problem  I think that matrix 1x1has not inverse ....
Now I got Accepted :)
Best regards
DM
This was silly mistake .... very silly .... I misunderstood problem  I think that matrix 1x1has not inverse ....
Now I got Accepted :)
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)

 New poster
 Posts: 23
 Joined: Sun Jun 15, 2003 4:45 pm
 Location: Ukraine
10524 Matrix Reloaded after rejudgement
I am totaly disorientated. My AC program gets WA now, but I have checked it many times.
What do the words "No pivoting is allowed" mean? Can somebody explain it or give us an example of input and output?
And what is the limit value for matrix elements?
THANKS!!
What do the words "No pivoting is allowed" mean? Can somebody explain it or give us an example of input and output?
And what is the limit value for matrix elements?
THANKS!!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
It's easy !!
When in time of computing you analize row 3 nad matrix is i.e.:
1000
0100
0001
0010
your program must answer "not possible"  that's all . but you see that such matrix exist  you can exchange rows 3 and 4 and everything is ok
but in this problem  it's impossible
Best regards
DM
When in time of computing you analize row 3 nad matrix is i.e.:
1000
0100
0001
0010
your program must answer "not possible"  that's all . but you see that such matrix exist  you can exchange rows 3 and 4 and everything is ok
but in this problem  it's impossible
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)
actually ,
i saw many to solve the problem using pivoting.
actually, pivoting is a special corrector method.
but when a method was not perticularly said
(when there are multiple method creting multiple answer),
it's not better or wise to use that method. use the simple,
not the complex if others are not said.
I am poor in English. I know. But i think
you all will understand what i want to say.
the line is added for just clarity.
The problem was given in the contest as a easy problem.
But thinking complex made it complex.
And, from the numerical methods' point of view,
there may be many methods producing different answer.
If other way is not said, it is better to use the simple.
And, like you, many questioned me whether to do it using
pivoting or not.
So, for clarity pivoting is removed(The mathod was not used
the first time, the line is just added,not any other change but some
tripical test cases.).
So check for tripical test cases and those who got wa can
easily get ac.
And sorry for the late.
It's for the server upgrading.

Anupam
i saw many to solve the problem using pivoting.
actually, pivoting is a special corrector method.
but when a method was not perticularly said
(when there are multiple method creting multiple answer),
it's not better or wise to use that method. use the simple,
not the complex if others are not said.
I am poor in English. I know. But i think
you all will understand what i want to say.
the line is added for just clarity.
The problem was given in the contest as a easy problem.
But thinking complex made it complex.
And, from the numerical methods' point of view,
there may be many methods producing different answer.
If other way is not said, it is better to use the simple.
And, like you, many questioned me whether to do it using
pivoting or not.
So, for clarity pivoting is removed(The mathod was not used
the first time, the line is just added,not any other change but some
tripical test cases.).
So check for tripical test cases and those who got wa can
easily get ac.
And sorry for the late.
It's for the server upgrading.

Anupam
"Everything should be made simple, but not always simpler"

 New poster
 Posts: 23
 Joined: Sun Jun 15, 2003 4:45 pm
 Location: Ukraine
what?
This problem is really unclear. What on earth does 'no pivoting is allowed' mean ? Are you saying that:
all matrices are 2*2 or less, or diagonal ? If you calculate the inverse of a 2*2 matrix in general then surely you have used pivoting although it is not completely obvious ? Or are there things like general 3*3 matrices in the input and we should use the formula ? How far does this go ? What on earth is this problem really saying ?
I don't understand the example above at all, the matrix given has an inverse, is it necessary to use pivoting to find it ? Well...... no, it isn't since the matrix given is clearly self inverse........ help!!!!!!!
all matrices are 2*2 or less, or diagonal ? If you calculate the inverse of a 2*2 matrix in general then surely you have used pivoting although it is not completely obvious ? Or are there things like general 3*3 matrices in the input and we should use the formula ? How far does this go ? What on earth is this problem really saying ?
I don't understand the example above at all, the matrix given has an inverse, is it necessary to use pivoting to find it ? Well...... no, it isn't since the matrix given is clearly self inverse........ help!!!!!!!
The "no pivoting" comment says (or at least I assumed so, and got AC) that:
"Since we assume you're using the method of Gaussian elimination for inverting matrices, you are not, in this process, allowed to swap two rows (or two columns)."
For people who want to solve it some other way (some people have great imagination ), well, good luck...
"Since we assume you're using the method of Gaussian elimination for inverting matrices, you are not, in this process, allowed to swap two rows (or two columns)."
For people who want to solve it some other way (some people have great imagination ), well, good luck...
Per: that still does not apply to the case above you can add row four to row three:
10001000
01000100
00010010
00100001
10001000
01000100
00110011
00100001
now subtract row three from row 4:
100 010 00
010 001 00
001 100 11
00010010
multiply row 4 by 1:
10001000
01000100
00110011
00010010
and subtract row 4 from row3:
10001000
01000100
00100001
00010010
so...........
10001000
01000100
00010010
00100001
10001000
01000100
00110011
00100001
now subtract row three from row 4:
100 010 00
010 001 00
001 100 11
00010010
multiply row 4 by 1:
10001000
01000100
00110011
00010010
and subtract row 4 from row3:
10001000
01000100
00100001
00010010
so...........
Yeah, OK, it's a question as to how you define Gaussian elimination.
The way I've usually seen it, you first have a "forward elimination" (direct translation of the swedish term, not sure if it's correct) phase where you make the matrix upper triangular. In this phase, you first add multiples of row 1 to rows 2..n, then multiples of row 2 to rows 3..n, and so on, and that's it: you never add a row to the rows above it. Then, similarly, there's the "backward elimination" phase to make the matrix lower triangular as well.
The way I've usually seen it, you first have a "forward elimination" (direct translation of the swedish term, not sure if it's correct) phase where you make the matrix upper triangular. In this phase, you first add multiples of row 1 to rows 2..n, then multiples of row 2 to rows 3..n, and so on, and that's it: you never add a row to the rows above it. Then, similarly, there's the "backward elimination" phase to make the matrix lower triangular as well.