JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm SPOJ :: TETRAHRD [ 1 2 ]    NEXT >
 SPOJ :: TETRAHRD | Reply I'm trying to solve http://www.spoj.com/problems/TETRAHRD/ . I've established the relation that S_n(Sum of 1st n tetranacci no's F_0+F_1 ... +F_n) = (F_n+2 + 2*F_n + F_n-1 -1)/3 . So I've calculated F_n+2,F_n,F_n-1 once using matrix exponentiation of 4*4 matrix. I've stored all intermediate F_x's (x<=n+2) in this process. So I can directly find S_m using these stored values. Finally S_n - S_m-1 is found. But this approach is giving TLE.Can anyone please suggest a better approach to solve the problem??
 Re: SPOJ :: TETRAHRD (response to post by lalitloc) | Reply Matrix exponentiation is log(n), but storing all intermediate F(x)'s will make it O(n), isn't it? You can calculate the sum of powers in log(n) -Here is an example -a ^ 0 + a ^ 1 + a ^ 2 + a ^ 3 + a ^ 4 + a ^ 5= a ^ 0 + a ^ 1 + a ^ 2 + a ^3 * (a ^ 0 + a ^ 1 + a ^ 2)= (1 + a ^ 3) * (a ^ 0 + a ^ 1 + a ^ 2)And you can recursively solve the same thing for (a ^ 0 + a ^ 1 + a ^ 2). Hope this helps.
 Re: SPOJ :: TETRAHRD (response to post by emotionalBlind) | Reply Actually I've stored the intermediate values of F_x in power function which computes M^n (M is Matrix).So without storing the intermediate values in each function call it takes O(k^3*logn) where M is k*k matrix.Now with storage it took another k^2 operations in each call so it's O((k^3+k^2)*logn). In your method for M^m+M^m+1+M^m+2.... M^n = M^m(1+M^1....M^n-m) . Doesn't it take k^3*log(m) for computing M^m and k^3*log(n-m) for (1+M^1...M^n-m) . So in total O(k^3(log(mn-m^2) + k^3) ??
 Re: SPOJ :: TETRAHRD (response to post by lalitloc) | Reply I don't understand it clearly now. How many F_x's you are storing? For all 1 to n?
 Re: SPOJ :: TETRAHRD (response to post by emotionalBlind) | Reply ```#include #include #include   using namespace std;   long long int modulo2( long long int a, long long int b, long long int c) // computes a^b %c { long long int x=1,y=a; // long long is taken to avoid overflow of intermediate results long long int x1, y1, x2, y2, b2, t1, t2; bool two;   while(b){ x1 = 0; y1 = x; x2 = 0; y2 = y; b2 = y; two = b & 1;   while(b2){ if (two) { if(b2 & 1){ t1 = x1+y1; t2 = x2+y2; x1 = (t1>c) ? t1-c : t1; x2 = (t2>c) ? t2-c : t2; } t1 = y1<<1; t2 = y2<<1; y1 = (t1>c) ? t1-c : t1; y2 = (t2>c) ? t2-c : t2; } else { if(b2 & 1){ t2 = x2+y2; x2 = (t2>c) ? t2-c : t2; } t2 = y2<<1; y2 = (t2>c) ? t2-c : t2; } b2 >>=1; } if (two) x = x1; y = x2; b >>=1; } return x; }   long long int a[4][4]; long long int b[4][4]; long long int p[1000000][16]={0}; void power(long long int n,long long int m); void mul(int n,long long int m); int main() { long long int mod=1000000007; int test; scanf("%d",&test); long long int inv=modulo2(3,mod-2,mod); // mod of inv of 3 while(test>0) { long long int n,m; int k; scanf("%lld%lld",&m,&n); a[0][0]=1;a[0][1]=1;a[0][2]=1;a[0][3]=1; a[1][0]=1;a[1][1]=0;a[1][2]=0;a[1][3]=0; a[2][0]=0;a[2][1]=1;a[2][2]=0;a[2][3]=0; a[3][0]=0;a[3][1]=0;a[3][2]=1;a[3][3]=0; b[0][0]=1;b[0][1]=1;b[0][2]=1;b[0][3]=1; b[1][0]=1;b[1][1]=0;b[1][2]=0;b[1][3]=0; b[2][0]=0;b[2][1]=1;b[2][2]=0;b[2][3]=0; b[3][0]=0;b[3][1]=0;b[3][2]=1;b[3][3]=0;   long long int ans1,ans2;   if(n==0 || n==1 || n==2) { ans1=0; } else if(n==3) { ans1=1; } else { power(n-1,mod); ans1=( ( (a[0][0]+(2*a[2][0])%mod+a[3][0]-1)%mod )*inv)%mod; // S_n= ans1= (F_n+2 + 2*F_n + F_n-1 -1)/3 }   a[0][0]=1;a[0][1]=1;a[0][2]=1;a[0][3]=1; a[1][0]=1;a[1][1]=0;a[1][2]=0;a[1][3]=0; a[2][0]=0;a[2][1]=1;a[2][2]=0;a[2][3]=0; a[3][0]=0;a[3][1]=0;a[3][2]=1;a[3][3]=0; b[0][0]=1;b[0][1]=1;b[0][2]=1;b[0][3]=1; b[1][0]=1;b[1][1]=0;b[1][2]=0;b[1][3]=0; b[2][0]=0;b[2][1]=1;b[2][2]=0;b[2][3]=0; b[3][0]=0;b[3][1]=0;b[3][2]=1;b[3][3]=0; if(m==0 || m==1 || m==2 || m==3) { ans2=0; }   else { power(m-2,mod); ans2=( ( (a[0][0]+(2*a[2][0])%mod+a[3][0]-1)%mod )*inv)%mod; // ans2=S_m-1 } // printf("ans1 is %lld and ans2 is %lld\n",ans1,ans2); int ans=(ans1-ans2+mod)%mod; //ans=S_n - S_m-1 printf("%d\n",ans); test--; } return 0; }   void power(long long int n,long long int m){ // for M^n mod m int i,j; //printf("now using pow(%lld) \n",n); if(n==1) { return ; }   else if( n<1000000 && p[n][0]!=0) // return if the values are precomputed { for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { a[i][j]=p[n][4*i+j]; } } return ; }   power(n/2,m); mul(0,m); if( (n%2) != 0 ) { mul(1,m); } /*printf("matrix after m^%lld is :\n",n); for(i=0;i<4;i++){ for(j=0;j<4;j++){ printf("%lld ",a[i][j]); } printf("\n"); }*/ if(n<1000000) // store the computed values { for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { p[n][4*i+j]=a[i][j]; } } } return ; }   void mul(int n,long long int m){ // For multiplication of matrices int i,j,x; int k=4; long long int d[k][k],sum=0; for(i=0;i
 Re: SPOJ :: TETRAHRD (response to post by lalitloc) | Reply Please use [cpp] tag.
 Re: SPOJ :: TETRAHRD (response to post by emotionalBlind) | Reply Despite being suggest by a lot of fellow programmers , You do not usually put the code in cpp tag. So I am assuming that you do not know how to do it.It is done like this : You have to use cpp and /cpp tag. both tags should be enclosed by square brackets. see this example on http://ideone.com/eY6ouY. ```#include #include #include   using namespace std;   long long int modulo2( long long int a, long long int b, long long int c) // computes a^b %c { long long int x=1,y=a; // long long is taken to avoid overflow of intermediate results long long int x1, y1, x2, y2, b2, t1, t2; bool two;   while(b){ x1 = 0; y1 = x; x2 = 0; y2 = y; b2 = y; two = b & 1;   while(b2){ if (two) { if(b2 & 1){ t1 = x1+y1; t2 = x2+y2; x1 = (t1>c) ? t1-c : t1; x2 = (t2>c) ? t2-c : t2; } t1 = y1<<1; t2 = y2<<1; y1 = (t1>c) ? t1-c : t1; y2 = (t2>c) ? t2-c : t2; } else { if(b2 & 1){ t2 = x2+y2; x2 = (t2>c) ? t2-c : t2; } t2 = y2<<1; y2 = (t2>c) ? t2-c : t2; } b2 >>=1; } if (two) x = x1; y = x2; b >>=1; } return x; }   long long int a[4][4]; long long int b[4][4]; long long int p[1000000][16]={0}; void power(long long int n,long long int m); void mul(int n,long long int m); int main() { long long int mod=1000000007; int test; scanf("%d",&test); long long int inv=modulo2(3,mod-2,mod); // mod of inv of 3 while(test>0) { long long int n,m; int k; scanf("%lld%lld",&m,&n); a[0][0]=1;a[0][1]=1;a[0][2]=1;a[0][3]=1; a[1][0]=1;a[1][1]=0;a[1][2]=0;a[1][3]=0; a[2][0]=0;a[2][1]=1;a[2][2]=0;a[2][3]=0; a[3][0]=0;a[3][1]=0;a[3][2]=1;a[3][3]=0; b[0][0]=1;b[0][1]=1;b[0][2]=1;b[0][3]=1; b[1][0]=1;b[1][1]=0;b[1][2]=0;b[1][3]=0; b[2][0]=0;b[2][1]=1;b[2][2]=0;b[2][3]=0; b[3][0]=0;b[3][1]=0;b[3][2]=1;b[3][3]=0;   long long int ans1,ans2;   if(n==0 || n==1 || n==2) { ans1=0; } else if(n==3) { ans1=1; } else { power(n-1,mod); ans1=( ( (a[0][0]+(2*a[2][0])%mod+a[3][0]-1)%mod )*inv)%mod; }   a[0][0]=1;a[0][1]=1;a[0][2]=1;a[0][3]=1; a[1][0]=1;a[1][1]=0;a[1][2]=0;a[1][3]=0; a[2][0]=0;a[2][1]=1;a[2][2]=0;a[2][3]=0; a[3][0]=0;a[3][1]=0;a[3][2]=1;a[3][3]=0; b[0][0]=1;b[0][1]=1;b[0][2]=1;b[0][3]=1; b[1][0]=1;b[1][1]=0;b[1][2]=0;b[1][3]=0; b[2][0]=0;b[2][1]=1;b[2][2]=0;b[2][3]=0; b[3][0]=0;b[3][1]=0;b[3][2]=1;b[3][3]=0;   if(m==0 || m==1 || m==2 || m==3) { ans2=0; }   else { power(m-2,mod); ans2=( ( (a[0][0]+(2*a[2][0])%mod+a[3][0]-1)%mod )*inv)%mod; } // printf("ans1 is %lld and ans2 is %lld\n",ans1,ans2); int ans=(ans1-ans2+mod)%mod; printf("%d\n",ans); test--; } return 0; }   void power(long long int n,long long int m){ int i,j; //printf("now using pow(%lld) \n",n); if(n==1) { return ; }   else if( n<1000000 && p[n][0]!=0) { for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { a[i][j]=p[n][4*i+j]; } } return ; }   power(n/2,m); mul(0,m); if( (n%2) != 0 ) { mul(1,m); } /*printf("matrix after m^%lld is :\n",n); for(i=0;i<4;i++){ for(j=0;j<4;j++){ printf("%lld ",a[i][j]); } printf("\n"); }*/ if(n<1000000) { for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { p[n][4*i+j]=a[i][j]; } } } return ; }   void mul(int n,long long int m){ int i,j,x; int k=4; long long int d[k][k],sum=0; for(i=0;i
 Re: SPOJ :: TETRAHRD (response to post by emotionalBlind) | Reply I guess you missed a^1 at the beginning of the formula.
 Re: SPOJ :: TETRAHRD (response to post by Jarekczek) | Reply Thanks, edited.
 Re: SPOJ :: TETRAHRD (response to post by emotionalBlind) | Reply Doesn't your method for (M^m + M^m+1 ... M^n) take O(k^3(log(mn-m^2) + k^3) time ??
 Re: SPOJ :: TETRAHRD (response to post by lalitloc) | Reply I think it's O(k ^ 3 * log n).
 Re: SPOJ :: TETRAHRD (response to post by emotionalBlind) | Reply Can you please elaborate your method on finding M^m + M^m+1 ...+M^n
 Re: SPOJ :: TETRAHRD (response to post by lalitloc) | Reply Lets say, f(n) = M ^ 1 + M ^ 2 + ... + M ^ nM ^ m + M ^ (m + 1) + ... + M ^ n = (M ^ 1 + .. M ^ n) - (M ^ 1 + .. + M ^ (m - 1))= f(n) - f(m - 1)So, now all we need to do is, calculate f(n) efficiently.Lets say n = 16.so f(16) = M ^ 1 + M ^ 2 + ... + M ^ 16= (M ^ 1 + M ^ 2 + ... + M ^ 8) + M ^ 8 * ( M ^ 1 + M ^ 2 + ... + M ^ 8)= ( M ^ 1 + M ^ 2 + ... + M ^ 8) * (1 + M ^ 8)Similarly M ^ 1 + M ^ 2 + ... + M ^ 8 can be written as (M ^ 1 + M ^ 2 + M ^ 3 + M ^ 4) * (1 + M ^ 4)Similarly, (M ^ 1 + M ^ 2 + M ^ 3 + M ^ 4) can be written as(M ^ 1 + M ^ 2) * (1 + M ^ 2)Similarly M ^ 1 + M ^ 2 can be written as M ^ 1 * (1 + M ^ 1)so f(16) = M ^ 1 * ( 1 + M ^ 1) * ( 1 + M ^ 2) * (1 + M ^ 4) * (1 + M ^ 8)So there are log(n) + 1 term in this sequence you need to multiply log(n) times. Which is O(log n * k ^ 3 + log n * calculation_cost_of_power_of_M())= O(log n * k ^ 3 + log n * log n * k ^ 3)= O(log n * log n * k ^ 3)Yes, seems a little more costlier than O(log n * k ^ 3).Hope this helps.
 Re: SPOJ :: TETRAHRD (response to post by emotionalBlind) | Reply Where do you my code is taking more time?? . I think mine is O( (k^3+k^2)logn) + some constants. Plzzz Help I've used [cpp] tag now.Please see it once
 Re: SPOJ :: TETRAHRD (response to post by lalitloc) | Reply Could you please explain your algorithm so that it would be easier to understand?
 Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm SPOJ :: TETRAHRD Previous Thread  |  Next Thread [ 1 2 ]    NEXT >