Phân tích

Test Set 1

\(N\) đủ nhỏ cho thuật toán mũ. Duyệt mọi hoán vị vẫn quá chậm, nhưng nhiều trường hợp lặp: một bánh đã bị che có thể bị che theo nhiều cách mà không ảnh hưởng phần tiếp theo. Loại việc tính lặp dẫn đến quy hoạch động.

Thay vì nhớ chính xác chồng, với mỗi bánh lưu một trong ba trạng thái: chưa dùng, nhìn thấy, bị che. Bánh nhìn thấy luôn xếp theo bán kính giảm dần; vị trí bánh bị che không ảnh hưởng quá trình. Định nghĩa \(f(s)\) là số cách hoàn tất từ trạng thái \(s\).

Nếu không còn bánh chưa dùng, \(f(s)=1\). Nếu còn, thử từng bánh chưa dùng làm bánh kế tiếp; gọi \(s_i\) là trạng thái sau khi nấu bán kính \(i\), thì \(f(s)=\sum_i f(s_i)\). Có \(3^N\) trạng thái; chi phí ngoài đệ quy là đa thức bậc thấp theo \(N\), dễ cài \(O(N)\), tổng \(O(3^NN)\).

Cũng có thể quay lui, dựng hoán vị từng phần tử và kiểm tra các \(V_i\) của tiền tố. Có thể chứng minh độ phức tạp bị chặn bởi \(O(2^NN^3)\), tốt hơn đáng kể \(O(N!)\) và đủ cho nhóm này.

Test Set 2

Duy trì danh sách bánh nhìn thấy; khi bánh bị che, coi nó bị “xóa” khỏi danh sách. Gọi \(P_i\) là bán kính bánh thứ \(i\), ta xây các bất đẳng thức giữa kích thước.

Mỗi lần thêm, số bánh thấy được chỉ tăng \(1\), giữ nguyên hoặc giảm. Nếu tăng hơn \(1\), đáp án \(0\).

• Nếu \(V_i=V_{i-1}+1\), bánh mới nhỏ hơn mọi bánh thấy được; thêm \(P_x>P_i\), với \(x\) là bánh cuối danh sách trước đó.
• Nếu \(V_i\le V_{i-1}\), bánh mới lớn hơn \(V_{i-1}-V_i+1\) bánh cuối và các bánh đó bị xóa. Thêm \(P_i>P_x\), với \(x\) là bánh cuối bị xóa. Nếu \(V_i>1\), bánh mới nhỏ hơn phần còn lại; thêm \(P_y>P_i\), với \(y\) là bánh đầu không bị xóa.

Trong trường hợp sau, bất đẳng thức cũ \(P_y>P_x\) trở nên dư thừa vì đã có \(P_y>P_i>P_x\); xóa cạnh cũ để tránh dư thừa gây vấn đề.

Sau khi xóa cạnh dư, mỗi bánh nằm bên phải nhiều nhất một bất đẳng thức \(A>B\). Mô hình hóa thành cây có cạnh \(A\to B\) khi \(A>B\). Đếm thứ tự hợp lệ đệ quy từ gốc là bánh lớn nhất — bánh ở đầu danh sách nhìn thấy cuối cùng.

Gọi \(s(i)\) là kích thước cây con gốc \(i\), \(f(i)\) là số cách gán các kích thước \(1..s(i)\) hợp lệ trong cây con. Với mỗi con \(j\), cây con tự hoán vị theo \(f(j)\) cách; \(f(i)\) là tích các \(f(j)\) nhân số cách phân phối kích thước cho các cây con. Vì \(i\) lớn nhất trong cây con nên nhận kích thước lớn nhất; \(s(i)-1\) kích thước còn lại được phân phối bằng hệ số đa thức.

Tiền tính giai thừa và nghịch đảo giai thừa để chia modulo. Xây cây và tính đáp án đều \(O(N)\).

Lời giải khác

Hai nhận xét: (1) bánh lớn nhất bán kính \(N\) chỉ có thể ở vị trí \(k\) lớn nhất thỏa \(V_k=1\); (2) nó che mọi bánh trước nên thứ tự phần trước không ảnh hưởng các \(V_i\) sau. Tách thành hai bài độc lập trái/phải.

Ở phần phải, bánh lớn nhất luôn thấy được, nên ngầm trừ \(1\) khỏi mọi \(V_i\) (không thật sự cập nhật vì quá chậm). Chọn bánh nào nằm trái/phải theo \({N-1\choose k-1}\) cách. Cơ sở: đoạn rỗng có một thứ tự; nếu không có \(V_i=1\), có không thứ tự. Đáp án là tích đáp án trái, phải và hệ số nhị thức.

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