Phân tích

Test Set 1

Đề bài yêu cầu tính một hàm từ số nguyên sang số nguyên. Sau khi chọn một đa giác, phần việc còn lại lại giống bài toán ban đầu: tiếp tục chọn đa giác. Điều này gợi ý mạnh mẽ một lời giải đệ quy.

Một cách là đi từ trên xuống: chọn đa giác lớn nhất trước, rồi chọn phần còn lại. Với mọi đa giác trừ đa giác lớn nhất, có thêm điều kiện phải “nằm vừa” trong đa giác trước: số cạnh mới phải là một ước thực sự của số cạnh trước.

Ta mã hóa bằng hàm nhận số cạnh tổng còn lại \(t\) và kích thước đa giác cuối \(p\):

tức một cộng giá trị lớn nhất trên mọi \(q\) là ước của \(p\), cùng cơ sở \(f(0,p)=0\) và các điều kiện thích hợp để \(q\) thật sự là một đa giác. Đáp án là \(\max_p f(N,p)\).

Với giới hạn Test Set 1, đệ quy đủ nhanh ngay cả khi duyệt mọi \(3\le q\le\min(p-1,t)\). Có thể tìm ước nhanh hơn bằng cách chỉ duyệt tới \(\sqrt p\) rồi xét cả \(q\) và \(p/q\), nhưng tối ưu này không cần cho Test Set 1 và chưa đủ cho Test Set 2.

Test Set 2

Ghi nhớ hóa thường là phản xạ đầu tiên để tăng tốc đệ quy, nhưng miền của hàm trên quá lớn. Cách từ dưới lên phù hợp hơn: bắt đầu bằng đa giác nhỏ nhất. Ta dùng biểu thức tương tự nhưng đổi vai trò tham số và biến duyệt:

Sự hoán đổi này tăng tốc đáng kể: khi xét mọi \(p\), ta chỉ cần nhảy từng bước \(q\), giảm tổng kích thước vòng lặp theo hệ số \(q\). Cài đặt cẩn thận là đủ qua Test Set 2, dù khó chắc chắn về thời gian.

Ta làm tốt hơn bằng nhận xét: sau khi chọn đa giác kích thước \(q\), mọi đa giác về sau đều có kích thước là bội của \(q\). Vì vậy có thể chia toàn bộ bài toán cho \(q\) — đồng thời tạm cho phép “đa giác giả” kích thước \(2\) — bằng cách đặt

Nếu cẩn thận không cho phép kích thước \(2\) ở đa giác đầu tiên, ta chỉ còn phải tính \(g(t)=f(t,1)\), có miền đủ nhỏ để ghi nhớ hóa. Thêm memoization cho ta lời giải nhanh hơn; quan trọng hơn, có thể tiền tính toàn bộ hàm đệ quy và biết chắc thời gian chạy không phụ thuộc vào dữ liệu đầu vào.

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