Phân tích: Quality Food

Nhiều lời giải

Đôi khi người ra đề nghĩ ra những lời giải lớn và phức tạp, rồi hóa ra lại có những cách đơn giản hơn. Ở đây chúng tôi trình bày hai lời giải: cách đơn giản mà nhiều thí sinh đã dùng, và cách phức tạp hơn của tác giả.

Chi phí cho một lần giao hàng là bao nhiêu?

Hãy xem xét chi phí của một lần giao hàng chứa \(K\) bữa ăn. Dễ dàng nhận thấy rằng chúng ta nên đặt mua bữa ăn rẻ nhất có thời gian hết hạn ít nhất là 0, bữa ăn rẻ nhất có thời gian hết hạn ít nhất là 1, bữa ăn rẻ nhất có thời gian hết hạn ít nhất là 2, và cứ tiếp tục như vậy cho đến khi đặt mua bữa ăn rẻ nhất có thời gian hết hạn ít nhất là \(K\). Vì \(K\) có thể rất lớn, chúng ta sẽ giải quyết vấn đề này trong \(O(N \log N)\).

Đầu tiên, chúng ta sắp xếp các loại thức ăn theo giá, và xây dựng một mảng chứa \([(0, 0), (d_1, c_1), (d_2, c_2), \dots]\), trong đó chúng ta nên mua thức ăn có giá \(c_i\) cho các bữa ăn từ ngày \(d_{i-1}\) đến \(d_i\) sau khi chuyến giao hàng đến. Sau đó, chúng ta có thể xử lý mảng đó thành một mảng khác chứa \((d_i, C_i)\), với \(C_i\) là tổng chi phí của một lần giao hàng kéo dài \(d_i\) ngày, và \((C_i - C_{i-1}) / (d_i - d_{i-1}) = c_i\).

Chúng ta chỉ cần thực hiện các bước trên một lần. Khi đã có mảng đó, việc tìm chi phí để một lần giao hàng kéo dài \(K\) ngày là một phép tìm kiếm nhị phân \(O(\log N)\) (hoặc tìm kiếm tuyến tính đơn giản vì hiệu suất không quá khắt khe): tìm \(i\) sao cho \(d_{i-1} \le K < d_i\), và chi phí sẽ là \(C_{i-1} + (K - d_{i-1}) \cdot c_{i-1}\).

Chúng ta gọi hàm đó là SingleDeliveryCost(days), và để thuận tiện, ta định nghĩa SingleDayCost(day) là chi phí để mua bữa ăn rẻ nhất có thời gian hết hạn ít nhất là day. Lưu ý rằng SingleDayCost(a) <= SingleDayCost(b) nếu \(a \le b\), và SingleDeliveryCost(days+1) = SingleDeliveryCost(days) + SingleDayCost(days+1).

Các lần giao hàng nên có kích thước (gần như) bằng nhau

Giả sử chúng ta có một giải pháp có một lần giao hàng \(A\) chứa \(a\) bữa ăn, và một lần giao hàng khác \(B\) chứa \(b\) bữa ăn, với \(b \ge a+2\). Khi đó chi phí cho hai lần giao hàng này là SingleDeliveryCost(a) + SingleDeliveryCost(b). Nếu thay vào đó chúng ta tăng kích thước của \(A\) lên \(a+1\) và giảm kích thước của \(B\) xuống \(b-1\), chúng ta vẫn có tổng số ngày như cũ, nhưng chi phí giao hàng sẽ là:
SingleDeliveryCost(a+1) + SingleDeliveryCost(b-1)
= SingleDeliveryCost(a) + SingleDayCost(a+1) + SingleDeliveryCost(b) - SingleDayCost(b-1)
<= SingleDeliveryCost(a) + SingleDeliveryCost(b) (do SingleDayCost là hàm không giảm).

Điều này cho thấy tất cả các lần giao hàng của chúng ta nên có kích thước \(a\) hoặc \(a+1\) cho một giá trị \(a\) nào đó.

Các lần giao hàng nên có kích thước "thú vị"

Giả sử chúng ta muốn mua tổng cộng \(D\) ngày thức ăn, và muốn biết các lần giao hàng nên lớn bao nhiêu. Xét số lượng lần giao hàng \(X\) sao cho nếu chúng ta nhìn vào kích thước của lần giao hàng lớn nhất, \(\lceil D/X \rceil\), thì \(\lceil D/(X-1) \rceil = \lceil D/X \rceil = \lceil D/(X+1) \rceil\). Trong trường hợp như vậy, việc thêm một lần giao hàng làm thay đổi chi phí một lượng là SingleDeliveryCost(ceil(D/X)) - ceil(D/X) * SingleDayCost(ceil(D/X)). Một trong hai hướng thay đổi số lượng lần giao hàng sẽ không làm tăng chi phí, nghĩa là chúng ta không bao giờ cần cân nhắc các giá trị \(X\) "không thú vị" này.

Điều đó có nghĩa là chúng ta chỉ cần xem xét các số lượng lần giao hàng sao cho nếu thay đổi số lượng giao hàng, chúng ta sẽ làm thay đổi SingleDayCost(ceil(D/X)). Chỉ có khoảng \(2N\) kích thước giao hàng như vậy, và thử tất cả chúng sẽ giải quyết được bài toán trong \(O(N \log N)\).

Cách tiếp cận khác

Một thí sinh chưa tự thuyết phục được về lập luận trên vẫn có cơ hội tốt để giải bài. Trước hết, chúng tôi trình bày một mẹo — “Thay đổi câu hỏi” — có thể dùng dù có nhận ra tính chất trên hay không và có thể làm toán dễ hơn; sau đó là một cách hoàn toàn khác, dù bản thân nó cũng cần một ít toán.

Thay đổi câu hỏi

Thay vì giải trực tiếp bài toán được hỏi, ta có thể dùng một mẹo để giải câu hỏi đơn giản hơn: “Tôi có thể ăn thức ăn chất lượng trong \(D\) ngày không?”. Ta làm điều này bằng cách tìm kiếm nhị phân trên đáp án. Biết đáp án nằm từ \(0\) đến \(M\), ta chỉ cần giải câu hỏi quyết định ấy \(O(\log M)\) lần.

Nên có bao nhiêu lần giao hàng?

Nếu logic của lời giải trước quá phức tạp, cách thay thế này có lẽ cũng không làm bạn vui hơn. Mặt khác, nếu bạn thấy phân tích độ phức tạp chưa có đủ thừa số logarithm hoặc chưa có đủ loại tìm kiếm “-phân”, bạn có thể thích nó. Đây là lời giải ban đầu của chúng tôi; tác giả phần I/O có một niềm tự hào hơi kỳ quặc vì đã góp phần tạo ra một bài mà “tìm kiếm nhị phân trong tìm kiếm tam phân trong tìm kiếm nhị phân” là lời giải hoàn toàn hợp lý.

Ta sẽ tìm kiếm tam phân theo số lần giao hàng để cực tiểu hóa chi phí mua thức ăn chất lượng cho \(D\) ngày. Muốn dùng tìm kiếm tam phân, hàm phải giảm nghiêm ngặt rồi tăng nghiêm ngặt, hoặc ngược lại. Miền xét bắt đầu ở số lần giao hàng \(X\) nhỏ nhất mà ta có thể đặt đủ \(D\) bữa, bất kể đắt đến đâu, và kết thúc tại \(X=D\). Ta sẽ chứng minh hàm giảm rồi tăng trên miền này.

Trước hết, mở rộng SingleDayCost ra số thực. Ta đã biết giá trị tại số nguyên; nội suy tuyến tính giữa chúng và gọi hàm thu được là \(G\). Khi đó chi phí cho \(X\) lần giao hàng và \(D\) ngày, gọi là \(H(X)\), bằng

Ta sắp lấy đạo hàm. Mặc dù \(G\) liên tục, nó không khả vi tại mọi nơi. Có vài cách xử lý; ở đây đi theo con đường của nhà vật lý. Định nghĩa \(G''\) là tổng các hàm delta sao cho tích phân hai lần của \(G''\) theo \(X\) cho lại \(G\). Sau đó, định nghĩa \(G'\) là tích phân của \(G''\), và \(G\) là tích phân của \(G'\). Nhờ vậy ta có thể nói đạo hàm bậc nhất lẫn bậc hai của \(G\) đều không âm. Đừng thử cách này ở nhà, nhất là nếu nhà bạn nằm trong một lớp toán!

Điều thật sự cần chứng minh là \(H(X)\) giảm rồi tăng. Chỉ cần chứng minh đạo hàm bậc hai của nó không âm:

Do đó, \(H(X)\) giảm rồi tăng — hoặc chỉ giảm, hoặc chỉ tăng, cũng không sao — nên có thể tìm kiếm tam phân để tìm chi phí nhỏ nhất cho \(D\) ngày. Độ phức tạp là \(O(N\log N+\log^2(M)\log N)\).

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