PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: am_aadvik
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given a string S, as well an an integer K.
Consider the string \underbrace{(S + S + \ldots + S)}_{K \text{ times}}, where + denotes string concatenation.
In this large string, you may replace each occurrence of I with any character of your choice.
Find the maximum possible number of adjacent equal characters you can obtain.
EXPLANATION:
Let’s solve for K = 1 first, i.e we have the entire string with us.
It’s not hard to see that a simple greedy approach works: for each occurrence of I, replace it with whichever non-I character appears closest to its right.
For example, if we have IIAIBIA, it’ll turn into AAABBAA by doing this.
Note that if S ends with an I then there will be some occurrences of I that don’t get replaced when we do this; forming a suffix.
For these occurrences alone, we can instead make them equal to the nearest non-I character to the left.
So IIBIACII would become BBBAACCC.
After performing this replacement, simply count the number of adjacent pairs of equal characters.
Proving that this is optimal is fairly easy: for example you can look at contiguous blocks of I’s and see that it’s optimal to replace them all with the same character; and the optimal choice of character is one that borders the block.
Let’s now attempt to extend this to K \gt 1.
The greedy idea still works, of course - the only issue is that we can no longer directly create the entire string since it is humongous.
However, we can easily ‘lift’ the result from K = 1 to the larger string.
That is, let’s first replace the I’s in S greedily, as we did earlier.
Now, consider some pair of adjacent indices (i, i+1) in S.
- Suppose S_i = S_{i+1}.
Then, our greedy replacement ensures that these two characters will remain equal in all copies of S.
So, they contribute a total of K to the answer: one for each copy. - Suppose S_i \ne S_{i+1}.
Then, our greedy replacement ensures that these two characters will remain unequal in all copies of S.
So, they don’t contribute anything to the answer at all.
This gives us a pretty simple start: just compute the answer for K = 1, and multiply it by K.
However, there is one more detail we need to take care of: the first and last characters.
Since the strings are placed end-to-end, the first character and the last character of S will be adjacent to each other (K-1) times.
So, if S_1 = S_N (after replacement), we need to add an extra (K-1) to the answer.
Depending on your implementation, you might have to handle the case where all the characters of S are equal to I separately (for which the answer is of course just NK-1).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, k; cin >> n >> k;
string s; cin >> s;
int p = -1;
for (int i = 0; i < n; i++){
if (s[i] != 'I'){
p = i;
}
}
if (p == -1){
int ans = n * k - 1;
cout << ans << "\n";
return;
}
int ans = 0;
for (int i = p + 1; i < n; i++){
if (s[i] == 'I'){
s[i] = s[i - 1];
}
}
for (int i = p - 1; i >= 0; i--){
if (s[i] == 'I'){
s[i] = s[i + 1];
}
}
for (int i = 0; i + 1 < n; i++){
if (s[i] == s[i + 1]){
ans += k;
}
}
if (s[0] == s[n - 1]){
ans += k - 1;
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}