Phân tích: Doubly-sorted Grid

Đây là một bài toán đếm, với kích thước bảng không quá lớn. Bài toán gợi ý ngay về quy hoạch động trên một không gian trạng thái có số lượng lớn theo hàm mũ. Và thực tế đúng là như vậy.

Theo giới hạn của bài toán, giả sử kích thước lớn hơn giữa \(m\) và \(n\) là size. Một giải pháp với \(2^{2 \cdot \text{size}}\) trạng thái là ổn, trong khi một giải pháp với \(2^{4 \cdot \text{size}}\) trạng thái có lẽ chỉ tốt cho bộ dữ liệu nhỏ. Tuy nhiên, đối với những người thường xuyên thi lập trình, có nhiều cách thông thường để định nghĩa các trạng thái cho các bài toán lưới tương tự rơi vào trường hợp sau.

Vì vậy, phần then chốt của bài toán là tìm ra không gian trạng thái phù hợp. Một khi đã tìm thấy, các thí sinh chắc chắn có thể thực hiện giải pháp quy hoạch động một cách dễ dàng.

Hình ảnh cơ bản ở đây là các đường đi trên lưới (lattice paths). Cụ thể, hãy xem xét, trong một lưới được sắp xếp kép, tất cả các chữ cái nhỏ hơn hoặc bằng một ký tự cụ thể. Chúng tạo thành một vùng đóng hướng lên phía góc trên bên trái. Nói cách khác, nếu chữ cái tại \((r, c)\) không lớn hơn ký tự đã định, thì chữ cái tại \((r', c')\) cũng vậy, nếu \(r' \le r\) và \(c' \le c\). Kết quả là, ranh giới ngăn cách vùng này và phần còn lại của lưới tạo thành một đường đi đơn điệu từ góc dưới bên trái đến góc trên bên phải, và chỉ có thể đi về phía Bắc (lên trên) hoặc phía Đông (sang phải). Đây là một chủ đề quen thuộc -- có tổng cộng \(\binom{m+n}{m}\) đường đi như vậy. Hãy gọi chúng là đường đi đơn điệu. Đối với hai đường đi đơn điệu, ta nói một đường thống trị đường kia nếu nó không bao giờ nằm dưới đường kia. Bất kỳ lưới sắp xếp kép nào cũng tương ứng 1-1 với 26 đường đi đơn điệu (một số có thể trùng nhau), mỗi đường cho một chữ cái, và đường đi cho chữ cái lớn hơn thống trị các đường đi cho các chữ cái nhỏ hơn. Hình bên trái dưới đây mô tả tình huống khi có ba chữ cái; và các ranh giới đơn điệu cho 'a' và 'b' được tô đậm.

Tiến thêm một bước nữa. Hãy tập trung không chỉ vào ranh giới chính xác cho một chữ cái mà vào bất kỳ đường đi đơn điệu nào. Với bất kỳ đường đi đơn điệu \(P\) và bất kỳ chữ cái \(c\) nào, định nghĩa:

Đối với bất kỳ đường đi đơn điệu nào trừ đường đi bị thống trị nhiều nhất, chúng ta có một hoặc nhiều điểm cực đại, đó là các điểm mà đường đi đi sang hướng Đông rồi sau đó là một bước đi lên trên. Trong hình thứ hai ở trên, chúng ta làm nổi bật một đường đi đơn điệu với các điểm cực đại của nó được tô màu. Để tính \(dp[P][c]\), chúng ta có thể chia tình huống thành hai trường hợp:

1. Chữ cái \(c\) không xuất hiện chút nào. Có \(dp[P][c-1]\) cách để làm điều này.
2. Ngược lại, \(c\) phải xuất hiện ở ít nhất một trong các điểm cực đại của \(P\). Đối với mỗi tập con không rỗng của các điểm cực đại, chúng ta có thể gán chữ cái \(c\) cho chúng, giảm nhiệm vụ của chúng ta xuống \(dp[P'][c]\), trong đó \(P'\) là một đường đi chỉ khác \(P\) ở tập hợp các điểm cực đại đó. Chúng ta sử dụng công thức bao hàm-loại trừ trên tất cả các tập con không rỗng để tính toán đóng góp cho \(dp[P][c]\) trong trường hợp này.

Giải pháp như vậy tương đối trực quan và đủ nhanh theo các ràng buộc của chúng ta. Bằng cách thêm một biến phụ, người ta có thể tìm thấy một giải pháp nhanh hơn. Bây giờ hãy tinh chỉnh:

Chúng tôi để lại các chi tiết cài đặt như một bài tập dễ dàng cho độc giả quan tâm. Chúng tôi đề cập rằng, khi \(m=n\), số lượng trạng thái là \(26 \cdot \binom{2n}{n} \cdot n = \Theta(4^n n^{0.5})\). Mặc dù việc tính toán một giá trị \(dp[P][c][k]\) duy nhất có thể liên quan đến tối đa \(n\) bước, thời gian chạy có thể được chứng minh là \(\Theta(4^n n^{0.5})\) bằng một phân tích trừ dần đơn giản -- đối với \(P\) và \(c\) cố định, chúng ta cần tổng cộng \(O(n)\) bước để tính bảng cho tất cả \(k\).

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