Test Set 1

Có nhiều cách giải Test Set 1. Một cách đặc biệt thú vị là đem lời giải của một bài Chung kết cũ áp dụng vào đây; ngay cả lời giải Test Set 1 của bài đó cũng hoạt động.

Test Set 2

Test Set 2 có các số rất lớn, nên cần những nhận xét riêng cho bài này.

Nhận xét 1. Nếu có thể tạo một dãy liên tiếp từ \(A\) đến \(B\), thì cũng có thể dùng cùng các xúc xắc theo cùng thứ tự để tạo dãy từ \(1\) đến \(B-A+1\), vì một xúc xắc đang cho số \(X\) luôn có thể được dùng để cho số \(X-A+1\).

Nhận xét 2. Nếu một dãy dùng xúc xắc \(di\) cho số \(X\) và xúc xắc \(dj\) cho số \(X+1\), với \(i>j\), ta có thể tạo cùng dãy đó bằng cách dùng \(dj\) cho \(X\) và \(di\) cho \(X+1\).

Nhận xét 2b. Mọi dãy liên tiếp có thể tạo được cũng có thể được tạo khi dùng các xúc xắc theo thứ tự không giảm của số mặt.

Kết hợp Nhận xét 1 và 2b cho ta thuật toán: sắp xếp các xúc xắc, rồi theo thứ tự đó, thử kéo dài dãy hiện tại bất cứ khi nào có thể. Mã giả:

maximum_straight_length(S):
  sort(S)
  length = 0
  for si in S:
    if si > length: length += 1
  return length

Ngoài bước sắp xếp, thuật toán chỉ cần thời gian tuyến tính, nên tổng độ phức tạp là \(O(N\log N)\). Cận này đủ nhanh cho Test Set 2.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2022, Qualification Round.