Cách tính độ chênh vênh của một hoán vị bất kỳ

Ta nhận thấy với mỗi dãy núi bất kỳ, phần tử nhỏ nhất luôn nằm ở đầu hoặc cuối dãy. Sau đó, ta có thể xóa đi phần tử đó mà dãy còn lại vẫn là một dãy núi.

Dựa trên đó, để tính độ chênh vênh của một dãy, ta có thể làm như sau:

• Xét từng phần tử theo thứ tự từ nhỏ đến lớn,
• Với mỗi phần tử, thử đưa nó về đầu hoặc cuối dãy,
• Trong hai cách đó, chọn cách nào có số bước hoán đổi nhỏ hơn,
• Sau đó xóa phần tử đó đi và tiếp tục thực hiện tương tự với dãy còn lại.

Dễ thấy đây là cách có số bước ít nhất để biến đổi một dãy bất kì thành dãy núi.

Trường hợp ~a~ là hoán vị của ~1, 2, 3, \ldots, n~

Ta mô hình hoá bài toán bằng cách gọi

• ~pos_i~ là vị trí của phẩn tử có giá trị ~i~ trên dãy ~a~,
• ~left_i~ là số lượng chỉ số ~j~ thoả mãn ~1 \le j \le pos_i~ và ~a_j > i~
• ~right_i~ là số lượng chỉ số ~j~ thoả mãn ~pos_i \le j \le n~ và ~a_j > i~

Khi đó độ chênh vênh của một dãy chính xác bằng ~\sum_1^n \min(left_i, right_i)~

Do đang xét hoán vị nên ta có thêm các tính chất sau với mọi ~i~:

• ~left_i + right_i = n - i~
• ~0 \le left_i \le n - i~

Hơn nữa, dãy ~left~ mô tả chính xác cách xây dựng một hoán vị duy nhất trong số ~n!~ hoán vị, bằng cách duy trì một hoán vị từ ~i + 1~ đến ~n~ và lần lượt chèn các phần tử theo thứ tự từ lớn đến nhỏ, ~left_i~ cũng chính là vị trí mà ~i~ cần chèn vào hoán vị đang có.

Như vậy nếu ta xét trên tất cả hoán vị, phân phối giá trị của ~left_i~ là phân phối đều . Nói cách khác, nếu gọi ~countLeft_{i,j}~ là số hoán vị có ~left_i = j~ thì ~countLeft_{i,0} = countLeft_{i,1} = countLeft_{i,2} = \dots = countLeft_{i,n - i} \big(= \frac{n!}{n - i + 1}\big)~

Từ đó ta có thể dễ dàng tính nhanh được kết quả trong trường hợp ~l = (1, 2, \dots, n)~ và ~r = (n, n - 1, \dots, 1)~

Để giải cho trường hợp tổng quát, ta đưa về bài toán gần giống quy hoạch động thứ tự từ điển. Ta cần tìm được cách tính tổng nhanh cho một nhóm các hoán vị có chung một tiền tố, nhưng hậu tố bất kì.

Trường hợp này thực ra không khác trường hợp ở trên quá nhiều:

• Với các số ~x~ đã xuất hiện trong phần tiền tố chung, ~left_x~ đã được xác định
• Với các số ~x~ không xuất hiện trong phần tiền tố chung, ~left_x~ vẫn giữ phân phối đều trong một khoảng xác định, đó là ~[c, n - x]~ trong đó ~c~ là số lượng số lớn hơn ~x~ đã xuất hiện trong phần tiền tố chung

Có thể thấy kết quả của phần tiền tố là cố định, và phần hậu tố là trường hợp tính trên tất cả hoán vị có sửa đổi.

Trường hợp tổng quát

Xét trường hợp tổng quát, lúc này mỗi giá trị sẽ có nhiều giá trị ~left~ khác nhau, mỗi giá trị ứng với một lần xuất hiện trong dãy. Giả sử giá trị ~x~ có ~k~ phần tử, gọi ~left_{x, i}~ là số lượng số lớn hơn bên trái phần tử có giá trị ~x~ thứ ~i~ từ trái sang phải. Dễ thấy ~0 \le left_{x, 1} \le left_{x, 2} \le \dots \le left_{x, k} \le n - c~ ~(1 \le i < k)~ với ~c~ là số lượng số lớn hơn ~x~.

Nếu xét trên tất cả hoán vị và trên tất cả các phần tử có giá trị ~x~, ta vẫn nhận được một phân phối đều trên đoạn ~[0, n-c]~ và số lần xuất hiện của một giá trị đúng bằng ~\binom {n-c+k}{k - 1}/k \times numPerm~.

Trong đó ~numPerm~ là số lượng hoán vị khác nhau được tính bằng công thức ~\frac{(cnt_1 + cnt_2 + \dots + cnt_n)!}{cnt_1! * cnt_2! * \dots * cnt_n!}~

Việc tính toán cho một nhóm các hoán vị có chung một tiền tố cũng có thể được thực hiện tương tự như trường hợp dãy là hoán vị của các số từ ~1~ đến ~n~.

Lưu ý cài đặt Ta có tổng cộng ~O(n^2)~ dạng hoán vị cần tính kết quả, nếu tính toán kết quả từng nhóm trong ~O(n)~ như cách đã ở trên thì độ phức tạp tổng là ~O(n^3)~. Để giảm xuống ~O(n^2)~, ta cần tối ưu quá trình tính toán, tính lần lượt các dạng theo thứ tự nhất định để tận dụng lại kết quả. Phần này xin nhường lại cho bạn đọc.

lm j c0 code ahjhj