Test Set 1

Ở Test Set đầu, có thể dùng vét cạn. Với deque bánh còn lại \(\mathbf{D}\), chọn phục vụ khách kế tiếp bằng chiếc ở đầu hoặc cuối deque. Đồng thời, mỗi khi lấy một chiếc ra, cập nhật độ ngon lớn nhất trong các bánh đã phục vụ. Có thể dùng đệ quy vét cạn để mô phỏng toàn bộ quá trình.

Mỗi bước thường có hai lựa chọn — chiếc đầu hoặc chiếc cuối — nên độ phức tạp thời gian tổng thể là \(O(2^\mathbf{N})\), đủ cho Test Set 1.

Có thể cải thiện vét cạn bằng ghi nhớ đáp án tối ưu ứng với deque con hiện tại. Tổng số deque con liên tiếp cần xét là

Do đó độ phức tạp giảm xuống \(O(\mathbf{N}^2)\).

Test Set 2 và Test Set 3

Cách trên không áp dụng được cho các Test Set lớn hơn vì sẽ vượt thời gian. Ta cần một nhận xét tốt hơn: nếu hai chiếc có thể phục vụ ở một thời điểm mang độ ngon \(\mathbf{D}_{\text{left}}\) và \(\mathbf{D}_{\text{right}}\), luôn tốt hơn hoặc không kém khi phục vụ chiếc có độ ngon nhỏ hơn.

Để chứng minh, không mất tính tổng quát giả sử \(\mathbf{D}_{\text{left}}\le\mathbf{D}_{\text{right}}\), và gọi \(\mathbf{D}_{\max}\) là độ ngon lớn nhất trong các bánh đã phục vụ.

Nếu \(\mathbf{D}_{\text{left}}<\mathbf{D}_{\max}\), chiếc bên trái sẽ được phục vụ miễn phí bất kể được lấy ra lúc nào. Vì vậy có thể lấy nó ngay mà không ảnh hưởng đáp án cuối.

Ngược lại, nếu \(\mathbf{D}_{\text{left}}\ge\mathbf{D}_{\max}\) thì do \(\mathbf{D}_{\text{left}}\le\mathbf{D}_{\text{right}}\), phục vụ \(\mathbf{D}_{\text{left}}\) trước luôn tốt hơn. Nếu lấy \(\mathbf{D}_{\text{right}}\) trước, \(\mathbf{D}_{\max}\) sẽ được cập nhật lên ít nhất \(\mathbf{D}_{\text{right}}\), khiến chiếc \(\mathbf{D}_{\text{left}}\) sau đó không được trả tiền nếu nhỏ hơn.

Vì thế tiêu chí phục vụ là: luôn lấy \(\min(\mathbf{D}_{\text{left}},\mathbf{D}_{\text{right}})\) và cập nhật \(\mathbf{D}_{\max}\) khi cần. Mỗi khách chỉ cần \(O(1)\) thời gian, nên tổng độ phức tạp là \(O(\mathbf{N})\).

Google Code Jam khuyến nghị luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Lời giải này được dịch đầy đủ từ bản phân tích chính thức của Google Code Jam 2022, Vòng 1B.