Phân tích

Test Set 1 — cách trực tiếp

\(1234567\) là một năm gầm vang và lớn hơn mọi đầu vào khả dĩ. Vì vậy, nếu lần lượt kiểm tra từng năm sau \(Y\), mỗi bộ dữ liệu cần kiểm tra không quá \(1234567\) năm; thực tế ít hơn nhiều nhưng khó chứng minh cận chặt hơn.

Để kiểm tra năm \(y\), thử từng tiền tố \(p\) của \(y\), rồi xem việc “hoàn thiện” bằng cách nối \(p+1,p+2,\ldots\) có tạo đúng \(y\) không. Tiền tố hợp lệ dài nhiều nhất một nửa \(y\), nên số trường hợp nhỏ.

Nếu vẫn chưa tin vào thời gian, có thể tiền tính một lần tính gầm vang cho mọi số tới \(1234567\) và ghi nhớ. Mỗi bộ dữ liệu chỉ cần tìm giá trị true kế tiếp trong một bảng khá nhỏ; thời gian gần như độc lập với đầu vào và có thể được kiểm chứng bằng chạy thử mà không mạo hiểm một lượt nộp thật.

Test Set 1 — độ phức tạp rõ ràng hơn

Độ dài số đầu tiên của phép nối nhiều nhất \(3\) chữ số. Thử cả \(999\) khả năng, nối các số liên tiếp cho tới khi vượt ngưỡng \(1234567\). Mỗi dãy nối có nhiều nhất \(6\) số. Cách này dựng tập mọi năm gầm vang liên quan trong thời gian rất nhỏ.

Sau đó tìm tuyến tính trong danh sách dưới \(6000\) phần tử để lấy năm nhỏ nhất lớn hơn \(Y\). Có thể dùng tìm kiếm nhị phân để nhanh hơn, nhưng không cần.

Test Set 2

Hai cách trên đều không dùng được. Khoảng cách giữa hai năm gầm vang liên tiếp có thể rất lớn; chẳng hạn, có thể chứng minh như một bài tập rằng không có năm nào khác giữa \(100000000100000001\) và \(100000001100000002\). Việc kiểm tra riêng một năm cũng tốn hơn trước. Với cách liệt kê, có tới \(10^9-1\) ứng viên cho số đầu, và một số ứng viên tạo dãy nối dài hơn nhiều, khiến toàn bộ tập không thể chứa trong bộ nhớ, chưa nói tới thời gian tính.

Cách chia trường hợp

Tập mọi năm gầm vang là phép nối của ít nhất \(3\) số vẫn đủ nhỏ: trong trường hợp này số bắt đầu lớn nhất chỉ có \(6\) chữ số. Ta áp dụng cách liệt kê của Test Set 1 với thay đổi đó.

Còn các năm là phép nối đúng hai số liên tiếp. Hàm \(f(x)\) bằng phép nối \(x\) và \(x+1\) là hàm tăng, nên dùng phương pháp chia đôi để tìm hiệu quả phần tử nhỏ nhất trong tập con này lớn hơn \(Y\). Lấy nhỏ nhất giữa ứng viên của hai trường hợp.

Cách tổng quát

Tổng quát hóa cách thứ hai bằng họ hàm \(f_n(x)\) là phép nối \(x,x+1,\ldots,x+n-1\). Mọi \(f_n\) đều tăng. Vì vậy, với mỗi số lượng số liên tiếp \(n\), dùng chia đôi để tìm ứng viên tốt nhất, rồi lấy nhỏ nhất trong các ứng viên. Do \(n\le\log Y\), độ phức tạp là \(O(\log^2Y)\) và dùng được ngay cả với cận rất lớn.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1C, bài Roaring Years.