Quy đổi về lưu lượng cố định

Trong lúc đổ đầy bể, mỗi nguồn nước được bật trong một phần nào đó của tổng thời gian. Điều này tương đương với việc bật nguồn ấy suốt toàn bộ thời gian ở một lưu lượng cố định nằm giữa 0 và \(R_i\). Vì vậy, bài toán trở thành chọn lưu lượng cho từng nguồn sao cho tổng lưu lượng là lớn nhất mà vẫn đạt đúng nhiệt độ yêu cầu. Khi đó thời gian đổ đầy bằng dung tích bể chia cho tổng lưu lượng.

Trước hết, đặt mọi nguồn ở lưu lượng cực đại và tính nhiệt độ của lượng nước thu được. Nếu nhiệt độ này đúng bằng nhiệt độ đích, ta đã có lời giải.

Điều chỉnh nhiệt độ

Nếu hỗn hợp quá nóng, cần hạ nhiệt độ bằng cách giảm lưu lượng của một số nguồn. Để tổng lưu lượng giảm ít nhất có thể, bắt đầu giảm từ nguồn nóng nhất, rồi chuyển dần sang các nguồn mát hơn nếu cần, cho đến khi nhiệt độ trung bình của dòng nước bằng nhiệt độ đích. Nếu làm như vậy mà không bao giờ đạt được nhiệt độ đích thì bài toán vô nghiệm.

Nếu hỗn hợp quá lạnh khi tất cả nguồn đều ở lưu lượng cực đại, xử lý đối xứng: tăng nhiệt độ bằng cách giảm lưu lượng, bắt đầu từ nguồn lạnh nhất.

Có thể sắp xếp các nguồn theo nhiệt độ và theo dõi tổng lưu lượng cùng tổng nhiệt \(\sum r_iC_i\) để tính phần lưu lượng cần giảm ở nguồn cuối cùng. Việc sắp xếp tốn \(O(N\log N)\) thời gian, phần quét tốn \(O(N)\), và dùng \(O(N)\) bộ nhớ.

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