Love Charm

Points: 0.10 (partial)

Time limit: 3.0s

Memory limit: 512M

Input: stdin

Output: stdout

Author:

vnoicup

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Having lived nearly twenty years without a lover, Trung decided to go to the temple to seek love. After completing all the rituals, Trung received a love charm. The charm contains a string of length ~n~ consisting of only two letters ~\texttt{O}~ or ~\texttt{K}~. With deep understanding of his own destiny, Trung knows that the effectiveness of the charm depends on the consecutive pairs of letters. Specifically:

The pair ~\texttt{OK}~ has an effect, so if the charm has ~a~ pairs of ~\texttt{OK}~, the effectiveness of the charm will increase by ~a^2~.
The pair ~\texttt{KO}~ has a counter-effect, so if the charm has ~b~ pairs of ~\texttt{KO}~, the effectiveness of the charm will decrease by ~b^2~.

In other words, if the charm has ~a~ pairs of ~\texttt{OK}~ and ~b~ pairs of ~\texttt{KO}~, the effectiveness of the charm will be ~a^2 - b^2~. For example, if the charm contains the string ~\texttt{OOOKOO}~, then ~a = 1~, ~b = 1~, so the effectiveness of the charm will be ~1^2 - 1^2 = 0~.

Trung is not very satisfied with his charm, so he asked the temple for another charm. However, the temple only allows Trung to change the current charm up to ~k~ times, each time Trung can choose any two letters on the charm and swap them. Help Trung obtain a love charm with the maximum possible effectiveness!

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.

The first line contains two positive integers ~n~ and ~k~ (~2 \leq n \leq 10^5~, ~1 \leq k \leq 10~) — the length of the string written on the charm and the maximum number of transformations.

The second line contains a string ~s~ consisting of ~n~ characters ~\texttt{O}~ or ~\texttt{K}~, describing the string written on the charm.

The sum of ~n~ over all test cases is guaranteed not to exceed ~10^5~.

Output

For each test case, output an integer which is the maximum effectiveness the charm can achieve.

Scoring

Subtask	Score	Constraints
1	~250~	Sum of ~n~ does not exceed ~100~, ~k = 1~
2	~750~	~k = 1~
3	~1250~	No additional constraints
Total	~2250~

Sample Input 1

5
2 1
KO
2 1
OK
7 1
OOOKKKK
7 1
KKOOKKK
10 2
KOOKOKKKOO

Sample Output 1

Notes

In the first test case, the optimal swapping sequence is ~\mathtt{KO}~ ~\to \mathtt{OK}~. The resulting charm has an effectiveness of ~1~.

In the second test case, it is optimal to keep the string as ~\mathtt{OK}~, with an effectiveness of ~1~.

In the fifth test case, an optimal swapping sequence is ~\mathtt{KO}~~\mathtt{OKOKKKOO} \to \mathtt{OKOKOK}~~\texttt{K}~~\texttt{KO}~~\texttt{O}~ ~\to \mathtt{OKOKOKOKOK}~, resulting in a charm with an effectiveness of ~9~.

Comments

Please read the guidelines before commenting.

11
y commented on Aug. 13, 2024, 9:47 a.m.
Mình xin đóng góp lời giải cho bài này như sau:

Subtask 1:

Duyệt trâu ~n^2~ cách hoán đổi, với mỗi cách hoán đổi tính chi phí trong ~O(n)~

Subtask 2:

Cho xâu ~s~ độ dài ~n~ được đánh số từ ~1~. Nếu biết số vị trí ~i > 1~ có ~s_i \neq s_{i-1}~ là ~x~ thì ta có thể tính chi phí trong ~O(1)~ như sau:

Nếu ~s_1 = \text{O}~ thì chi phí là ~{\left\lfloor \frac{x}{2} \right\rfloor}^2 - {\left\lfloor \frac{x-1}{2} \right\rfloor}^2~

Nếu ~s_1 = \text{K}~ thì chi phí là ~{\left\lfloor \frac{x-1}{2} \right\rfloor}^2 - {\left\lfloor \frac{x}{2} \right\rfloor}^2~

Một thao tác swap ta có thể đưa về việc: thay đổi kí tự ~s_i~ và ~s_j~ thành đối của nó ~(i<j)~, hay nghĩa là ghép cặp một kí tự ~\text{O}~ với một kí tự ~\text{K}~ sau đó hoặc ngược lại.

Ta sẽ sử dụng quy hoạch động. Gọi ~\text{dp}(i, \text{numOper}, \text{numO}, \text{numK}, \text{last})~ là số vị trí ~j \leq i~ có ~s_j \neq s_{j-1}~ lớn nhất với điều kiện:

Đã sử dụng ~\text{numOper}~ thao tác;

Đã thực hiện ~\text{numO}~ lần đổi từ ~\text{O} \rightarrow \text{K}~, nhưng những vị trí này chưa được ghép cặp với các kí tự ~\text{K}~ nào đằng sau nó;

Đã thực hiện ~\text{numK}~ lần đổi từ ~\text{K} \rightarrow \text{O}~, nhưng những vị trí này chưa được ghép cặp với các kí tự ~\text{O}~ nào đằng sau nó.

Kí tự ~s_{i}~ là ~\text{last}~

Tại vị trí ~i~, giả sử đã tính được ~\text{dp}(i, \text{numOper}, \text{numO}, \text{numK}, \text{last})~ và muốn chuyển sang trạng thái thứ ~i+1~:

Nếu ta giữ nguyên ~s_{i+1}~:

Chuyển sang trạng thái ~(i+1, \text{numOper}, \text{numO}, \text{numK}, s_{i+1})~

Nếu ta chọn thay đổi ~s_{i+1}~:

Nếu ta cho vị trí ~i+1~ trả "nợ" cho các vị trí trước:

Nếu ~s_{i+1}= \text{O}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO}, \text{numK} - 1, \text{K})~

Nếu ~s_{i+1}= \text{K}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO} - 1, \text{numK}, \text{O})~

Nếu ta muốn tiếp tục cho vị trí ~i+1~ vào danh sách "nợ":

Nếu ~s_{i+1}= \text{O}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO} + 1, \text{numK}, \text{K})~

Nếu ~s_{i+1}= \text{K}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO}, \text{numK} + 1, \text{O})~

Lưu ý xử lí các trạng thái không hợp lệ một cách thích hợp.

Vì ~k \geq 1~, nên ta luôn chọn thay đổi kí tự đầu tiên thành ~\text{O}~ để đáp án là dương. Từ đó dễ dàng suy ra base case cho bài toán.

Để lấy đáp án, ta duyệt toàn bộ trạng thái ~(i, j, 0, 0, x)~ với ~0 \leq j \leq k~, ~x \in \{0,1\}~ và đoạn ~[i+1,n]~ chứa toàn kí tự ~x~ để lấy kết quả. Nếu trạng thái hợp lệ, cực đại hoá kết quả với ~{\left\lfloor \frac{\text{dp}(i,j,0,0,x)}{2} \right\rfloor}^2 - {\left\lfloor \frac{\text{dp}(i,j,0,0,x)-1}{2} \right\rfloor}^2~

Độ phức tạp: ~O(nk^3)~

Ngoài ra mình đọc submission còn thấy một số thuật toán tham lam cho subtask này, nhưng mình chưa nghĩ kĩ nên trình bày luôn thuật toán này để phục vụ cho subtask cuối ;)

Subtask 3:

Bằng thuật toán của subtask 2 ta có thể qua luôn được subtask 3 như sau:

Nhận thấy ta chỉ duyệt các bộ ~(\text{numOper}, \text{numO}, \text{numK})~ có ~\text{numO} \leq \text{numOper}~ và ~\text{numO} + \text{numK} \leq \text{numOper}~. Nên ta có thể nén các bộ trạng thái này lại. Thực tế chưa có đến ~300~ trạng thái với ~k \leq 10~. Vậy độ phức tạp tối đa là ~n \times 300 \times 2~ ~= 6 \times 10^7~

Tuy nhiên ta cũng có thể làm tốt hơn:

Nhận thấy việc lưu ~\text{numOper}~ là không cần thiết.

Ta thay đổi ý nghĩa của biến ~\text{numO}~ và ~\text{numK}~ thành số lần đổi ~\text{O} \rightarrow \text{K}~ và số lần đổi ~\text{K} \rightarrow \text{O}~ (bỏ qua khái niệm "nợ" ở subtask 2).

Như vậy ta chỉ cần đảm bảo ~\text{numO}~ và ~\text{numK}~ luôn dương và ~\leq k~ trong mọi vị trí ~i~, và đến thời điểm cuối cùng ~\text{numO}=\text{numK}~ là đủ, do các thao tác có thể đổi chỗ cho nhau.

Công thức chuyển từ đây cũng đơn giản hơn, các bạn có thể tự suy ra từ subtask 2.

Từ đó độ phức tạp giảm xuống ~O(nk^2)~.

Triển khai mẫu các bạn có thể xem ở phần Editorial.