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

Post by Leonid » Sat Dec 30, 2006 7:07 pm

Any Hints?

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

Post by mf » Sat Dec 30, 2006 7:28 pm

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

Post by Ivan » Sat Dec 30, 2006 8:24 pm

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:

Post by mf » Sat Dec 30, 2006 8:41 pm

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

Post by Ivan » Sat Dec 30, 2006 8:51 pm

Thanks mf!
Happy New Year!

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

Post by RoBa » Sun Dec 31, 2006 1:21 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

Post by Ivan » Sun Dec 31, 2006 4:52 pm

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

Post by Observer » Mon Jan 01, 2007 4:07 am

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~ :D

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

Post by Hao Hu » Mon Jan 01, 2007 8:30 am

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:

Post by Hao Hu » Mon Jan 01, 2007 8:57 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Jan 01, 2007 11:07 am

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. :D

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Jan 01, 2007 11:16 am

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

Post by temper_3243 » Mon Jan 01, 2007 1:38 pm

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
New poster
Posts: 5
Joined: Mon Jan 01, 2007 8:22 am
Location: Nanjing University, China
Contact:

Post by Hao Hu » Mon Jan 01, 2007 2:53 pm

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

Post by Observer » Tue Jan 02, 2007 3:34 am

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

Post Reply

Return to “Volume 111 (11100-11199)”