Các quan sát ban đầu

Trước hết có vài quan sát hữu ích. Thứ nhất, đoạn dài \(1\) hoặc \(2\) không cần thêm bánh để có tính chất kim tự tháp, nên có thể bỏ qua điều kiện độ dài \(\ge3\) trong đề. Thứ hai, với mọi đoạn, “đỉnh” trong đáp án tối ưu là chồng lớn nhất của đoạn ban đầu (phần suy luận này dành cho bạn). Nếu có nhiều chồng lớn nhất, ta chọn chồng ngoài cùng bên trái làm đỉnh.

\(O(S^3)\) — Quá chậm

Với mỗi trong số \(\binom{S+1}{2}\) đoạn, xác định vị trí đỉnh sau khi biến đoạn thành kim tự tháp. Khi biết đỉnh, ta có hai bài toán nhỏ hơn: cần dãy không giảm bên trái đỉnh và dãy không tăng bên phải đỉnh. Để tính số bánh cần cho đoạn không giảm, quét từ trái và thêm bánh cho tới khi không còn chồng nào nằm bên trái chồng thứ \(i\) trong đoạn cao hơn hẳn chồng thứ \(i\). Duy trì cực đại hiện tại khi quét cho phép tính số bánh cần cho mỗi đoạn bằng \(O(S)\) phép toán. Có \(O(S^2)\) đoạn nên tổng cộng cần \(O(S^3)\) phép toán.

\(O(S^2)\) — Test Set 1

Các ý tưởng trên là nền tảng cho lời giải nhanh hơn. Thay vì tính lại độc lập số bánh cần để biến một đoạn thành dãy không giảm (hoặc không tăng), ta dùng kết quả từ đoạn khác. Giả sử biết chỉ số chồng lớn nhất trong \([L,R]\), gọi là \(M[L,R]\), và số bánh ít nhất để biến \([L,R]\) thành dãy không giảm, gọi là \(X[L,R]\). Ta tính được cả \(M[L,R+1]\) và \(X[L,R+1]\) trong \(O(1)\) vì chiều cao tại \(M[L,R+1]\) là \(\max(P_{M[L,R]},P_{R+1})\) và

Tương tự, lưu \(Y[L,R]\) là số bánh ít nhất để biến \([L,R]\) thành dãy không tăng.

Với mọi \([L,R]\), số bánh ít nhất để biến đoạn thành kim tự tháp là

Tiền xử lý tốn \(O(S^2)\) thời gian và bộ nhớ; bước sau dùng \(O(1)\) cho mỗi đoạn. Tổng độ phức tạp là \(O(S^2)\).

\(O(S\log S)\) — Test Set 2

Chiến lược trên quá chậm và tốn quá nhiều bộ nhớ với giới hạn lớn. Ta vẫn dùng ý tưởng tính số bánh cần để biến một đoạn thành dãy không giảm hoặc không tăng. Nhưng thay vì tính \(X,Y\), ta tính giá trị tích lũy:

và

Thay vì tập trung vào hai đầu mút, chiến lược sẽ dựa trên đỉnh của các đoạn.

Ban đầu chưa biết \(X'\) hay \(Y'\) cho đoạn nào. Ta giả sử chỉ biết chúng cho các đoạn cực đại. Nếu hai đoạn kề nhau, ta gộp chúng (không bao giờ có các đoạn giao nhau). Ví dụ, nếu biết \(X'[L,k]\) và \(X'[k+1,R]\), ta gộp thành \(X'[L,R]\) rồi quên hai giá trị cũ. Quy trình gộp đầy đủ ở dưới. Do đó mỗi chồng thuộc nhiều nhất một đoạn đã biết của \(X'\) và một đoạn đã biết của \(Y'\).

Ta xử lý các đỉnh từ nhỏ nhất đến lớn nhất. Khi xử lý chồng \(i\), chỉ quan tâm các đoạn có \(i\) làm đỉnh. Nếu \(X'[L,i-1]\) đã được tính, \(L\) phải là chỉ số xa nhất bên trái sao cho \(P_L,P_{L+1},\ldots,P_{i-1}\) đều nhỏ hơn \(P_i\) (do thứ tự xử lý). Tương tự, nếu \(Y'[i+1,R]\) đã được tính, \(R\) phải là chỉ số xa nhất bên phải sao cho \(P_{i+1},P_{i+2},\ldots,P_R\) đều ít nhất bằng \(P_i\). Nếu \(L,R\) như vậy tồn tại, tổng số bánh cần trên mọi đoạn có \(i\) làm đỉnh là

Nếu không biết \(X'[L,i-1]\) với bất kỳ \(L\) nào thì \(P_{i-1}\ge P_i\), nên \(i\) không thể là đỉnh của đoạn chứa cả \(i-1,i\). Đáp án cho chúng được tính sau khi xét \(i-1\) làm đỉnh (tương tự với \(i+1\) nếu không biết \(Y'[i+1,R]\)). Khi đó có thể dùng \(X'=0\) (hoặc \(Y'=0\)). Vì các đoạn là cực đại và ta xử lý từ nhỏ đến lớn, \(P_{L-1}\ge P_i\) (tương tự \(P_{R+1}>P_i\)).

Ta muốn gộp \(X'[L,i-1]\), \(X'[i+1,R]\) và chồng \(i\) thành \(X'[L,R]\) qua hai bước. Trước hết, \(X'[L,i]=X'[L,i-1]\): do xử lý từ nhỏ đến lớn, \(P_i\) có thể được tự do thêm làm đầu phải của mọi dãy không giảm trong phạm vi này. Tiếp theo gộp \(X'[L,i]\) với \(X'[i+1,R]\). \(X'[L,R]\) lấy tổng trên các đoạn kết thúc tại chồng \(R\). Đoạn bắt đầu trong \([i+1,R]\) đã được tính trong \(X'[i+1,R]\). Nếu bắt đầu trong \([L,i]\), ta khởi đầu bằng một dãy trong \([L,i]\); nhưng vì \(P_i\) là đỉnh, mọi giá trị bên phải phải bằng đúng \(P_i\). Số bánh để nâng mọi giá trị trong \([i+1,R]\) lên \(P_i\) tính được trong \(O(1)\) bằng tổng tích lũy. Phép gộp đầy đủ là

Các giá trị \(Y'\) được tính tương tự. Ban đầu cần sắp xếp các chồng trong \(O(S\log S)\); các bước còn lại tốn hằng số cho mỗi đỉnh, tức \(O(S)\). Thuật toán chạy trong \(O(S\log S)\).

\(O(S)\)

Dù lời giải \(O(S\log S)\) đủ nhanh cho test set 2, lời giải \(O(S)\) cũng khả thi! Sau đây là phác thảo có thể đọc độc lập với lời giải trên.

Để đơn giản, giả sử mọi chồng có chiều cao khác nhau. Khi so sánh hai chồng cùng chiều cao, phá hòa bằng cách coi chồng có chỉ số lớn hơn là cao hơn.

Hãy suy nghĩ từ kết quả cuối. Với mỗi chồng, ta muốn tính chi phí kim tự tháp hóa cho mọi đoạn mà nó cao nhất; khi đó nó là đỉnh. Cộng các giá trị ấy cho mọi chồng sẽ cho kết quả chung.

Để tính các chi phí đó, với mỗi chồng \(s\), ta tính:

• Chồng cao hơn gần nhất bên trái \(s\) (có thể là chồng “lính canh” cao vô hạn thêm ở đầu dãy), gọi là vật chặn trái. \(D_L\) là khoảng cách tuyệt đối (tính theo số chồng) từ \(s\) tới nó.
• Chồng cao hơn gần nhất bên phải \(s\) (hoặc chồng lính canh thêm sau dãy), gọi là vật chặn phải. \(D_R\) là khoảng cách tuyệt đối từ \(s\) tới nó.
• Chi phí kim tự tháp hóa cho mọi đoạn kết thúc tại \(s\) và có \(s\) cao nhất, gọi là chi phí bên trái \(C_L\).
• Chi phí kim tự tháp hóa cho mọi đoạn bắt đầu tại \(s\) và có \(s\) cao nhất, gọi là chi phí bên phải \(C_R\).

Chi phí ứng với \(s\) là

Làm sao tính \(C_L,D_L\) cho mỗi chồng? (Lời giải cho \(C_R,D_R\) đối xứng; khác biệt chính là do phá hòa, bất đẳng thức so sánh nghiêm ngặt ở một phía và không nghiêm ngặt ở phía kia.)

Duyệt từ trái sang phải, duy trì cấu trúc ngăn xếp \(X\) ghi nhớ dãy giảm dài nhất kết thúc ở chồng hiện tại. Khi gặp \(s\), lấy khỏi \(X\) mọi chồng thấp hơn \(s\), cộng đóng góp của chúng vào chi phí bên trái hiện tại. Ban đầu đặt \(t'=s\); về sau, \(t'\) là chồng vừa được lấy ra trước đó. Đóng góp của chồng thấp hơn \(t\) bị lấy ra là số bánh còn thiếu giữa \(t,t'\) (tính trong thời gian hằng số nếu tiền xử lý tổng tích lũy kích thước các chồng), nhân khoảng cách tới vật chặn trái của \(t'\). Vật chặn trái của \(s\) là chồng đầu tiên không thể lấy khỏi \(X\) vì nó cao hơn \(s\). Xử lý xong \(s\), đưa \(s\) vào \(X\) rồi tiếp tục.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 3 — Pancake Pyramid.