11149  Power of Matrix
Moderator: Board moderators
A hint:
Code: Select all
A+A^2+...+A^(2n) = (A+A^2+...+A^n) + A^n (A+A^2+...+A^n)
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.
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.
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~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.
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 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
I did exactly the same thing.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.

 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);
Matrix tmp=add(ret,mul(pow,ret));
if(k%2==1)
{
Matrix tt=mul(pow,pow);
Matrix newpow=mul(tt,m);
Matrix ans=add(tmp,newpow);
return ans;
}
return tmp;
}

 New poster
 Posts: 5
 Joined: Mon Jan 01, 2007 8:22 am
 Location: Nanjing University, China
 Contact:
I should not return m... I should return the m % 10 ....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); Matrix tmp=add(ret,mul(pow,ret)); if(k%2==1) { Matrix tt=mul(pow,pow); Matrix newpow=mul(tt,m); Matrix ans=add(tmp,newpow); return ans; } return tmp; }
Solo Player
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org