Để lời giải được rõ hơn, mình sẽ kí hiệu một số/phần tử bằng chữ cái in thường, và một mảng các số/phần tử bằng chữ cái in hoa.

Subtask 2: ~n \le 2000~

Đầu tiên, nếu mọi phần tử của ~A~ đều khác nhau thì số điểm tốt nhất sẽ là ~0~, và bất kì cách sắp xếp nào của ~A~ đều đưa ra số điểm này. Ngược lại, số điểm ta đạt được sẽ ít nhất là ~1~.

Ta có nhận xét quan trọng sau: khi đạt điểm tối ưu, ~A~ sẽ có dạng $$A = B \cdot k + B' + T = \underbrace{B + B + \dots + B}_{\text{$k$ lần}} + B' + T$$ với ~k \ge 1~ và ~B'~ là một tiền tố (prefix) của ~B~ (ở đây, ~B'~ và ~T~ có thể là hai mảng rỗng). Điểm của dãy này là bằng ~|B| \cdot (k - 1) + |B'|~. Việc chứng minh rằng đây là cấu trúc tối ưu xin được nhường lại cho bạn đọc. Ta kí hiệu ~B~ là "phần thân", ~B'~ là "phần đầu", và ~T~ là "phần dư".

Ở đây, ta sẽ thực hiện duyệt qua giá trị ~k~ ở trên, và sẽ cố gắng phân các giá trị phân biệt của ~A~ vào các phần thân, đầu, và dư. Với một giá trị ~v~ bất kì, gọi ~cnt_v~ là số lần ~v~ xuất hiện trong ~A~. Gọi ~t = \lfloor \frac{cnt_v}{k + 1} \rfloor~. Ta có hai trường hợp sau:

• Số lần xuất hiện của ~v~ trong ~B'~ bằng số lần xuất hiện của ~v~ trong ~B~. Cách tốt nhất để trường hợp này xảy ra là đưa ~t~ lần giá trị ~v~ vào ~k~ phần thân và ~1~ phần đầu, và ~cnt_v - t \cdot (k + 1)~ lần còn lại vào phần dư. Dễ nhận thấy contribution của vào điểm của ~A~ từ giá trị ~v~ trong trường hợp này là ~t \cdot k~.
• Số lần xuất hiện của ~v~ trong ~B'~ bé hơn số lần xuất hiện của ~v~ trong ~B~. Cách tốt nhất để trường hợp này có thể xảy ra là đưa ~t + 1~ lần giá trị ~v~ vào ~k~ phần thân, và ~cnt_v - (t + 1) \cdot k~ lần vào phần đầu ~B'~. Contribution vào điểm của ~A~ trong trường hợp này là ~cnt_v - (t + 1)~. Tuy nhiên, nếu ~cnt_v - (t + 1) \cdot k < 0~, trường hợp này không tồn tại, nên các bạn phải chú ý khi cài đặt.

Vì thế, với mỗi giá trị phân biệt ~v~, ta chọn trường hợp có contribution to hơn rồi cộng vào đáp án cho ~k~ hiện tại. Cuối cùng, ta chỉ cần chọn giá trị ~k~ mà có điểm to nhất.

Để dựng lại cách sắp xếp, giả sử ~B = B' + B''~. Thế thì với một giá trị ~v~ bất kì,

• Nếu ~v~ được chọn ở trường hợp 1, ta chỉ cần cho ~t~ lần ~v~ vào ~B'~, rồi cho ~cnt_v - t \cdot (k + 1)~ lần còn lại vào phần dư ~T~.
• Nếu ~v~ được chọn ở trường hợp 2, gọi ~p = cnt_v - (t + 1) \cdot k~ là số lần xuất hiện của ~v~ trong ~B'~. Ta cho ~p~ lần ~v~ vào ~B'~, và ~t - p~ lần ~v~ vào ~B''~.

Từ đây bạn đã có thể dựng lại toàn bộ mảng ~A~ sau khi sắp xếp. Do ~k~ có thể đi từ ~1~ tới ~n~ và có ~n~ giá trị phân biệt trong ~A~, độ phức tạp ở đây là ~O(n^2)~.

Subtask 3: Không có giới hạn gì thêm

Khi duyệt ~k~, ta nhận xét rằng nếu ~cnt_v < k~, thì contribution của ~v~ ở cả hai trường hợp đều là ~0~. Vì thế, khi duyệt qua ~k~, ta chỉ cần duyệt qua các giá trị phân biệt ~v~ mà có ~cnt_v \ge k~ để xử lý hai trường hợp.

Ta xem xét độ phức tạp của ý tưởng tối ưu trên. Với một giá trị ~v~ bất kì, giá trị này chỉ được xét khi ~k = 1, 2, \dots, cnt_v~. Nói cách khác, giá trị ~v~ sẽ được xét ở ~cnt_v~ lần duyệt ~k~ khác nhau. Vì thế, độ phức tạp của phép tối ưu trên chính xác bằng ~O(\sum_{v=1}^n cnt_v) = O(n)~, do phép tổng bên trái chính xác bằng số lượng các phần tử của ~A~.

Để cài đặt phép tối ưu trên, các bạn có thể sắp xếp các giá trị ~v~ theo ~cnt_v~ tăng dần rồi dùng kỹ thuật hai con trỏ. Việc sắp xếp có thể được thực hiện bằng std:sort với độ phức tạp ~O(n \log n)~, hoặc counting sort với độ phức tạp ~O(n)~.

A monad is a monoid in the category of endofunctors.