WA in "3*N Tiling" (INOI2002)

can someone pls tell me what edge case am i missing https://www.codechef.com/viewsolution/36216814

2 Likes

Can you explain your code for k = 3? Your code is hard to understand.

@therealnishuz
so i have used 3 dps which are inter connected
dp is the main dp
f[n] is for no of ways of covering 3n lenght grid but leaving one corner (either top or bottom both are included)
g[n] is for leaving 2 squares one int middle and the other either on top or bottom

main dp
i created the dp by taking cases of differnt end piece (ie 13 or 22 31) in length
so for end piece 1
3 we have dp[n-1]
for 31 we can have in 2 ways ye can either have 3 31 pieces which would give dp[n-3] or we can club a 31 an a 22 and here is the part where i used the dp f
a 31 and 22 piece combided would fit a grid with 1 corner missing that is the dp of f

now to define f
i created it in the same way i created the main dp but 13 would work as in the last colummum there is 1 corner missing in f we can have 3 31 pieces so it would be f[n-3] and g[n-1] for using 2*2 as the last piece i noticed that any other set of pieces used as the last pieces would create gaps

now g
in g we can have 3 31 which gives g[n-3] or a combination of 31 and 22 to get dp[n-3] i multiplied it by 2 as i can arrage the 31 and 2*2 in 2 ways and f is not because it is based on g so it would be multiplied automatically

now we have defined everything so i ran a loop after defining the base cases to find dp[n]

i ran my code against an ac code for n=1 to 10000 and it gave the correct ans and even the dps kind of matched

this is a cleaner and main part of my code

ll dp[n+1]={0};
dp[1]=1;
dp[2]=1;
dp[3]=2;
dp[4]=3;
dp[5]=4;
dp[6]=8;
ll f[n+1]={0};
ll g[n+1]={0};
f[1]=0;
f[2]=0;
f[3]=0;
f[4]=2;
g[1]=0;
g[2]=0;
g[3]=2;
g[4]=2;
for(int i=5;i<7;i++){
f[i]=(f[i-3]+g[i-1])%1000000007;
g[i]=(2dp[i-3]+g[i-3])%1000000007;
}
for(int i=7;i<n+1;i++){
f[i]=(f[i-3]+g[i-1])%1000000007;
g[i]=(2
dp[i-3]+g[i-3])%1000000007;
dp[i]=(dp[i-1]+f[i-2]+dp[i-3])%1000000007;
}
cout<<dp[n]<<le;

if you need any more explanation just ask me

There is an issue in your dp[i] relation. You’re right about 1 1x3 tile and 3 3x1 tiles. But, you can stick a 2x2 on the top or bottom and the 3x1 will be where you don’t place it. Notice that they’re symmetric. So your relation for dp[i] should be
dp_i = dp_{i-1} + dp_{i-3} + 2f_{something} (replace something with the correct value because it isn’t clear from your definition of f).

Also, use an ‘x’ to show multiplication. ‘*’ is for italics.

Just compare your answers with mine

AC code
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
const ll p=1e9 + 7;
struct matrix{
    vector<vector<ll>> mat;
    matrix(int n, int m){
        mat.resize(n,vector<ll>(m));
    }
    matrix operator*(matrix a){
        matrix ans(this->mat.size(),a.mat[0].size());
        for(int i=0;i<this->mat.size();i++){
            for(int j=0;j<a.mat[0].size();j++){
                for(int k=0;k<a.mat.size();k++){
                    ans.mat[i][j]+=(this->mat[i][k]*a.mat[k][j])%p;
                    ans.mat[i][j]%=p;
                }
            }
        }
        return ans;
    }
};
matrix matpower(matrix base,ll power){
    matrix ans(base.mat.size(),base.mat.size());
    for(int i=0;i<base.mat.size();i++){
        ans.mat[i][i]=1;
    }
    while(power){
        if(power & 1){
            ans=ans*base;
        }
        base=base*base;
        power>>=1;
    }
    return ans;
}
void solve2(){
    int n;
    cin>>n;
    matrix init(1,3);
    init.mat={{1,0,1}};
    matrix base(3,3);
    base.mat={
    {0,0,1},
    {1,0,1},
    {0,1,0}
    };
    cout<<(init*matpower(base,n)).mat[0][0]<<"\n";

}
void solve(){
    int n;
    cin>>n;
    matrix init(1,9);
    init.mat={{1,0,0,1,0,0,2,0,2}};
    matrix base(9,9);
    base.mat=
    {
    {0,0,0,0,0,0,1,0,2},
    {0,0,0,0,0,0,0,1,0},
    {0,0,0,0,0,0,0,0,1},
    {1,0,0,0,0,0,0,0,0},
    {0,1,0,0,0,0,1,0,0},
    {0,0,1,0,0,0,0,0,0},
    {0,0,0,1,0,0,1,0,0},
    {0,0,0,0,1,0,0,0,0},
    {0,0,0,0,0,1,0,1,0}
    };
    cout<<(init*matpower(base,n-1)).mat[0][0]%p<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >>t;
    //precompute();
    while(t--){
        int k;
        cin>>k;
        if(k==3){
            solve();
        }
        else if(k==1){
            int n;
            cin>>n;
            cout<<(n%3==0)<<"\n";
        }
        else{
            solve2();
        }
    }
}

The answer should diverge before 10
If it doesn’t then it is overflow or you’ve written 1000000007 wrong somewhere

Also learn latex

i solved the prob thanks everyone for replying