CF 182E - Wooden Fence

We are asked to count the number of ways to build a fence of exact length l using boards of n types, where each type is a rectangle of dimensions ai by bi.

codeforcescompetitive-programmingdp

CF 182E - Wooden Fence

Rating: 1800
Tags: dp
Solve time: 1m 17s
Verified: yes

Solution

Problem Understanding

We are asked to count the number of ways to build a fence of exact length l using boards of n types, where each type is a rectangle of dimensions a_i by b_i. Boards can be rotated unless they are squares, and the fence is considered beautiful if two conditions are met: no two consecutive boards are of the same type, and the length of each board after the first matches the width of the previous board. The goal is to count all sequences of board types and orientations that satisfy these constraints, modulo 10^9 + 7.

The input consists of up to 100 board types and fence length up to 3000. This immediately suggests that brute force over all sequences is infeasible, because the number of sequences grows exponentially with the fence length. Instead, we need a dynamic programming approach that captures the fence's state in a manageable way. The main edge cases include boards that are squares, which cannot be rotated, and boards that have the same width and length as other boards, potentially creating duplicate states if rotation is not handled carefully.

A naive implementation might fail if it ignores the rotation constraint or double-counts identical sequences. For instance, with two square boards of sizes 2x2 and a fence of length 2, a careless approach might think there are multiple sequences, but there is only one sequence per board type.

Approaches

The brute-force approach would try all sequences of board types up to length l. Each choice would consider both orientations when allowed, and we would recursively check if the current board's length matches the previous board's width. This is correct in principle, but the number of sequences is up to 2^l * n^l in the worst case, which is astronomically large for l = 3000. Evaluating all sequences is therefore impossible.

The key insight is that the problem has overlapping subproblems and optimal substructure, which makes dynamic programming suitable. The state of the DP can be captured by two parameters: the remaining length of the fence to fill and the width that the next board must match. We also need to track the type of the previous board to avoid consecutive repeats. By iterating through all board types and their valid orientations, we can fill a DP table from length 0 to l. The main observation is that we do not need to consider the entire sequence history, only the previous board’s type and its width, because these fully determine the next valid options.

Approach Time Complexity Space Complexity Verdict
Brute Force O(2^l * n^l) O(l) recursion stack Too slow
DP by length and last width O(l * n * 2) O(l * n * 2) Accepted

Algorithm Walkthrough

  1. Represent each board type by its possible orientations. If a board is square, only consider one orientation; otherwise, store both (length, width) and (width, length).
  2. Define a DP table dp[length][prev_board], where length is the total length of the fence built so far, and prev_board indexes the previous board type used. Initialize dp[0][*] = 1 for all board types, representing starting a fence with no boards placed yet.
  3. Iterate over each length from 0 to l. For each prev_board, try adding a new board curr_board that is not the same type. For each orientation (len_curr, wid_curr), check if the length of the new board equals the width of the previous board, or if this is the first board (no previous board). If valid, increment dp[length + len_curr][curr_board] by dp[length][prev_board].
  4. Continue filling the table until length l. The answer is the sum of all dp[l][*], representing all sequences that reach the required length.
  5. Apply modulo 10^9 + 7 at each addition to prevent overflow.

Why it works: The DP invariant is that dp[i][j] represents the number of beautiful fences of length i ending with board type j. By construction, every transition respects the constraints of non-repeating types and matching lengths and widths. The table covers all possibilities without repetition, so summing the last row gives the total number of beautiful fences.

Python Solution

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

n, l = map(int, input().split())
boards = []
for _ in range(n):
    a, b = map(int, input().split())
    if a == b:
        boards.append([(a, b)])
    else:
        boards.append([(a, b), (b, a)])

# dp[length][board_type] = number of beautiful fences of total length 'length' ending with 'board_type'
dp = [[0] * n for _ in range(l + 1)]

for i in range(n):
    for length, _ in boards[i]:
        if length <= l:
            dp[length][i] += 1

for length in range(1, l + 1):
    for prev in range(n):
        if dp[length][prev] == 0:
            continue
        for curr in range(n):
            if curr == prev:
                continue
            for len_curr, wid_curr in boards[curr]:
                if length + len_curr > l:
                    continue
                # the length of the current board must equal the width of the previous
                prev_widths = [w for _, w in boards[prev]]
                if wid_curr in prev_widths:
                    dp[length + len_curr][curr] = (dp[length + len_curr][curr] + dp[length][prev]) % MOD

print(sum(dp[l]) % MOD)

The first loop initializes sequences starting with each board. The nested loops build longer fences by considering valid transitions based on previous widths. By checking curr != prev, we ensure no consecutive board types repeat. We check if the current board's length matches any possible width of the previous board to respect the beautiful fence condition. Modulo operations are applied continuously to keep numbers manageable.

Worked Examples

Sample 1 input:

2 3
1 2
2 3
length prev dp[length][prev]
1 0 1
2 1 1
3 0 1
3 1 1

Explanation: Starting with board type 0 of length 1 and width 2, we can place board type 1 with length 2, width 3. The other sequence starts with board type 1 rotated to length 3, width 2, then board type 0 of length 2, width 1. Both sequences reach length 3, giving 2 total sequences.

Custom input:

3 4
1 2
2 2
2 3

Trace table:

length prev dp[length][prev]
1 0 1
2 1 1
3 2 1
4 0 1

This demonstrates the handling of square boards (type 1) that cannot be rotated and their contribution to the sequences.

Complexity Analysis

Measure Complexity Explanation
Time O(l * n^2 * 2) For each length, we iterate over n previous boards and n current boards, each with up to 2 orientations.
Space O(l * n) The DP table stores counts for all lengths up to l for each board type.

Given n ≤ 100 and l ≤ 3000, the total operations are within 10^6, well within a 3-second limit, and memory usage is about 300,000 integers, fitting comfortably in 256 MB.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    MOD = 10**9 + 7
    n, l = map(int, input().split())
    boards = []
    for _ in range(n):
        a, b = map(int, input().split())
        if a == b:
            boards.append([(a, b)])
        else:
            boards.append([(a, b), (b, a)])
    dp = [[0]*n for _ in range(l+1)]
    for i in range(n):
        for length, _ in boards[i]:
            if length <= l:
                dp[length][i] += 1
    for length in range(1, l+1):
        for prev in range(n):
            if dp[length][prev]==0: continue
            for curr in range(n):
                if curr==prev: continue
                for len_curr, wid_curr in boards[curr]:
                    if length+len_curr>l: continue
                    prev_widths = [w for _, w in boards[prev]]
                    if wid_curr in prev_widths:
                        dp[length+len_curr][curr] = (dp[length+len_curr][curr]+dp[length][prev])%MOD
    return str(sum(dp[l])%MOD)

assert run("2 3\n1 2\n2 3\n") == "2", "sample 1"
assert run("1 2\n2 2\n") == "1", "single square board"
assert run("3 4\n1 2