Phân tích: Milkshakes

Nhìn bề ngoài, bài toán này có vẻ yêu cầu giải bài toán kinh điển "Satisfiability" (Bài toán thỏa mãn công thức logic), một ví dụ điển hình của bài toán NP-đầy đủ. Các khách hàng đại diện cho các mệnh đề (clauses), các hương vị sữa lắc đại diện cho các biến, và các hương vị malted/unmalted đại diện cho việc biến đó có bị phủ định hay không.

Tuy nhiên, chúng tôi không chọn một bài toán khó đến vậy! Ràng buộc làm cho bài toán này trở nên dễ dàng hơn là mỗi khách hàng chỉ có thể thích tối đa một hương vị malted (tương đương với việc các mệnh đề chỉ có tối đa một biến bị phủ định - hay còn gọi là Horn clauses).

Bằng cách sử dụng các bước sau, chúng ta có thể nhanh chóng tìm ra liệu có tồn tại giải pháp hay không, và nếu có, giải pháp đó là gì:

1. Bắt đầu với mọi hương vị đều là unmalted và xem xét từng khách hàng một.
2. Nếu có một khách hàng chưa được hài lòng (nghĩa là tất cả các hương vị unmalted họ thích đều đã bị đổi thành malted trong các bước trước) và họ không thích bất kỳ hương vị malted nào, thì không có giải pháp nào khả thi.
3. Nếu có một khách hàng chưa được hài lòng và họ có một hương vị malted yêu thích, thì chúng ta bắt buộc phải làm cho hương vị đó thành malted. Chúng ta thực hiện việc này, sau đó quay lại bước 2 (để kiểm tra lại tất cả các khách hàng dựa trên thay đổi mới này).
4. Nếu không còn khách hàng nào không hài lòng, thì chúng ta đã có một giải pháp hợp lệ và có thể để các hương vị còn lại là unmalted.

Lưu ý rằng bất cứ khi nào chúng ta chuyển một hương vị thành malted, đó là vì chúng ta bị ép buộc phải làm vậy để thỏa mãn một khách hàng nào đó mà không còn lựa chọn nào khác. Do đó, giải pháp thu được chắc chắn sẽ có số lượng hương vị malted ít nhất có thể.

Cách cài đặt và Độ phức tạp

Với các cấu trúc dữ liệu khéo léo, thuật toán trên có thể được cài đặt để chạy trong thời gian tuyến tính so với tổng số lượng sở thích của khách hàng (tổng các giá trị \(T\)).

Trong mỗi bước, khi một hương vị được chuyển từ unmalted sang malted, chúng ta chỉ cần kiểm tra các khách hàng thích hương vị đó ở dạng unmalted để xem họ có còn được thỏa mãn bởi hương vị khác hay không. Nếu một khách hàng không còn hương vị nào khác để hài lòng và họ có một lựa chọn malted, ta tiếp tục quá trình. Vì mỗi hương vị chỉ có thể chuyển từ unmalted sang malted tối đa một lần, thuật toán sẽ kết thúc nhanh chóng.

Thông tin thêm:

• Bài toán Satisfiability
• Mệnh đề Horn (Horn clauses)

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