 # 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;
dp=1;
dp=2;
dp=3;
dp=4;
dp=8;
ll f[n+1]={0};
ll g[n+1]={0};
f=0;
f=0;
f=0;
f=2;
g=0;
g=0;
g=2;
g=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.

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.size());
for(int i=0;i<this->mat.size();i++){
for(int j=0;j<a.mat.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<<"\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%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