11149 - Power of Matrix

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

Moderator: Board moderators

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

11149 - Power of Matrix

Any Hints?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
A hint:

Code: Select all

A+A^2+...+A^(2n) = (A+A^2+...+A^n) + A^n (A+A^2+...+A^n)

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
Is a solution with a complexity roughly n^3 * log(k) supposed to pass the
time limit ? Or you need to improve a bit on the n^3 part ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Ivan wrote:Is a solution with a complexity roughly n^3 * log(k) supposed to pass the time limit ?
Mine passed.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
Thanks mf!
Happy New Year!

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm
How to make it in 2 seconds?

My ACed program (C++) cost about 5 seconds, but the time limit is 2s during the contest...
mf wrote:
Ivan wrote:Is a solution with a complexity roughly n^3 * log(k) supposed to pass the time limit ?
Mine passed.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
As you probably noticed the problem is almost identical to one of the
relatively recent problems on TopCoder (SRM 306). The only difference
is the time limit. In order to pass it the only thing I did additionaly
is to avoid calculating A^n on every recursive step. So I just kind of
turned the function that calculates a matrix power (A ^ k) from a
recursive one into a DP one (memoization). In the beginning of each
test case I just calculate A ^ k and store the intermediate results in
a map. Than on each recursive step you get what you need from this map
avoiding to calculate the same thing twice. That improved the run time
from 6+ sec to less than 1 sec.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Ivan wrote:As you probably noticed the problem is almost identical to one of the relatively recent problems on TopCoder (SRM 306). The only difference is the time limit.
I am not a Topcoder member, and this task is designed long time ago (but the judge input/output is recently made). So it is interesting to see that people over the world have similar ideas in designing new programming tasks~ P.S. We have already got more than 6 tasks that can be used in our "Newbie Contest 4"! Of course the judge data etc are not done, and the contest will probably hold at the end of 2007 I think? 7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Hao Hu
New poster
Posts: 5
Joined: Mon Jan 01, 2007 8:22 am
Location: Nanjing University, China
Contact:

11149 Power of Matrix WA

code removed because of getting accepted
Last edited by Hao Hu on Mon Jan 01, 2007 12:48 pm, edited 1 time in total.
Solo Player

Hao Hu
New poster
Posts: 5
Joined: Mon Jan 01, 2007 8:22 am
Location: Nanjing University, China
Contact:
Problem solved...so careless in the base case of solve(k).
Solo Player

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Ivan wrote:In order to pass it the only thing I did additionaly
is to avoid calculating A^n on every recursive step. So I just kind of
turned the function that calculates a matrix power (A ^ k) from a
recursive one into a DP one (memoization). In the beginning of each
test case I just calculate A ^ k and store the intermediate results in
a map. Than on each recursive step you get what you need from this map
avoiding to calculate the same thing twice. That improved the run time
from 6+ sec to less than 1 sec.
I did exactly the same thing. helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Congratulation..~!!
If you get AC, you may remove your code..
I think that's kind of courtesy here..

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am
i didn't find anything wrong in the base case of solve(k)

Code: Select all

Matrix solve(int k)
{
if(k==1) return m;
Matrix ret=solve(k/2);
Matrix pow=power(m,k/2);
if(k%2==1)
{
Matrix tt=mul(pow,pow);
Matrix newpow=mul(tt,m);
return ans;
}
return tmp;
}

Hao Hu
New poster
Posts: 5
Joined: Mon Jan 01, 2007 8:22 am
Location: Nanjing University, China
Contact:
temper_3243 wrote:i didn't find anything wrong in the base case of solve(k)

Code: Select all

Matrix solve(int k)
{
if(k==1) return m;
Matrix ret=solve(k/2);
Matrix pow=power(m,k/2);
if(k%2==1)
{
Matrix tt=mul(pow,pow);
Matrix newpow=mul(tt,m);
return ans;
}
return tmp;
}
I should not return m... I should return the m % 10 ....
Solo Player

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I think computing A^k recursively also works, but if this is not done properly, then the complexity may increase to O(n^3 (log k)^2).
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org