Phân tích

Kịch bản cơ bản ở đây rất giống với bài toán đổi tiền (change-making problem) truyền thống, ngoại trừ việc đầu vào có thể (và thực tế là được đảm bảo) rất lớn. Một điều kiện về kích thước tối thiểu của đầu vào là rất bất thường đối với một bài toán lập trình thi đấu, và chúng tôi không thêm nó chỉ để cho vui. Giải pháp của chúng tôi thực sự đòi hỏi độ dài hàng rào ít nhất là \(10^{10}\).

Dữ liệu nhỏ (Small Input)

Trước khi đi vào giải pháp thực sự, hãy thảo luận về một cách tiếp cận đơn giản hơn để giải quyết tập dữ liệu nhỏ. Giả sử tấm ván dài nhất có độ dài \(A \le 100\). Ý tưởng chính là chúng ta không bao giờ nên sử dụng nhiều hơn \(A\) tấm ván của bất kỳ kích thước nào nhỏ hơn \(A\). Nếu chúng ta làm vậy, chúng ta có thể thay thế \(A\) tấm ván đó bằng một số lượng ít hơn các tấm ván độ dài \(A\). Và điều đó tất nhiên sẽ là một giải pháp tốt hơn.

Cụ thể, điều này có nghĩa là tổng độ dài của tất cả các tấm ván ngắn hơn tối đa là \(N \cdot A \cdot A \le 1,000,000\). Sử dụng tìm kiếm theo chiều rộng (BFS), chúng ta có thể tìm ra cách tối ưu để chọn các tấm ván này để có được mỗi độ dài trong phạm vi đó. Chi phí để hoàn thành hàng rào bằng cách sử dụng các tấm ván độ dài \(A\) sau đó có thể được tính bằng một phép chia đơn giản.

Nhân tiện, bạn thực sự có thể thay thế \(N \cdot A \cdot A\) bằng chỉ \(A \cdot A\) trong giải pháp trên. Hy vọng bạn sẽ hiểu lý do sau khi đọc phần còn lại của giải pháp!

Dữ liệu lớn (Large Input)

Giải pháp cho dữ liệu nhỏ không thực sự tận dụng được độ dài tối thiểu của hàng rào. Vì vậy, câu hỏi lớn là: làm thế nào chúng ta có thể làm được điều đó?

Giải pháp trước đó đã đưa ra một chút gợi ý. Đối với một hàng rào thực sự dài, việc chúng ta muốn sử dụng tối đa tấm ván dài nhất để bao phủ càng nhiều độ dài càng tốt là điều hợp lý. Vì vậy, giả sử tấm ván dài nhất có độ dài \(A\), và L bằng \(p \cdot A + q\) với các số nguyên \(p, q\) và \(q < A\). (Lưu ý rằng đề bài đảm bảo \(p \ge A\)). Khi đó chúng ta cần thực hiện một trong các việc sau:

• Sử dụng một số lượng \(T_{0,q}\) tấm ván ngắn hơn để tạo ra một hàng rào có độ dài \(0 \cdot A + q\), sau đó sử dụng \(p\) tấm ván độ dài \(A\) để bao phủ phần còn lại.
• Sử dụng một số lượng \(T_{1,q}\) tấm ván ngắn hơn để tạo ra một hàng rào có độ dài \(1 \cdot A + q\), sau đó sử dụng \(p-1\) tấm ván độ dài \(A\) để bao phủ phần còn lại.
• ...
• Sử dụng một số lượng \(T_{p,q}\) tấm ván ngắn hơn để tạo ra một hàng rào có độ dài \(p \cdot A + q\), sau đó sử dụng \(0\) tấm ván độ dài \(A\) để bao phủ phần còn lại.

Vì vậy, chúng ta cần tính \(p + S_{p,q}\) trong đó \(S_{p,q}\) được định nghĩa là \(\min(T_{0,q} - 0, T_{1,q} - 1, \dots, T_{p,q} - p)\). Một cách trực quan, \(S_{p,q}\) có thể được coi là đo lường số lượng tấm ván tối thiểu cần thiết để có được độ dài hàng rào là \(q \pmod A\), tuân theo hai sửa đổi:

• Mỗi khi độ dài tăng thêm \(A\), điều đó có nghĩa là bớt đi một tấm ván độ dài tối đa trong tương lai, vì vậy bạn có thể trừ đi một từ tổng số lượng.
• Tổng độ dài không được phép vượt quá \(p \cdot A + q\).

Và bây giờ, chúng ta có thể cụ thể hóa việc điều kiện L rất lớn giúp đơn giản hóa mọi thứ như thế nào:

Bổ đề: Điều kiện thứ hai trong định nghĩa của \(S_{p,q}\) là không cần thiết.

Chứng minh: Chúng tôi khẳng định rằng \(T_{i,q} - i\) đạt giá trị nhỏ nhất khi \(i \le p\), điều này sẽ chứng minh bổ đề. Vì vậy, hãy xem xét một giá trị \(T_{i,q} - i\) tối thiểu. Khi đó chúng ta có một tập hợp các tấm ván \(b_1, b_2, \dots, b_m\) tạo ra độ dài \(i \cdot A + q\). Nếu \(i > p\), thì \(m > p \ge A\). Nhưng khi đó, tập hợp \(\{b_1, b_1 + b_2, \dots, b_1 + b_2 + \dots + b_m\}\) chứa ít nhất \(A+1\) số, vì vậy có hai số trong số này đồng dư với nhau theo mô-đun \(A\). Trừ chúng đi, chúng ta có thể tìm thấy một tập con không rỗng của \(\{b_1, b_2, \dots, b_m\}\) có tổng là bội số của \(A\). Do đó, chúng ta có thể thay thế tập con đó bằng các tấm ván độ dài \(A\) để có được một giải pháp tốt hơn hẳn, ngụ ý rằng \(T_{i,q} - i\) không thể tối ưu ngay từ đầu!

Được rồi, điều đó rất tốt, nhưng giải pháp là gì? Bổ đề trước đó ngụ ý rằng chúng ta cần tính số lượng tấm ván tối thiểu cần thiết để có được một hàng rào có độ dài \(q \pmod A\), với thực tế là mỗi khi tổng độ dài tăng thêm \(A\), chúng ta sẽ cần ít hơn một tấm ván trong tương lai. (Đối với các hàng rào ngắn hơn, cách tiếp cận này đơn giản là không hoạt động. Thuật toán của chúng ta sẽ tạo ra một hàng rào rất dài với độ dài chính xác theo mô-đun \(A\), và sau đó cố gắng trừ đi các tấm ván độ dài \(A\), điều này tất nhiên là không được phép!)

Dù sao, một khi bài toán đã được giảm bớt theo cách này, nó có thể được thực hiện khá đơn giản bằng tìm kiếm theo chiều rộng (BFS). Đồ thị của chúng ta có một đỉnh cho mỗi số dư theo mô-đun \(A\). Từ mỗi đỉnh, chúng ta thêm một cạnh cho mỗi độ dài tấm ván có thể. Nếu việc thêm tấm ván đó làm tổng độ dài vượt qua bội số tiếp theo của \(A\), thì nó có trọng số 0 (vì ta thêm 1 tấm ván mới nhưng lại bớt được 1 tấm ván độ dài \(A\)). Ngược lại, nó có trọng số 1. Vì vậy, thuật toán cuối cùng là: tính khoảng cách nhỏ nhất trong đồ thị này đến đỉnh \(q\) để có được \(S_{p,q}\), và cuối cùng cộng thêm \(p\).

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