Charles defines the goodness score of a string as the number of indices such that
where (-indexed).
For example, the string CABABC
has a goodness score of since
and .
Charles gave Ada a string of length , consisting of uppercase letters and asked her to convert it into a string with a goodness score of . In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to ?
The first line of the input gives the number of test cases, . test cases follow.
The first line of each test case contains two integers and . The second line of each test case contains a string of length , consisting of uppercase letters.
For each test case, output one line containing Case #:
,
where is the test case number (starting from 1) and is the minimum number of
operations required to transform the given string into a string with goodness score equal
to .
Memory limit: 1 GB.
.
.
Time limit: 20 seconds.
.
Time limit: 40 seconds.
for at most test cases.
For the remaining cases, .
In Sample Case #1, the given string already has a goodness score of . Therefore the minimum number of operations required is .
In Sample Case #2, one option is to change the character at index to B
in
order to have a goodness score of . Therefore, the minimum number of operations required
is .
2 5 1 ABCAA 4 2 ABAA
Case #1: 0 Case #2: 1
Analysis
As per the given definition of operation, Ada can only change the goodness score by one in a
single move. Therefore to get a string with the required goodness score in the minimum number of
operations Ada can either increase or decrease the goodness score by one in each step. Let us assume
there are indices( (-indexed)) in the given string such that
. We have 3 cases now.
-
Case 1: ,
In this case, Ada already has the string which has a goodness score of . Therefore
number of operations required is .
-
Case 2: ,
In this case, Ada can change letters at indices ( (-indexed))
that satisfy to the letter at .
Then she will have a string with a goodness score of . Therefore the minimum number of
operations is .
-
Case 3: ,
In this case, Ada can change letters at indices ( (-indexed))
that satisfy to any other uppercase letter other than
the one at . As a result, she will have a string with a goodness score of .
Therefore the minimum number of operations is .
All the above described operations can be done in complexity. Therefore the overall
complexity is .
Sample Code (C++)
int kGoodnessString(string s, int k) {
int minOperations = 0, x = 0;
for(int i = 0; i < s.size() / 2; i++) {
if(s[i] != s[s.size() - i - 1]) {
x++;
}
}
if(x == k) {
minOperations = 0;
}
else if(x > k) {
minOperations = x - k;
}
else {
minOperations = k - x;
}
return minOperations;
}
use rustgym_util::*;
use std::fmt::Write;
use std::io::*;
fn solve(case_no: usize, reader: &mut impl BufRead, writer: &mut impl Write) {
let args: Vec<usize> = reader.parse_vec();
let n = args[0];
let k = args[1] as i32;
let s: Vec<char> = reader.collect_string().chars().collect();
let mut g = 0;
for i in 0..n / 2 {
if s[i] != s[n - 1 - i] {
g += 1;
}
}
let res = (g - k).abs();
writeln!(writer, "Case #{}: {}", case_no, res).unwrap();
}
google_test_gen!(test, "input.txt", "output.txt");