 # INOI2002 - WA

Problem : 3 X N tiling
For `N=2` , why is the recurrence not `dp[N-2] + dp[N-3]` ???

It is.
Did you get the base cases right?

Edit: I am assuming you meant k=2.

What are the base cases?
This was my program :
#include<bits/stdc++.h>
using namespace std;

``````int dp1(int n){
if (n%3 == 0){
cout << 1 << "\n";
}
else{
cout << 0 << "\n";
}
}
int dp;
int dp2(int n){
dp = 0;
dp = 1;
dp = 1;
dp = 2;
dp = 2;
if (n <= 4){
cout << dp[n] << "\n";
}

else{
cout << dp[n-2] + dp[n-3] << "\n";
}
}

int main(){
int T;
scanf("%d",&T);
for (int i=0; i<T; i++){
int K,N;
scanf("%d%d",&K,&N);
if (K == 1){
dp1(N);
}

else if (K == 2){
dp2(N);
}

else if (K == 3){
cout << "0" << "\n";
}

}
return 0;
}
``````

(I haven’t figured out K=3 yet, so it’s marked as 0.)

dp = 1;
Wait, where are the for loops?

Oh okay. What is the for loop?

My new code :
#include “iostream”
using namespace std;

``````int dp1(int n){
if (n%3 == 0){
cout << 1 << "\n";
}
else{
cout << 0 << "\n";
}
}
int dp;
int dp2(int n){
dp = 0;
dp = 1;
dp = 1;
dp = 1;
dp = 2;
for (int i = 6; i <= n; i++)
{
dp[i] = dp[i-2] + dp[i-3];
}

return dp[n];
}

int main(){
int T;
scanf("%d",&T);
for (int i=0; i<T; i++){
int K,N;
scanf("%d%d",&K,&N);
if (K == 1){
dp1(N);
}

else if (K == 2){
dp2(N);
}

else if (K == 3){
cout << "0" << "\n";
}

}
return 0;
}
``````

But why isn’t this working too?

``````cout<<dp2(n)<<"\n";
``````

you’re returning a value but not actually outputting it.

Still WA !!!
#include
using namespace std;

``````int dp1(int n){
if (n%3 == 0){
cout << 1 << "\n";
}
else{
cout << 0 << "\n";
}
}
int dp;
int dp2(int n){
dp = 0;
dp = 1;
dp = 1;
dp = 1;
dp = 2;
for (int i = 6; i <= n; i++)
{
dp[i] = dp[i-2] + dp[i-3];
}

cout << dp[n] << "\n";
}

int main(){
int T;
scanf("%d",&T);
for (int i=0; i<T; i++){
int K,N;
scanf("%d%d",&K,&N);
if (K == 1){
dp1(N);
}

else if (K == 2){
dp2(N);
}

else if (K == 3){
cout << "0" << "\n";
}

}
return 0;
}
``````

or

``````#include <iostream>
using namespace std;

int dp1(int n){
if (n%3 == 0){
cout << 1 << "\n";
}
else{
cout << 0 << "\n";
}
}
int dp;
int dp2(int n){
dp = 0;
dp = 1;
dp = 1;
dp = 1;
dp = 2;
for (int i = 6; i <= n; i++)
{
dp[i] = dp[i-2] + dp[i-3];
}

return dp[n];
}

int main(){
int T;
scanf("%d",&T);
for (int i=0; i<T; i++){
int K,N;
scanf("%d%d",&K,&N);
if (K == 1){
dp1(N);
}

else if (K == 2){
cout << dp2(N) <<"\n";
}

else if (K == 3){
cout << "0" << "\n";
}

}
return 0;
}``````

You have to return the answer % (1e9 + 7). That is written in the question. On doing that, it got accepted.
Your 32 points submission:
https://www.codechef.com/viewsolution/30217950

Spoilers

The 100 point solution is quite hard. You HAVE to do it on pen and paper, else you will mess it up.