Phân tích bài toán

Bài toán yêu cầu đếm số cách loại bỏ các phần tử khỏi một dãy cho đến khi ta thu được một dãy không tăng. Nhìn bài toán từ phía kết thúc, giả sử chúng ta biết dãy không tăng cuối cùng có độ dài \(K\). Một số phần tử đã bị loại bỏ, và tổng cộng chúng ta đã loại bỏ \(N-K\) phần tử. Có \((N-K)!\) (giai thừa của \(N-K\)) cách để loại bỏ những phần tử đó. Vì vậy, ước lượng ban đầu có vẻ là tổng các giai thừa đó trên tất cả các dãy con không tăng của dãy ban đầu.

Tuy nhiên, điều này không hoàn toàn chính xác. Một số dãy con không tăng thậm chí không thể đạt tới được vì chúng ta dừng lại ngay khi dãy của mình trở thành không tăng. Ví dụ, trong ví dụ thứ hai của đề bài, dãy đã là không tăng ngay từ đầu, vì vậy không có dãy con thực sự nào có thể đạt tới được. Đối với các dãy con có thể đạt tới được, không phải mọi cách để đạt tới chúng đều khả thi. Ví dụ, trong ví dụ đầu tiên, chúng ta có thể đạt được dãy con '7 <số 6 thứ nhất>' (lưu ý, nó nên được coi là khác với dãy con '7 <số 6 thứ hai>') bằng cách loại bỏ số 6 thứ hai, sau đó là số 4. Tuy nhiên, nó không thể đạt được bằng cách thực hiện các thao tác đó theo thứ tự ngược lại, vì chúng ta sẽ dừng lại ngay sau khi loại bỏ số 4.

Bây giờ thay vì tính tất cả \((N-K)!\) cách để đạt được một dãy con nhất định, chúng ta chỉ cần đếm các cách khả thi. Mẹo chính để giải bài toán này là: hãy đếm các cách không khả thi thay vào đó, rồi thực hiện phép trừ. Các cách không khả thi đơn giản là những cách mà trước lần loại bỏ cuối cùng, dãy con đã là một dãy không tăng có độ dài \(K+1\). Và đối với mỗi dãy con như vậy, có đúng \(K+1\) cách để thực hiện một lần loại bỏ không khả thi và dẫn đến một dãy con độ dài \(K\). Điều đó có nghĩa là tổng số cách không khả thi để đạt được tất cả các dãy con không tăng độ dài \(K\) bằng tổng số dãy con không tăng độ dài \(K+1\) nhân với \((N-K-1)!\) (số cách để đạt được dãy con dài hơn) nhân với \(K+1\).

Tóm lại, giả sử \(A_K\) là số lượng dãy con không tăng có độ dài \(K\). Khi đó đáp án của bài toán này là tổng theo \(K\) của:

Giải quyết bài toán con

Bây giờ chúng ta đã đưa bài toán về một bài toán đơn giản hơn nhiều: tìm \(A_K\). Bài toán này có thể được giải quyết bằng cách tiếp cận quy hoạch động tiêu chuẩn, với một chút biến tấu để chạy nhanh hơn.

Đầu tiên, hãy giả sử rằng tất cả các số đầu vào là khác nhau và nằm trong khoảng từ \(0\) đến \(N-1\). Không khó để biến đổi chúng theo cách này mà không làm thay đổi kết quả. Nếu có các số bằng nhau, chúng ta sẽ giảm nhẹ giá trị của số ở bên phải, sao cho tính chất không tăng của tất cả các dãy con được bảo toàn. Cụ thể, ta có thể thay thế mỗi giá trị \(S_i\) bằng một cặp \((S_i, -i)\) và so sánh các cặp này theo thứ tự từ điển để duy trì quan hệ "lớn hơn hoặc bằng" ban đầu.

Bài toán quy hoạch động của chúng ta bây giờ sẽ là: số lượng dãy con không tăng độ dài \(P\) kết thúc bằng số \(Q\) là bao nhiêu? Gọi số đó là \(B_{P,Q}\). Chúng ta sẽ tìm chúng theo thứ tự các số \(Q\) xuất hiện trong dãy.

Không khó để thấy rằng \(B_{P,Q}\) chỉ là tổng của \(B_{P-1,Q'}\) cho tất cả các số \(Q'\) lớn hơn \(Q\) và xuất hiện trước \(Q\) trong dãy. Vì chúng ta xử lý các trạng thái theo thứ tự các số \(Q\) xuất hiện trong dãy, chúng ta chỉ cần lấy tổng trên tất cả các \(Q'\) đã xuất hiện mà lớn hơn \(Q\).

Đây đã là một giải pháp khả thi cho bài toán, nhưng nó hơi chậm: nó chạy trong \(O(N^3)\), hơi quá nhiều đối với \(N=8000\). Chúng ta có \(O(N^2)\) trạng thái trong quy hoạch động, và chúng ta cần tìm tổng của \(O(N)\) số để xử lý mỗi trạng thái. Tuy nhiên, chúng ta có thể tính tổng đó nhanh hơn! Chúng ta chỉ cần một cấu trúc dữ liệu dạng mảng hỗ trợ thay đổi phần tử và tìm tổng của một hậu tố (trên tất cả các \(Q'\) lớn hơn \(Q\)), và cây Fenwick là một cấu trúc dữ liệu thực hiện chính xác điều đó, thực hiện mỗi thao tác trong thời gian \(O(\log N)\), cho tổng thời gian chạy là \(O(N^2 \log N)\).

Lưu ý rằng tất cả các phép tính cần được thực hiện modulo 10007.

Độ phức tạp

• Thời gian: \(O(N^2 \log N)\)
• Không gian: \(O(N^2)\) hoặc \(O(N)\) nếu tối ưu bộ nhớ cho DP.

Dựa trên phân tích chính thức của Google Code Jam.