INOI2002 - WA

help
1

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

2

It is.
Did you get the base cases right?

Edit: I am assuming you meant k=2.

3

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[10000000];
int dp2(int n){
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 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.)

4

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

5

Oh okay. What is the for loop?

6

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[10000000];
int dp2(int n){
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 1;
	dp[5] = 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?

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

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

8

Still WA !!!
#include
using namespace std;

int dp1(int n){
	if (n%3 == 0){
		cout << 1 << "\n";
	}
	else{
		cout << 0 << "\n";
	}
}
int dp[10000000];
int dp2(int n){
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 1;
	dp[5] = 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[10000000];
int dp2(int n){
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 1;
	dp[5] = 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;
}
9

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.