Gọi \(N\) là số ngày. Vì không được bỏ trống ngày nào, sinh viên phải yêu cầu ít nhất \(N/2\) bộ bài. Không có lý do yêu cầu nhiều hơn, vì các bộ dư không thể được nộp hết.

Trước hết ta trình bày quy hoạch động đủ cho Small, rồi công thức toán học giải Large.

Quy hoạch động

Vì chỉ được nộp bộ yêu cầu gần nhất, các bộ đang giữ tạo thành một ngăn xếp: yêu cầu là push, nộp là pop.

Ở ngày 1, rõ ràng phải yêu cầu một bộ và chọn một ngày để nộp nó. Giữa hai ngày ấy, ta có thể push và pop, nhưng ngay trước khi nộp bộ ngày 1, ngăn xếp phải chỉ còn bộ đó. Do đó số ngày nằm giữa ngày yêu cầu và ngày nộp phải chẵn.

Khoảng giữa yêu cầu và nộp là một bài toán con, và khoảng sau ngày nộp là bài toán con khác. Mỗi bài toán con phải để lại ngăn xếp đúng như lúc bắt đầu, nên cùng một quy tắc áp dụng đệ quy.

Định nghĩa bài toán con \((i,j)\) là điểm tối đa trên các ngày từ \(i\) đến \(j\), không được động vào phần ngăn xếp có từ trước ngày \(i\) và phải trả ngăn xếp về trạng thái ban đầu. Ta yêu cầu một bộ ở ngày \(i\), rồi chọn ngày nộp trong \([i,j]\) sao cho số ngày ở giữa là chẵn. Mỗi lựa chọn chia đoạn thành hai bài toán con có thể rỗng.

Với đoạn dài 6, các cách đặt ngày yêu cầu R và ngày nộp S là:

_ _ _ _ _ _
↓
R S _ _ _ _
R _ _ S _ _
R _ _ _ _ S

Ta nên luôn yêu cầu loại trùng tâm trạng ngày yêu cầu: nếu yêu cầu loại không trùng, điểm tốt nhất chỉ là 5, trong khi yêu cầu loại trùng luôn cho ít nhất 5. Khi đó cặp ngày đem lại 10 điểm nếu tâm trạng ngày yêu cầu và ngày nộp giống nhau, ngược lại là 5.

Đoạn rỗng là cơ sở. Với đoạn lớn hơn, thử mọi ngày nộp hợp lệ, cộng điểm cặp và điểm tối ưu của hai đoạn con. Bảng nhớ có \(O(N^2)\) ô, mỗi ô thử \(O(N)\) lựa chọn, nên độ phức tạp là \(O(N^3)\), đủ cho Small.

Công thức

Đếm số ngày chẵn/lẻ có tâm trạng Coding và Jamming, gọi lần lượt là \(CE,CO,JE,JO\). Điểm tối đa là

Trước hết chứng minh đây là cận trên. Mỗi cặp yêu cầu–nộp phải dùng một ngày chẵn và một ngày lẻ, vì số ngày nằm giữa phải chẵn. Muốn tạo cặp Coding–Coding cần một ngày Coding chẵn và một ngày Coding lẻ, nên có tối đa \(\min(CE,CO)\) cặp. Tương tự có tối đa \(\min(JE,JO)\) cặp Jamming–Jamming. Các ngày còn lại chỉ tạo được \(|CE-CO|\) cặp khác loại; cũng có thể chứng minh \(|JE-JO|\) bằng đúng giá trị này. Bất kể ghép phần dư thế nào, không thể có thêm cặp trùng loại.

Để chứng minh cận đạt được, lập danh sách các ngày theo thứ tự. Mỗi khi thấy hai ngày kề nhau có cùng tâm trạng, đánh dấu ngày đầu là yêu cầu, ngày sau là nộp, rồi xóa cả hai khỏi danh sách. Những cặp mới trở thành kề nhau sau khi xóa vẫn hợp lệ trong lịch thật: một cặp mới không thể nằm một nửa trong và một nửa ngoài cặp đã xóa, vì ta chỉ xóa khi không còn gì bên trong nó. Tiếp tục tới khi không còn hai ngày kề cùng tâm trạng. Khi ấy các tâm trạng phải xen kẽ, nên mọi ngày chẵn còn lại cùng một loại và mọi ngày lẻ còn lại là loại kia; ghép hết chúng thành các cặp khác loại. Cách dựng đạt đúng cận trên.

Thuật toán tham lam

Cũng có thể giải Large bằng ngăn xếp khi quét trái sang phải. Mỗi ngày:

1. Nếu không giữ bộ chưa nộp nào, hãy yêu cầu.
2. Nếu đã yêu cầu đủ \(N/2\) bộ, hãy nộp.
3. Nếu bộ trên đỉnh ngăn xếp trùng tâm trạng hiện tại, hãy nộp.
4. Nếu không, hãy yêu cầu.

Khó thấy ngay tính đúng, nhưng có thể chứng minh thuật toán tuân theo công thức trên. Cả thuật toán ngăn xếp và cách xóa cặp kề đều tìm được một số cặp cùng tâm trạng, gọi là “trúng”; cặp khác tâm trạng là “trượt”. Cần chứng minh ngăn xếp có số lần trúng tối ưu.

Trong hầu hết trường hợp, hai cách trúng và trượt ở cùng vị trí. Trực giác là bước 3–4 tương ứng với việc tìm và xóa cặp kề cùng tâm trạng, còn bước 1–2 dọn phần chưa ghép còn lại.

Có các trường hợp biên mà hai cách ghép không giống hẳn. Với CJCJJC, thuật toán ngăn xếp tạo RRRSSS, trong khi cách cặp kề tạo RRSRSS.

Mọi trường hợp như vậy xảy ra khi ngăn xếp để trượt một cặp, không nhận ra ở cùng độ sâu còn có cặp trúng về sau. Không mất tính tổng quát, dạng của chúng là; có thể đổi vai J và C:

... J ... C ... J ... J ...

Thuật toán ngăn xếp yêu cầu ở hai vị trí đầu và nộp ở hai vị trí cuối; cách cặp kề ghép cặp thứ hai trước rồi cặp thứ nhất. Dù ghép theo cách nào, kết quả vẫn có đúng một cặp trượt và một cặp trúng. Vì vậy cả hai đạt điểm tối ưu, dù lịch cụ thể khác nhau.

Công thức chạy \(O(N)\) thời gian, \(O(1)\) bộ nhớ; thuật toán ngăn xếp chạy \(O(N)\) thời gian và \(O(N)\) bộ nhớ.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 3.