can someone pls tell me what edge case am i missing CodeChef: Practical coding for everyone
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 13 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]=(2dp[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