JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 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<stdio.h>
#include<stdlib.h>
#include<vector>
 
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<k;i++)
	{
		for(j=0;j<k;j++)
		{
				 sum=0;
			for(x=0;x<k;x++)
			{
				if(n==0)
				{
					sum+=(a[i][x]*a[x][j])%m;
				//	printf("sum is %lld\n",sum);
 
				}
				if(n==1)
				{
					sum+= (a[i][x]*b[x][j])%m;
				//	printf("sum is %lld\n",sum);
				}
				d[i][j]=sum%m;
					//printf("d[%d][%d]  is %lld\n",i,j,d[i][j]);
			}
		}
	}
	for(i=0;i<k;i++)
	{
		for(j=0;j<k;j++)
		{
			a[i][j]=d[i][j];
		}
	}
	return ;
}
 
I'm storing the intermediate matrices M_x in 2-D array p[][] .I can store 1000000 such matrices.
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<stdio.h>
#include<stdlib.h>
#include<vector>
 
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<k;i++)
{
for(j=0;j<k;j++)
{
sum=0;
for(x=0;x<k;x++)
{
if(n==0)
{
sum+=(a[i][x]*a[x][j])%m;
//	printf("sum is %lld\n",sum);
 
}
if(n==1)
{
sum+= (a[i][x]*b[x][j])%m;
//	printf("sum is %lld\n",sum);
}
d[i][j]=sum%m;
//printf("d[%d][%d] is %lld\n",i,j,d[i][j]);
}
}
}
for(i=0;i<k;i++)
{
for(j=0;j<k;j++)
{
a[i][j]=d[i][j];
}
}
return ;
}
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 ^ n

M ^ 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?
[ 1 2 ]    NEXT >

RSS