Tiling problem 2 doubt

#1

#include
#define ll long long int
using namespace std;
ll recursion(ll n,ll m)
{
if(n==1 || n==m)
return n;
else
return recursion(n-1,m)+recursion(n-m,m);
}
int main() {
ll t;
cin>>t;
for(int j=0;j<t;j++)
{
ll n;
ll m;
cin>>n>>m;
if(n<m)
swap(n,m);
ll total=recursion(n,m);
cout<<total<<endl;
}
return 0;
}

#2

@checkmate112 try to solve dynamic programming else you will get tle

#3

Hi Karthik, pls see that your recurrence relation and base case is incorrect. First correct them pls and after that try applying Dynamic Programming to reduce time complexity.

Hope this helps :slight_smile:

#4

Can you help me in the recurrence relation because i am not getting it @proRram

#5

Hi Karthik, the recurrence relation here will be:

count(n) = {
1, 1 < = n < m ,
2, n = m ,
count(n-1) + count(n-m), m < n
}

Implement this using DP now using above relation and bottom up DP approach.

Pls try the question again now. Hope this helps :slight_smile:

#6

One more doubt is that ki why have we assumed ki we have placed one block in the field and then writing program with reference to that

#7

Karthik we are here using recursion to solve our sub-problems. If we view it in a top down approach, after we keep the first tile we are left with rest of the grid to fill with tiles and hence we solve them afterwards. Placing first block means we have begun one of the possible arrangements.

#8

ohh okay got it thanks for the help.

#9

for testcase 2 3 i am getting output 3 but the sample output is giving 1 and i have tried by calculating it manually as well and still its giving me 3.

#10

No Karthik, there is only 1 way you can place 1x3 tile in a 2x3 area. By putting it like this:
28%20PM

And all other ways are impossible. For example:

00%20PM
00%20PM1290×694 22.3 KB

I hope you understand now why there is only 1 possible way for 2x3.

#11

Hey
As you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.

#12

I am getting wrong answer. Can you please check the code?

#include
#define ll long long int
using namespace std;
ll countTiles(ll n, ll m)
{
ll c[n + 1];
c[0] = 0;
c[1] = 1;
for (ll i = 2; i <= n; i++) {
if (i > m)
c[i] = c[i - 1] + c[i - m];
else if (i < m)
c[i] = 1;
else
c[i] = 2;
}

return c[n];

}
int main() {
ll t;
cin>>t;
while(t–)
{
ll n,m;
cin>>n>>m;
cout<<countTiles(n,m)%1000000007<<endl;
}
return 0;
}