JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
SPOJ SEQ | Reply
Hi Guys,
i am trying to solve https://www.spoj.pl/problems/SEQ/
i came with a O(NK) solution, below one
#include<stdio.h>
typedef long long int LL;
int main()
{
    int t,i,k,j;
    LL a[11];
    LL c[11];
    LL n;
    LL n2;
    LL temp;
    LL mod=1000000000ll;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d",&k);
       for(i=1;i<=k;i++)
           scanf("%lli",&a[i]);
       for(i=1;i<=k;i++)
         scanf("%lli",&c[i]);
       scanf("%lli",&n);
       n2=(long long int)k;
       if(n<=k)
       {
          printf("%lli\n",a[n]);
       }
       else
       {
           while(n2<n)
           {
               j=k;
               temp=0ll;
               for(i=1;i<k;i++)
               {
                   temp=(temp+((a[i]*c[j])%mod))%mod;
                   j--;  
                   a[i]=a[i+1];         
               }
               a[k]=(temp+((a[k]*c[1])%mod))%mod;               
               n2++;
           }
           printf("%lli\n",a[k]);
       }
    }//end of while
    return 0;
}

its slow - TLE
where can i optimize my code?
Thanks.
Re: SPOJ SEQ (response to post by javasoul) | Reply
The problem is not the code, but the idea of simulating each step. Write a matrix A such that A * v_i = v_(i+1), where v_i is the vector (a_i, a_(i-1), ..., a_(i-k+1)), then use exponentiation by squaring to calculate A^(n-k); finally, compute A^(n-k) * v_k to get the desired answer in O(k^3 log n) time.

Edit: The Wikipedia article to which I linked is needlessly complicated. Reading the "Underlying idea" section should be enough (and perhaps the "Example implementations" section if you want examples).
Re: SPOJ SEQ (response to post by MauricioC) | Reply
Hi MauricioC,
   Here i am trying to understand it,
   Take this example
   3
   1 2 3
   4 5 6
   6
Here n=6,k=3,a1=1,a2=2,a3=3,a4=28,a5=139,a6=714(ans)
 so to take AXv_1=v_2;
  so A={4,
        5,
        6}
  &v_1=[3,2,1]
  so v_2={12,
	  10,
	  6} =28?
so i have the correct A?
 then A^(6-3)=A^3 = [64,125,216]
   v_k =?
?????

sorry, i didnt get it.. -;)
Re: SPOJ SEQ (response to post by javasoul) | Reply
I think you have some misconceptions - check this tutorial, maybe it will clear the things for you a little bit:

http://www.topcoder.com/tc?module=Static&d1=features&d2=010408

Before that you should probably read a bit about matrices and matrix multiplication.
Re: SPOJ SEQ (response to post by darko_aleksic) | Reply
ok. Let me try it.. Thanks.
yes i did a wrong mat mul,
a[3X1] & v1[1X3] = v2[3X3] is not required
should be a[1X3] & v1[3X1] = v2[1X1]??
i am reading.. thanks..
Re: SPOJ SEQ (response to post by javasoul) | Reply
A must be [KxK] in order to satisfy A * v_i = v_i+1 (where vectors are kx1)
Re: SPOJ SEQ (response to post by darko_aleksic) | Reply
Thanks for the help.
Here is my program:
#include<stdio.h>
#define end scanf("%s",read)
 
typedef long long int LL;
LL mat[11][11];
LL mat2[11][11];
LL tempmat[11][11];
 
LL v0[11];
LL mod=1000000000ll;
int k;
 
//multiply the matrix with the base vector v0
void mulwithbase()
{ int a,b,c;
  LL temp[11];
         for(a=0;a<k;a++)
         {
            temp[a]=0ll;
               for(c=0;c<k;c++){
                  //temp[a]=(temp[a]+((v0[c]*mat2[a][c])%mod))%mod;                  
                  temp[a]+=v0[c]*mat2[a][c];                  
                  temp[a]%=mod;
               }
         }
          for(a=0;a<k;a++)
              v0[a]=temp[a];
    return;
}
 
//multiply the matrix with the base matrix once to handle power od odd number
void mulonce()
{
     int a,b,c;
         for(a=0;a<k;a++)         
            for(b=0;b<k;b++)
            {
               tempmat[a][b]=0ll;
               for(c=0;c<k;c++){
                  //tempmat[a][b]=(tempmat[a][b]+((mat2[a][c]*mat[c][b])%mod))%mod;                  
                  tempmat[a][b]+=mat2[a][c]*mat[c][b];
                  tempmat[a][b]%=mod;
               }
            }          
          for(a=0;a<k;a++)
            for(b=0;b<k;b++)
              mat2[a][b]=tempmat[a][b];
    return;
}
 
//matrix mat2 to the power of p
void pow2(long long int p)
{
     int a,b,c,d;
     int monce=0;
     while(p>1ll){       
       if(p%2ll==1ll)
       {
          monce=1;
          p--;
       }else 
         monce=0;
        
       if(p%2ll==0ll)
       {
         for(a=0;a<k;a++)
         {
            for(b=0;b<k;b++)
            {
               tempmat[a][b]=0ll;
               for(c=0;c<k;c++){
                  //tempmat[a][b]=(tempmat[a][b]+((mat2[a][c]*mat2[c][b])%mod))%mod;                  
                  tempmat[a][b]+=mat2[a][c]*mat2[c][b];
                  tempmat[a][b]%=mod;
               }
            }
         }
          for(a=0;a<k;a++)
            for(b=0;b<k;b++)
              mat2[a][b]=tempmat[a][b];
       if(monce)
          mulonce();          
         p/=2ll;
       }
     }
     return;
}
 
int main()
{
    int t,i,j,row,col,k2;
    for(i=0;i<11;i++)
      for(j=0;j<11;j++)
        mat[i][j]=0ll;
        
    for(i=1,j=0;i<11;i++,j++)
      if(j<11)
       mat[i][j]=1ll;    
      
    LL a[11];
    LL c[11];
    LL n;
    LL n2;
    LL temp;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d",&k);
       k2=k-1;
       for(i=1;i<=k;i++){
           scanf("%lli",&a[i]);
           v0[k2--]=a[i];
       }
       for(i=1;i<=k;i++){
         scanf("%lli",&c[i]);
         mat[0][i-1]=c[i];
       }
       scanf("%lli",&n);
       n2=k*1ll;
       if(n<=k)
          printf("%lli\n",a[n]);
       else
       {
           n2=n-n2;
               for(i=0;i<11;i++)
                 for(j=0;j<11;j++)
                     mat2[i][j]=mat[i][j];                   
           pow2(n2);
           mulwithbase();
           printf("%lli\n",v0[0]);           
       }
    }//end of while
    return 0;
}

i tried.. couldnot able to find where the problem is, its failing for the i/p:
3
24 354 6
56 57 465
98765432
Expected O/p:257599514
But producing a wrong o/p: 960734616
For other small testcases its passing (atleast with wot ever i tried)
donno where is the bug..Pls help me..
Thanks..
Re: SPOJ SEQ (response to post by javasoul) | Reply
Your algorithm seems to exponentiate to the wrong power. For example, is your power is (in base 2) 110000, you start with A, then square it (A^2), square it again (A^4), square it again (A^8), then again (A^16), then square and multiply by A (A^33) then stop, but 33 is not 110000.

That is mostly because you're thinking of bits in the wrong order. You're actually exponentiating to 100001, which is a number obtained by reversing all but the most significant digit of the intended exponent.
Re: SPOJ SEQ (response to post by MauricioC) | Reply
Thank you MauricioC. Thank you so much. Got AC!!!
Thanks to darko_aleksic also.
Re: SPOJ SEQ (response to post by javasoul) | Reply
hey there I am also trying to implement the same logic. Still getting WA.

long long mat[11][11];
long long res[11][11];
long long previous[11]={0};
//code to raise a matrix res to the power n
void mulmat(long long res[11][11],int n)
{
if(n==1)return ;
if(n==2){long long temp[11][11];
for(int i=0;i<11;i++)
for(int j=0;j<11;j++)
temp[i][j]=0;
for(int i=0;i<11;i++)
for(int j=0;j<11;j++)
{
for(int k=0;k<11;k++)
{
temp[i][j]+=(res[i][k]*res[k][j])%mod;
temp[i][j]%=mod;
}
}
for(int i=0;i<11;i++)
for(int j=0;j<11;j++)
res[i][j]=temp[i][j];
return ;
}
if(n%2==0){ mulmat(res,n/2);
mulmat(res,2);
}
else
{
mulmat(res,(n-1)/2);
mulmat(res,2);
long long temp[11][11];
for(int i=0;i<11;i++)
for(int j=0;j<11;j++)
temp[i][j]=0;
for(int i=0;i<11;i++)
for(int j=0;j<11;j++)
{
for(int k=0;k<11;k++)
{
temp[i][j]+=(res[i][k]*mat[k][j])%mod;
temp[i][j]%=mod;
}
}

for(int i=0;i<11;i++)
for(int j=0;j<11;j++)
res[i][j]=temp[i][j];
return;
}
}

int main()
{

int n;
cin>>n;
while(n--){
for(int i=1;i<11;i++)
{previous[i]=0;
for(int j=0;j<11;j++)
{if(j+1!=i){res[i][j]=0;
mat[i][j]=0;
}
else
{res[i][j]=1;
mat[i][j]=1;
}
}}
previous[0]=0;
int order;
cin>>order;
int loo=order;

while(loo)
{ cin>>previous[loo-1];loo--; }
loo=order;
while(loo)
{ cin>>mat[0][order-loo];res[0][order-loo]=mat[0][order-loo];loo--; }
int nth;
cin>>nth;
long long ans=0;

if(nth<=order)
{cout<<previous[order-nth]><<endl;continue;}

else
{ mulmat(res,nth-order);


//multiplying first row of resultant matrix with the column vector and summing up terms

for(int i=0;i<11;i++)
{ans+=(res[0][i]*previous[i])%mod;
ans%=mod;
}
}

cout<<ans><<endl;
}

}
Re: SPOJ SEQ (response to post by javasoul) | Reply
whats the concept behind using temp=011 ..??
actually i'm new this is my first dp prob..!!
Re: SPOJ SEQ (response to post by javasoul) | Reply
SIR CAN U PLZ ELABOTATE
//tempmat[a][b]=(tempmat[a][b]+((mat2[a][c]*mat2[c][b])%mod))%mod;
WHY USING 10^9+011
Re: SPOJ SEQ (response to post by javasoul) | Reply
Can you please find why my code is giving WA.

#include <bits/stdc++.h>
using namespace std;

int test, k, n;
int b[10], c[10];
static long long int matrix[10][10];
long long int res[10][10];
long long int MOD = 1000000000ll;

//This is a customized matrix multiplication, result is stored again in matrix a
void matrixMultiplication(long long int a[][10], long long int b[][10]){
long long int c[k][k];
for(int i = 0; i < k; ++i){
for(int j = 0; j < k; ++j){
c[i][j] = 0;
for(int l = 0; l < k; ++l)
c[i][j] = (c[i][j] + (a[i][l] * b[l][j]) % MOD) % MOD;
}
}
for(int i = 0; i < k; ++i)
for(int j = 0; j < k; ++j)
a[i][j] = c[i][j];
}

//Here base matrix is "matrix" and power is "n"
void matrixExponentiation(){
while(n > 0){
if(n & 1)
matrixMultiplication(res, matrix); //res = res * base;
matrixMultiplication(matrix, matrix); //base = base * base;
n = n / 2;
}
}

long long int compute(){
if(n <= k)
return b[n - 1];
n = n - k;
matrixExponentiation();
long long int ans = 0;
for(int i = 0; i < k; ++i)
ans = (ans + (res[0][i] * b[k - i - 1]) % MOD) % MOD;
return ans;
}

int main(){
ios_base::sync_with_stdio(false);
for (int i = 1; i < 10; ++i)
matrix[i][i - 1] = 1;
cin >> test;
while(test--){
cin >> k;
for(int i = 0; i < k; ++i)
cin >> b[i];
for(int i = 0; i < k; ++i){
cin >> c[i];
matrix[0][i] = c[i];
}
cin >> n;
for(int i = 0; i < k; ++i)
for(int j = 0; j < k; ++j)
res[i][j] = (i == j);
cout << compute() << endl;
}
return 0;
}
RSS