Tile Stacking Problem

A stable tower of height n is a tower consisting of exactly n tiles of unit height stacked vertically in such a way, that no bigger tile is placed on a smaller tile. An example is shown below:

We have infinite number of tiles of sizes 1, 2, …, m. The task is calculate the number of different stable tower of height n that can be built from these tiles, with a restriction that you can use at most k tiles of each size in the tower.

Note: Two tower of height n are different if and only if there exists a height h (1 <= h <= n), such that the towers have tiles of different sizes at height h.

Examples:

Input : n = 3, m = 3, k = 1.
Output : 1
Possible sequences: { 1, 2, 3}. 
Hence answer is 1.

Input : n = 3, m = 3, k = 1.
Output : 7
{1, 1, 2}, {1, 1, 3}, {1, 2, 2},
{1, 2, 3}, {1, 3, 3}, {2, 2, 3}, 
{2, 3, 3}.

We basically need to count number of decreasing sequences of length n using numbers from 1 to m where every number can be used at most k times. We can recursively compute count for n using count for n-1.

The idea is to use Dynamic Programming. Declare a 2D array dp[][], where each state dp[i][j] denotes the number of decreasing sequences of length i using numbers from j to m. We need to take care of the fact that a number can be used a most k times. This can be done by considering 1 to k occurrences of a number. Hence our recurrence relation becomes:

Also, we can use the fact that for a fixed j we are using the consecutive values of previous k values of i. Hence, we can maintain a prefix sum array for each state. Now we have got rid of the k factor for each state.

Below is the C++ implemantation of this approach:

// CPP program to find number of ways to make stable
// tower of given height.
#include <bits/stdc++.h>
using namespace std;
#define N 100

int possibleWays(int n, int m, int k)
{
    int dp[N][N];
    int presum[N][N];
    memset(dp, 0, sizeof dp);
    memset(presum, 0, sizeof presum);

    // Initialing 0th row to 0.
    for (int i = 1; i < n + 1; i++) {
        dp[0][i] = 0;
        presum[0][i] = 1;
    }

    // Initialing 0th column to 0.
    for (int i = 0; i < m + 1; i++)
        presum[i][0] = dp[i][0] = 1;

    // For each row from 1 to m
    for (int i = 1; i < m + 1; i++) {

        // For each column from 1 to n.
        for (int j = 1; j < n + 1; j++) {

            // Initialing dp[i][j] to presum of (i - 1, j).
            dp[i][j] = presum[i - 1][j];
            if (j > k) {
                dp[i][j] -= presum[i - 1][j - k - 1];
            }
        }

        // Calculating presum for each i, 1 <= i <= n.
        for (int j = 1; j < n + 1; j++)
            presum[i][j] = dp[i][j] + presum[i][j - 1];
    }

    return dp[m][n];
}

// Driver Program
int main()
{
    int n = 3, m = 3, k = 2;
    cout << possibleWays(n, m, k) << endl;
    return 0;
}

Output:

7

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/tile-stacking-problem/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar