Qq in handling matrix
Moderator: Board moderators
Qq in handling matrix
Situation:
Language: Pascal
Given: A is a matrix of dimensions of n * n, where 1<=n<=100
and the values of every cells are either 0 or 1.
Task: Find A + A^2 + A^3 +...+ A^n
(A^n = A dot A dot A ...... for n times)
Time: <=1 second
e.g. If A =
0 1 0 0
0 0 1 0
0 0 0 0
1 1 0 0
Then the output is
0 1 1 0
0 0 1 0
0 0 0 0
1 2 2 0
If we do direct matrix multiplication for this task, the time complexity is O(n^4). Am I correct?
Are there any quicker method?
Language: Pascal
Given: A is a matrix of dimensions of n * n, where 1<=n<=100
and the values of every cells are either 0 or 1.
Task: Find A + A^2 + A^3 +...+ A^n
(A^n = A dot A dot A ...... for n times)
Time: <=1 second
e.g. If A =
0 1 0 0
0 0 1 0
0 0 0 0
1 1 0 0
Then the output is
0 1 1 0
0 0 1 0
0 0 0 0
1 2 2 0
If we do direct matrix multiplication for this task, the time complexity is O(n^4). Am I correct?
Are there any quicker method?
Last edited by Observer on Mon May 12, 2003 10:33 am, edited 5 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Yeah ....
But you could observe that:
A^n = A^(a0*1+a1*2+a2*4+.....)
such that
n = a0*1+a1*2+a2*4+.....
so you must calculate only apropriate powers of A, so I think that time complexity is lowered to (N^3)log(N) ....
Regards
DM
But you could observe that:
A^n = A^(a0*1+a1*2+a2*4+.....)
such that
n = a0*1+a1*2+a2*4+.....
so you must calculate only apropriate powers of A, so I think that time complexity is lowered to (N^3)log(N) ....
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'm sorry I don't quite understand.
Can you explain more clearly, please?
Can you explain more clearly, please?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
you have to compute Sigma(A^n) for i=1..n for some n, yes ?
so we should compute only A^n (rest of this you have computed in this process). but
A^n you should compute in less than n steps (in fact in log(n) steps)
i.e.
you want to compute A^90 nice value
so A^90 = A^(0*1 + 1*2 + 0*4 + 1*8 + 1*16 + 0*32 + 1*64)
so you must compute only A^2,A^8,A^16,A^64 ...
and A^8 = ((A^2)^2)^2, A^16 = (A^8)^2 ....
in other words calculate A^(2^i) for such i that 2^i <= n
and from it you have all results faster....
Maybe I said it now clearly
Regards
DM
so we should compute only A^n (rest of this you have computed in this process). but
A^n you should compute in less than n steps (in fact in log(n) steps)
i.e.
you want to compute A^90 nice value
so A^90 = A^(0*1 + 1*2 + 0*4 + 1*8 + 1*16 + 0*32 + 1*64)
so you must compute only A^2,A^8,A^16,A^64 ...
and A^8 = ((A^2)^2)^2, A^16 = (A^8)^2 ....
in other words calculate A^(2^i) for such i that 2^i <= n
and from it you have all results faster....
Maybe I said it now clearly
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)
Ah... Thanks very much.
Here is my interpretation of what you mean:
.......1....2....4....8....16
01 ...1....0....0....0....0 => 1
02 ...0....1....0....0....0 => 1
03 ...1....1....0....0....0 => 2
04 ...0....0....1....0....0 => 1
05 ...1....0....1....0....0 => 2
06 ...0....1....1....0....0 => 2
07 ...1....1....1....0....0 => 3
08 ...0....0....0....1....0 => 1
09 ...1....0....0....1....0 => 2
10 ...0....1....0....1....0 => 2

Sum:5....5....4....3....0 => 17
This may lead to quicker calculation.
Here is my interpretation of what you mean:
.......1....2....4....8....16
01 ...1....0....0....0....0 => 1
02 ...0....1....0....0....0 => 1
03 ...1....1....0....0....0 => 2
04 ...0....0....1....0....0 => 1
05 ...1....0....1....0....0 => 2
06 ...0....1....1....0....0 => 2
07 ...1....1....1....0....0 => 3
08 ...0....0....0....1....0 => 1
09 ...1....0....0....1....0 => 2
10 ...0....1....0....1....0 => 2

Sum:5....5....4....3....0 => 17
This may lead to quicker calculation.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
However ......
I know this method makes calculating A^n faster.
But how about Sigma(A^i) for i := 1 to n ??
(As A^i = A^(i1) * A, only n such multiplication is req. for Sigma(A^i) for i := 1 to n if we do it sequentially)
Please help!!!!!!!!
P.S. As you may know, the time complexity of common matrix multiplication algorithm is O(n^3). How can this be improved?
I know this method makes calculating A^n faster.
But how about Sigma(A^i) for i := 1 to n ??
(As A^i = A^(i1) * A, only n such multiplication is req. for Sigma(A^i) for i := 1 to n if we do it sequentially)
Please help!!!!!!!!
P.S. As you may know, the time complexity of common matrix multiplication algorithm is O(n^3). How can this be improved?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
It's almost it, but:
......1....2....4....8....16
01 ...1....0....0....0....0 => 1
02 ...0....1....0....0....0 => 1
03 ...1....1....0....0....0 => 2 <=> 1 because A and A^2 you have now
04 ...0....0....1....0....0 => 1
05 ...1....0....1....0....0 => 2 <=> 1
06 ...0....1....1....0....0 => 2 <=> 1
07 ...1....1....1....0....0 => 3 <=> 2
08 ...0....0....0....1....0 => 1
09 ...1....0....0....1....0 => 2 <=> 1
10 ...0....1....0....1....0 => 2 <=> 1

Sum:5....5....4....3....0 => 17 <=> 11
So you need fewer operations .... you must momoraize A^(2^i) in memory and used it if necessary ... you use more momory, but got better time
DM
......1....2....4....8....16
01 ...1....0....0....0....0 => 1
02 ...0....1....0....0....0 => 1
03 ...1....1....0....0....0 => 2 <=> 1 because A and A^2 you have now
04 ...0....0....1....0....0 => 1
05 ...1....0....1....0....0 => 2 <=> 1
06 ...0....1....1....0....0 => 2 <=> 1
07 ...1....1....1....0....0 => 3 <=> 2
08 ...0....0....0....1....0 => 1
09 ...1....0....0....1....0 => 2 <=> 1
10 ...0....1....0....1....0 => 2 <=> 1

Sum:5....5....4....3....0 => 17 <=> 11
So you need fewer operations .... you must momoraize A^(2^i) in memory and used it if necessary ... you use more momory, but got better time
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)
Excuse me. Can you explain what you mean by "store it in memory"?Dominik Michniewski wrote:you must memorize A^(2^i) in memory and used it if necessary ... you use more memory, but got better time
Do you mean storing it in an array?
And what will the new time complexity approximately be?
(Sorry for all that fuss because I'm just a beginner :p )
P.S. As you may know, the time complexity of common matrix multiplication algorithm (e.g. a single A * A operation) is O(n^3). How can this be improved? Are there any faster method?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Finally......
I've figure out that due to the nature of my qq, I can solve it using another algorithm which is more efficient......
Anyway, thanks for your help!!!
I've figure out that due to the nature of my qq, I can solve it using another algorithm which is more efficient......
Anyway, thanks for your help!!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

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