Mô hình hóa bằng tập các cặp

Ta có thể biểu diễn mỗi nghệ sĩ bằng một cặp số nguyên \((b,r)\), trong đó \(0 \le b \le B\) và \(0 \le r \le R\). Cặp \((0,0)\) không biểu diễn một nghệ sĩ hợp lệ. Tuy nhiên, ta có thể tạm coi nó là hợp lệ: vì luôn có thể thêm \((0,0)\) vào mọi cấu hình hợp lệ chưa chứa cặp này, ta chỉ cần giải bài toán đã sửa đổi rồi trừ 1 khỏi kết quả để thu được đáp án cuối cùng.

Khi đó, ta tập trung tìm kích thước của tập con lớn nhất của

sao cho tổng thành phần thứ nhất của các phần tử bằng \(B\), còn tổng thành phần thứ hai bằng \(R\). Ta gọi một tập các cặp phân biệt thỏa hai điều kiện tổng ứng với các giá trị cụ thể \(b,r\) là một tập hợp lệ theo \(b,r\).

Test Set 1

Trong Test Set 1, trước hết có thể nhận thấy kích thước của \(V\) nhỏ. Vì vậy, ta dùng quy hoạch động, duyệt qua \(V\) và với mỗi cặp quyết định có chọn nó hay không. Trạng thái còn phải lưu lượng cưa xanh và đỏ cần tạo thành.

Đánh số các phần tử của \(V\) theo một thứ tự bất kỳ là \(v_1,v_2,\ldots,v_{(B+1)(R+1)}\). Định nghĩa \(f(i,b,r)\) là kích thước lớn nhất của một tập con hợp lệ theo \(b,r\) lấy từ \(\{v_1,v_2,\ldots,v_i\}\).

Ta có định nghĩa truy hồi:

• \(f(0,0,0)=0\);
• với mọi \(b,r,i\),

Định nghĩa trên chưa xử lý các trạng thái không xác định. Một cách đơn giản là gán mọi trường hợp như vậy bằng \(-\infty\); riêng trong bài này, giá trị \(-B-R\) cũng đủ nhỏ để sử dụng.

Ghi nhớ các giá trị của truy hồi cho thời gian tỉ lệ với kích thước miền của \(f\), tức \((B+1)^2(R+1)^2\), và nhiều khả năng đủ nhanh cho Test Set 1. Nếu cả cách cài đặt lẫn ngôn ngữ bạn chọn đều tương đối chậm, có thể cần thêm một nhận xét để vượt giới hạn thời gian: thật ra hàm \(f\) đồng thời giải mọi bộ test vì tập \(V\) là cố định. Do đó, có thể dùng lại cùng bảng ghi nhớ cho tất cả bộ test, tiết kiệm 99% công việc so với giải từng bộ từ đầu. Thậm chí có thể tính sẵn toàn bộ bảng trước khi nộp và nhúng nó vào mã nguồn, nhưng nói chung cần thận trọng với chiến lược này vì tệp nguồn có thể vượt quá giới hạn 1 MB trong thể lệ cuộc thi.

Test Set 2

Với Test Set 2, chắc chắn cần nhận xét không khởi tạo lại bảng ghi nhớ cho từng bộ test. Tuy nhiên, nhận xét bổ sung quan trọng hơn lại gắn riêng với cấu trúc bài toán.

Trước tiên, gọi một tập là hợp lệ yếu theo \(b,r\) nếu đó là tập các cặp số nguyên không âm phân biệt, tổng các thành phần bên trái không vượt quá \(b\) và tổng các thành phần bên phải không vượt quá \(r\). Hiển nhiên, mọi tập hợp lệ theo \(b,r\) cũng hợp lệ yếu theo \(b,r\), nhưng chiều ngược lại không đúng.

Một tính chất quan trọng là: với \(b,r\) cố định, kích thước \(X\) của tập hợp lệ yếu theo \(b,r\) lớn nhất bằng kích thước \(Y\) của tập hợp lệ theo \(b,r\) lớn nhất. Ta chứng minh như sau:

1. \(Y\le X\), vì mọi tập hợp lệ theo \(b,r\) đều hợp lệ yếu theo \(b,r\).
2. \(X\le Y\): lấy một tập hợp lệ yếu \(S\) có kích thước \(X\). Chọn \((i,j)\in S\) sao cho \(i\) lớn nhất, và trong số các cặp có cùng \(i\) lớn nhất ấy, \(j\) cũng lớn nhất. Gọi \(d_b,d_r\) lần lượt là phần chênh lệch giữa \(b,r\) và tổng các thành phần trái, phải của các cặp trong \(S\). Xây dựng

Theo cách dựng, \(S'\) hợp lệ theo \(b,r\). Do cách chọn cực đại \((i,j)\), cặp \((i+d_b,j+d_r)\) không thuộc \(S\setminus\{(i,j)\}\), nên \(S\) và \(S'\) có cùng kích thước. Suy ra \(X\le Y\).

Tiếp theo, gọi một tập \(S\) là hợp lệ yếu tối tiểu theo \(b,r\) nếu \(S\) hợp lệ yếu theo \(b,r\) và thỏa:

• với mọi \((i,j)\in S\) có \(i>0\), cặp \((i-1,j)\) cũng thuộc \(S\);
• tương tự, với mọi \((i,j)\in S\) có \(j>0\), cặp \((i,j-1)\) cũng thuộc \(S\).

Tương tự lập luận trên, kích thước của tập hợp lệ yếu tối tiểu lớn nhất, với \(b,r\) cố định, bằng kích thước của tập hợp lệ yếu lớn nhất. Thật vậy, từ một tập hợp lệ yếu \(S\) có kích thước \(X\), nếu tồn tại \((i,j)\) vi phạm tính tối tiểu thì thay nó, tùy điều kiện bị vi phạm, bằng \((i-1,j)\) hoặc \((i,j-1)\). Ta vẫn thu được một tập hợp lệ yếu có cùng kích thước. Mỗi bước làm tổng tất cả các thành phần trong mọi cặp của \(S\) giảm nghiêm ngặt, nên quá trình chắc chắn kết thúc; khi đó không còn cặp vi phạm và ta đã dựng được một tập hợp lệ yếu tối tiểu có kích thước \(X\).

Bài toán còn lại là tìm kích thước của tập hợp lệ yếu tối tiểu lớn nhất với \(b,r\) cho trước. Theo điều kiện tối tiểu, nếu \((i,j)\) thuộc tập thì \((i-1,j)\), \((i-2,j)\), \((i,j-1)\), \((i,j-2)\), \((i-1,j-1)\), v.v. cũng thuộc tập. Nói chính xác hơn, sự xuất hiện của \((i,j)\) bắt buộc toàn bộ \((i+1)(j+1)\) cặp trong hình chữ nhật từ \((0,0)\) đến \((i,j)\), kể cả chính nó, phải xuất hiện.

Tổng các thành phần bên trái của riêng các cặp bắt buộc này là

và tương tự, tổng các thành phần bên phải là

Vì vậy, thay vì dùng toàn bộ \(V\) như lời giải trước, ta dùng \(V'\) gồm những cặp trong \(V\) không vượt hai cận này. Khi \(B\) và \(R\) gần nhau, kích thước \(V'\) xấp xỉ \(O(B^{1/3}R^{1/3})\), nhỏ hơn rất nhiều so với kích thước \(O(BR)\) của \(V\). Do đó, độ phức tạp tổng thể của thuật toán thu được cho tất cả bộ test là

đủ nhanh để vượt qua Test Set 2.

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