Maximizing Stacked Books: DP & LIS Solution for 2023B Problem

Problem Description

Each book is represented by an integer pair (l, w) indicating its length and width. A book A can be placed on top of book B only if both A 's length and width are strictly smaller than B 's. Given a list of books, determine the largest possible number of books that can be stacked together without rotating any book.

Input / Output

Input : a comma‑separated list of integers, e.g. 20,16,15,11,10,10,9,10, which represents the sequence [(20,16),(15,11),(10,10),(9,10)]. Output : a single integer – the maximum stack size, e.g. 3 .

Solution Idea – Transform to LIS

The problem is equivalent to the classic "Russian Doll Envelopes" problem. After sorting the books, the task reduces to finding the longest increasing subsequence (LIS) of the widths.

Sorting Strategy

Sort books by length ascending .

If lengths are equal, sort by width descending . This prevents books with the same length from being placed together in the LIS, which would violate the strict‑increase requirement on length.

After this ordering, any increasing subsequence of widths automatically satisfies the original stacking constraints.

Dynamic Programming for LIS

Let dp[i] be the length of the longest increasing subsequence that ends with the i ‑th book (after sorting). The recurrence is:

for i in range(1, n):
    for j in range(i):
        if books[i][1] > books[j][1]:
            dp[i] = max(dp[j] + 1, dp[i])

Initialize dp with all ones because each book alone forms a subsequence of length 1. The answer is max(dp) .

Reference Implementation (Python)

# 2023B – Book Stacking
# Input format: comma‑separated integers, e.g. "20,16,15,11,10,10,9,10"
lst = list(map(int, input().split(",")))
# Convert to list of (length, width) pairs
books = [(lst[i], lst[i+1]) for i in range(0, len(lst), 2)]
# Sort: length asc, width desc for equal lengths
books.sort(key=lambda item: (item[0], -item[1]))

n = len(books)
# DP array: dp[i] = longest stack ending with books[i]
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if books[i][1] > books[j][1]:
            dp[i] = max(dp[j] + 1, dp[i])
print(max(dp))

Complexity Analysis

Time complexity : Sorting takes O(N log N) . The DP double loop costs O(N²) . The overall complexity is dominated by O(N²) . Space complexity : The DP array uses O(N) additional space.

Key Takeaways

Convert a 2‑dimensional stacking problem into a 1‑dimensional LIS problem by appropriate sorting.

When lengths can be equal, sorting widths in descending order avoids invalid subsequences.

The classic DP formulation for LIS works directly after the transformation.