Phân tích: Box Factory

Bài toán này là một biến thể của bài toán Longest Common Subsequence (Dãy con chung dài nhất), nhằm tìm chuỗi ký tự dài nhất xuất hiện dưới dạng dãy con của cả hai chuỗi (một chuỗi \(S\) là dãy con của chuỗi \(T\) nếu \(S\) xuất hiện trong \(T\), có thể có thêm các ký tự khác xen kẽ giữa các phần tử của \(S\)). Trong trường hợp này, "chuỗi" thứ nhất là trình tự các loại của từng chiếc hộp được sản xuất, và "chuỗi" thứ hai là trình tự các loại của từng món đồ chơi.

Một thuật toán quy hoạch động cho bài toán này là tìm số lượng đồ chơi tối đa có thể đặt vào hộp bằng cách sử dụng \(x\) hộp đầu tiên và \(y\) món đồ chơi đầu tiên. Gọi giá trị này là \(f[x][y]\). Khi đó \(f[x][y]\) bằng giá trị lớn nhất của:

• \(f[x-1][y]\)
• \(f[x][y-1]\)
• \(f[x-1][y-1] + 1\)

Trường hợp cuối cùng chỉ áp dụng nếu loại của hộp thứ \(x\) bằng loại của món đồ chơi thứ \(y\). Ba trường hợp này tương ứng với hành động cuối cùng là bỏ một chiếc hộp, bỏ một món đồ chơi, và đặt một món đồ chơi vào một chiếc hộp khớp loại.

Tuy nhiên, mặc dù số lượng các đoạn (run) hộp và đồ chơi là nhỏ, tổng số lượng hộp và đồ chơi có thể rất lớn, vì vậy thuật toán này không khả thi. Nhưng chúng ta có thể sửa đổi nó để \(f[x][y]\) là số lượng đồ chơi tối đa có thể đặt vào hộp bằng cách sử dụng \(x\) đoạn hộp đầu tiên và \(y\) đoạn đồ chơi đầu tiên. Bây giờ \(f[x][y]\) là giá trị lớn nhất của:

• \(f[x-1][y]\)
• \(f[x][y-1]\)
• \(f[a][b] + g(a, b, x, y)\), với mọi \(a < x, b < y\)

Tương tự như trước, trường hợp cuối cùng chỉ áp dụng nếu loại của đoạn hộp \(x\) khớp với loại của đoạn đồ chơi \(y\). Nó tương ứng với việc chỉ sử dụng các hộp có loại đó trong các đoạn từ \(a+1\) đến \(x\), và các đồ chơi có loại đó trong các đoạn từ \(b+1\) đến \(y\). \(g(a, b, x, y)\) là giá trị nhỏ nhất giữa tổng số lượng các đồ chơi đó và tổng số lượng các hộp đó, chính là số lượng đồ chơi có thể đóng hộp trong phạm vi đó.

Thuật toán này có độ phức tạp \(O(N^2 M^2)\) (hoặc \(O(n^4)\) nếu \(N, M \le n\)). Một cải tiến khác có thể giảm độ phức tạp xuống còn \(O(n^3)\), phần này xin dành cho độc giả tự tìm hiểu!

Dựa trên phân tích chính thức của Google Code Jam.