Tiling Problem - II

#1

Timelimit exceede in 3 out of 4 testcases. Please help me with an efficient approach.

#2

Let f(n ) denote the no. of ways to place tiling n×m grid. Then , there arise two cases:-

  1. if the last tile is placed vertically , then f(n - 1).
  2. if last row is filled with horizontal tiles, then f(n - m).

Thus, f(n)= f(n -1)+f(n-m)

#3

I had also done the same thing in a reversed way.

#4

But your code isn’t memorized.

#5

What about this code? Same result. TLE in testcases

#6

This concept is alright. But memoize your code. Use either a HashMap or bottom up DP.

#7

Why this code too is giving timelimit. I used 2D array as Recursive storage


This one is I think iterative DP approach. This too give timelimit.

#8

You should implement it using 1d DP. There is just going to be 1 state i.e. the no of tiles till now.

#9


What about this? wrong answers in all testcases except one

#10

Change everything to long and it should work

#11 
import java.util.*;

public class Main {
	public static void main(String args[]) {

		Scanner scn = new Scanner(System.in);
		int t = scn.nextInt();
		while (t-- > 0) {
			int n = scn.nextInt();
			int m = scn.nextInt();
			System.out.println(tiling(n, m));
		}
	}

	public static long tiling(int n, int m) {
		long[] strg = new long[n + 1];
		strg[0] = 1;
		for (int i = 1; i <= n; i++) {
			strg[i] = strg[i - 1] + ((i - m < 0) ? 0 : strg[i - m]);
		}
		return strg[n];
	}
}

This gives wrong answer

#12

You need to take the answer modulo 10^9 + 7. Read the question again.

#13 
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String args[]) {

		Scanner scn = new Scanner(System.in);
		int t = scn.nextInt();
		while (t-- > 0) {
			int n = scn.nextInt();
			int m = scn.nextInt();
			System.out.println(tiling(n, m).mod(new BigInteger("1000000007")));
		}
	}

	public static BigInteger tiling(int n, int m) {
		BigInteger[] strg = new BigInteger[n + 1];
		strg[0] = new BigInteger("1");
		for (int i = 1; i <= n; i++) {
			strg[i] = strg[i - 1].add(((i - m < 0) ? new BigInteger("0") : strg[i - m]));
		}
		return strg[n];
	}
}

long didn’t worked. BigInteger worked

#14

Thanks, my doubt is solved. All testcases passed but first testcase took 2.19 seconds.
Is it ok?

#15

No, you don’t need to use BigInteger. It will give TLE because BigInteger operations are really time - expensive. Just take the mod of the answer right there in the loop where you are calculating the values of DP for each state using a long or an int M = 1e9 + 7

1 Like
#16

Wow, it worked. Thanks for helping me to solve the problem.

#17

Please provide a feedback if you have some time and feel like giving one.

#18

Why ans is moduled by 10^9+7