Test Set nhỏ

Một cách vét cạn là xét mọi tập con xúc xắc theo mọi thứ tự rồi tìm dãy dài nhất, nhưng Small có thể có 100 con nên cần chiến lược tốt hơn.

Trước hết lấy tập mọi số xuất hiện trên ít nhất một xúc xắc và sắp tăng. Tạo một khoảng ban đầu chỉ chứa số đầu tiên. Sau đó mở rộng và thu hẹp khoảng theo quy tắc dưới đây, luôn duy trì bất biến rằng toàn khoảng là một dãy gồm một hoặc nhiều số liên tiếp.

Kiểm tra xem dãy hiện tại có thể được tạo từ các xúc xắc hay không:

• Nếu có thể, mở rộng để gồm giá trị tiếp theo bên phải.
• Nếu giá trị mới không lớn hơn giá trị ngoài cùng bên phải cũ đúng 1, khoảng không còn liên tiếp; hãy bỏ mọi giá trị trừ giá trị mới này để khôi phục bất biến.
• Nếu không thể, thu hẹp bằng cách bỏ giá trị ngoài cùng bên trái.

Để kiểm tra một dãy, lập ghép cặp hai phía từ các số cần có sang các xúc xắc chứa chúng, sử dụng một thuật toán luồng như Ford–Fulkerson. Mỗi xúc xắc có đúng 6 mặt nên đồ thị có \(6N\) cạnh. Một lần chạy Ford–Fulkerson tốn \(O(N^2)\); ta chạy tối đa \(O(N)\) lần khi thay đổi khoảng, nên tổng là \(O(N^3)\). Các lời giải đa thức khác cũng có thể dùng được.

Test Set lớn

Để thuật toán luồng đủ nhanh, không cần khởi động lại từ đầu sau mỗi thay đổi. Khi mở rộng bằng một số mới, thêm hoặc kích hoạt toàn bộ \(O(N)\) cạnh tới số đó, rồi chỉ cần tìm và thêm một đường tăng luồng vào luồng hiện có. Vì toàn đồ thị có nhiều nhất \(6N\) cạnh, thao tác này cũng tốn \(O(N)\), nên cả lần mở rộng là \(O(N)\).

Khi thu hẹp, xóa các cạnh và phần luồng trên đường gắn với số bị bỏ trong \(O(N)\). Có \(O(N)\) lần mở rộng và thu hẹp, nên tổng thời gian cập nhật là \(O(N^2)\). Cộng với \(O(N^2)\) để giải hoàn toàn bài toán luồng lần đầu, độ phức tạp chung vẫn là \(O(N^2)\), đủ cho Large.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2017, Chung kết thế giới.