I m unable to understand the output of this question

#1

please explain how to proceed recursively …here is something ive done …check my code at https://ide.codingblocks.com/s/148171

#2

it is written in output format that …Print answer for every test case in a new line modulo 10^9+7.

#3

what is the meaning of this output format ??

#4

Hello @Ignitor,

This means that you have to modulus(%) your answer for each test case i.e. the number of ways to tile the floor with tiles of size 1 x m, with 1000000007 (i.e. 10^9+7).
This is done to limit your answer within the range (0 to 1000000006).

Now, understanding the question:

  1. The area that needs to be tilled is n x m.
  2. The tile has the dimension: 1 x m.
    …You can place tiles either horizontally or vertically:
    2.1. When placed horizontally i.e. 1 x m,
    … it will cover one entire row.
    2.2. When placed vertically i.e. m x 1,
    … it will cover one column and m rows of the area.
    So, you need m such vertical tiles to cover m columns and m rows.

Try to relate it with the Tilling Problem video as explained by Sir.
BTW, you might get TLE after writing your code though it would be logically correct.
This is because it is a problem with Dynamic Programming.

But, I would highly suggest you write the recursive code for it to understand the concept.

Hope, this would help.
Give a like if you are satisfied.

#5

sir…actually …i have’nt understood how to find the number of ways actually …so can you explain me the output for a custom input other than the sample input already given in the question ???

#6

Hello @Ignitor,

The approach is the same as you have been taught in the video: Tilling Problem I
You have to consider only the following while implementing it as the area is n x m instead of m x n:

  1. The area that needs to be tilled is n x m.
  2. The tile has the dimension: 1 x m.
    …You can place tiles either horizontally or vertically:
    2.1. When placed horizontally i.e. 1 x m,
    … it will cover one entire row.
    2.2. When placed vertically i.e. m x 1,
    … it will cover one column and m rows of the area.
    So, you need m such vertical tiles to cover m columns and m rows.

But, you would face TLE in any case.
So, I would suggest you solve this problem once you will complete the DP module of your course.

As you have asked for another test case:
10
39462 25602
29680 52811
83054 93356
29602 66791
14717 78403
55774 64800
67309 8625
29315 41141
7428 17804
86402 1354
Output:
13862
1
1
1
1
1
432069239
1
1
455550640

Hope, this would help.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

sir it is not working for inputs where the output you mentioned in the testcase above is large…please tell me the mistake and how to handle it https://ide.codingblocks.com/s/151897

#9

also please tell that if i will write return false in the base case instead of return true what will happen and why??

#10

Constraints are large and with recursion this problem will give TLE or undesired output for large test cases.
You have to solve it with Dynamic Programming. I would suggest you to return to this question after completing Dynamic Programming lectures. You would be able to solve it easily using DP concepts.

#11

Hey @Ignitor,

Pardon me for replying this late.

  1. There is no use of return statements in your code.

  2. Do as @pratyush63 has suggested.
    This, problem will pass the test case with DP based approach.

:slightly_smiling_face:

#12

so by recursion will it pass only one test case or more since i have got only 20/100 for this question

#13

also please explain me why are you saying that there is no need to use return statements in my code

#14

hey @Ignitor,

  1. yes, it won’t pass more than 1 test case with recursion only.

  2. Are you using the Boolean values that you are returning.
    You should rather use a void function and
    should write only return; to terminate further execution after the base case.

    Also, if you would observe your code carefully.
    Then your code is returning a value only if it reaches the base case.
    Therefore, there is no use of using a function that returns a value in your code.

Hope, this would help.

#15

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.