Qq in handling matrix

Write here if you have problems with your Pascal source code

Moderator: Board moderators

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

Qq in handling matrix

Post by Observer » Mon May 12, 2003 9:58 am

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

Post by Dominik Michniewski » Mon May 12, 2003 10:01 am

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

Post by Observer » Mon May 12, 2003 10:16 am

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

Post by Dominik Michniewski » Mon May 12, 2003 11:32 am

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

Post by Observer » Mon May 12, 2003 11:55 am

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

Post by Observer » Mon May 12, 2003 12:39 pm

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)

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

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

Post by Dominik Michniewski » Mon May 12, 2003 1:28 pm

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

Post by Observer » Mon May 12, 2003 3:54 pm

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

Post by Observer » Thu May 15, 2003 10:52 am

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

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

Post by Dominik Michniewski » Thu May 15, 2003 12:36 pm

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)

Post Reply

Return to “Pascal”