Counting Towers DP Problem

Jul 22, 2024

Counting Towers DP Problem

Introduction

  • Problem: Construct towers of height n and width 2 using an unlimited supply of rectangular blocks.
  • Objective: Determine the number of different ways to construct such towers, with mirrored and rotated towers counted separately.
  • Series: Part of a dynamic programming (DP) series.

Problem Statement

  • Input: Height (n) of the tower and number of test cases (T).
  • Output: Number of ways to construct a tower of height n and width 2 for every test case.
  • Constraints: Include up to 10^6 operations, and up to 10^8 operations per second.

Approach Overview

  • Complexity Analysis: Consider constraints and ensure solution fits within acceptable time complexity limits (order of n or T * n).
  • Grids and Cells: Investigate different ways to fill a 2xn grid using blocks in a dynamic programming fashion.

Observations and Grid Analysis

  • Filling Grids: Examine possible configurations for filling the grid, identifying constraints at specific cells:
    • Single cell: Occupied by vertical or horizontal blocks.
    • Mirrored Configurations: Must be treated separately.
  • Base Cases: Identify potential base cases where the completions of rows lead to further decisions.

Dynamic Programming States

State Definitions

  • DP States: Define DP[i, 0] and DP[i, 1]:
    • DP[i, 0]: Ways to fill from starting at row i to top with a horizontal block extending.
    • DP[i, 1]: Ways to fill with two vertical blocks extending.

Transition Cases

  1. For DP[i, 0] (horizontal extending):
    • Case 1: Close current horizontal block and start a new one.
    • Case 2: Close current block and start two vertical blocks.
    • Case 3: Extend current horizontal block.
  2. For DP[i, 1] (vertical extending):
    • Case 1: Close left, extend right.
    • Case 2: Close right, extend left.
    • Case 3: Extend both.
    • Case 4: Close both and start two vertical blocks.
    • Case 5: Close both and start a horizontal block.

Transition Equations

  • DP[i, 0] = DP[i+1, 0] + DP[i+1, 1]
  • DP[i, 1] = 2 * DP[i+1, 0] + 4 * DP[i+1, 1]
  • Base Cases: DP[n,0] = 1, DP[n,1] = 1

Final Computation

  • Aggregate results from the base cases to compute the final state for given n in time complexity O(n), for each test case.

Implementation Insights

  • Pre-computation: Compute results for all possible n up to 10^6 in advance, allowing O(1) query per test case.
  • DP Table Initialization: Implement a global DP table to avoid redundant memory allocation across test cases.

Code

T = int(input())
NS = 1000001
MOD = 1000000007
DP = [[0 for _ in range(2)] for _ in range(NS)] 
DP[NS-1][0] = DP[NS-1][1] = 1 
for i in range(NS-2, -1, -1):
    DP[i][0] = (DP[i+1][0] + DP[i+1][1]) % MOD
    DP[i][1] = (2 * DP[i+1][0] + 4 * DP[i+1][1]) % MOD
for _ in range(T):
    n = int(input())
    result = (DP[1][0] + DP[1][1]) % MOD
    print(result)

Homework

  • Optimize: Further optimize to move from T * n to T + n through pre-computation and smarter DP state definitions.

Conclusion

  • Encourage revisiting and re-watching the lecture for detailed understanding and mastery of the problem-solving approach for this complex DP problem.

Full transcript