11149 - Power of Matrix

[Leonid]

Any Hints?

[mf]

A hint:

Code: Select all

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

[Ivan]

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]

Is a solution with a complexity roughly n^3 * log(k) supposed to pass the time limit ?

Mine passed.

[Ivan]

Thanks mf!
Happy New Year!

[RoBa]

How to make it in 2 seconds?

My ACed program (C++) cost about 5 seconds, but the time limit is 2s during the contest...

Is a solution with a complexity roughly n^3 * log(k) supposed to pass the time limit ?

Mine passed.

[Ivan]

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]

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?

[Hao Hu]

code removed because of getting accepted

[Hao Hu]

Problem solved...so careless in the base case of solve(k).

[sohel]

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]

Congratulation..~!!
If you get AC, you may remove your code..
I think that's kind of courtesy here..

[temper_3243]

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;
}

[Hao Hu]

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;
}

I should not return m... I should return the m % 10 ....

[Observer]

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).