Phân tích

Dựa trên các ràng buộc của công thức, rõ ràng là các công thức tạo thành một cấu trúc cây. Cũng rõ ràng là các nguyên liệu cơ bản có thể được bỏ qua trong quá trình tính toán số bát: Bạn chỉ cần ném chúng vào bất kỳ chiếc bát nào bạn đang làm việc.

Xét một công thức có \(k\) hỗn hợp thành phần \(m_1, m_2, \dots, m_k\). Cần bao nhiêu bát để chuẩn bị công thức này? Việc làm việc trên nhiều hỗn hợp cùng lúc là không hợp lý, vì vậy hãy thử chuẩn bị các hỗn hợp theo một thứ tự nhất định.

Giả sử chúng ta cần \(b_i\) bát để chuẩn bị hỗn hợp thứ \(i\).

• Để chuẩn bị hỗn hợp đầu tiên, chúng ta cần \(b_1\) bát. Sau khi hoàn thành, hỗn hợp này chiếm 1 bát.
• Để chuẩn bị hỗn hợp thứ hai, chúng ta có thể tái sử dụng các bát đã dùng, ngoại trừ 1 bát đang chứa hỗn hợp thứ nhất. Vậy ta cần \(b_2 + 1\) bát. Sau khi hoàn thành, hai hỗn hợp này chiếm 2 bát.
• Tổng quát, khi chuẩn bị hỗn hợp thứ \(i\), chúng ta cần \(b_i\) bát cho chính nó cộng với \((i-1)\) bát đang chứa các hỗn hợp từ \(1\) đến \(i-1\) đã chuẩn bị xong. Vậy ta cần \(b_i + i - 1\) bát.
• Cuối cùng, sau khi đã chuẩn bị xong tất cả \(k\) hỗn hợp, chúng nằm trong \(k\) chiếc bát khác nhau. Ta cần thêm một chiếc bát nữa để trộn tất cả chúng lại (cùng với các nguyên liệu cơ bản). Tổng số bát lúc này là \(k + 1\).

Vậy nếu chuẩn bị theo thứ tự \(1, 2, \dots, k\), số bát tối đa cần dùng là:

Nhìn vào công thức này, ta thấy để tối thiểu hóa giá trị \(b\), chúng ta nên chuẩn bị các hỗn hợp đòi hỏi nhiều bát hơn trước. Nói cách khác, ta nên sắp xếp các \(b_i\) theo thứ tự giảm dần.

Thuật toán

1. Xây dựng cây biểu diễn các hỗn hợp. Các nút lá là các hỗn hợp chỉ gồm nguyên liệu cơ bản.
2. Sử dụng đệ quy (DFS) để tính số bát tối thiểu cho mỗi nút (hỗn hợp):
3. Với mỗi hỗn hợp, gọi đệ quy để tìm số bát cần thiết cho các hỗn hợp thành phần của nó.
4. Lưu các kết quả trả về vào một danh sách.
5. Sắp xếp danh sách này theo thứ tự giảm dần: \(b_1 \ge b_2 \ge \dots \ge b_k\).
6. Số bát cần cho hỗn hợp hiện tại là \(\max(\max_{i=1}^k (b_i + i - 1), k + 1)\). Nếu hỗn hợp không có hỗn hợp thành phần nào (\(k=0\)), số bát mặc định là 1.
7. Kết quả của bài toán là giá trị tính được tại nút gốc (hỗn hợp đầu tiên).

Độ phức tạp

• Xây dựng cây và duyệt DFS: \(O(N \cdot M \log M)\) hoặc \(O(N \cdot M)\) tùy vào cách xử lý chuỗi và sắp xếp, trong đó \(N\) là số hỗn hợp và \(M\) là số thành phần tối đa. Với \(N=1000\) và \(M=10\), thuật toán chạy rất nhanh.

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