Qq in handling matrix

Write here if you have problems with your Pascal source code

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I'm sorry I don't quite understand.

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

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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^(i-1) * A, only n such multiplication is req. for Sigma(A^i) for i := 1 to n if we do it sequentially)

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

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Dominik Michniewski wrote:you must memorize A^(2^i) in memory and used it if necessary ... you use more memory, but got better time
Excuse me. Can you explain what you mean by "store it in memory"?
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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Finally......

I've figure out that due to the nature of my qq, I can solve it using another algorithm which is more efficient......

7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
That's nice ))

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)