PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: abdelmohaymn
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
You’re given a string S that consists of both uppercase and lowercase letters.
The letters \text{a, b, c, \ldots, z} have values \{x, x+1, \ldots, x+25\} in order, and the letters \{A, B, \ldots, Z\} have values \{y, y+1, \ldots, y+25\}.
Let v_c denote the value of character c.
It is guaranteed that |x-y|\geq 26.
You can perform the following operation:
- Choose two characters c_1 and c_2 such that 0 \leq v_{c_1} - v_{c_2} \leq f_{c_1} and f_{c_1} \gt 0.
Here, f_{c_1} denotes the frequency of c_1 in S. - Then, delete all occurrences of c_1 from the string, and append a single copy of c_2 to it.
Find the lexicographically minimum string you can end up with.
EXPLANATION:
Without loss of generality, let x \lt y (so the lowercase letters are ‘smaller’).
Observe that if S contains at least one lowercase letter, it’s possible to delete all of them and end up with several copies of 'a'.
Similarly, if S contains at least one uppercase letter, it’s possible to delete all of them and end up with several copies of 'A'.
How?
Note that choosing c_1 = c_2 in our operation is always valid, and replaces every occurrence of c_1 with a single occurrence of it.
Then, we can choose c_1 and c_1 - 1 to shift c_1 to its predecessor, since it has frequency 1 now.
By repeatedly performing this operation, we end up with only 'a' and 'A' in S.
This means the answer string only ever needs to contain the characters 'a' and 'A'.
Further, observe that:
- If the answer contains only
'a', it’s optimal for there to be a single occurrence. - The same applies for when the string contains only
'A'. - If the answer contains both
'a'and'A', it’s optimal for there to be as many occurrences of'a'as possible, and exactly one'A'.
Among these three types of strings, the best is \text{a}, followed by \text{aa\ldots aaA}, and finally \text{A}.
Notice that the last two cases are really just the same thing: a non-zero number of 'a's followed by a single 'A'. So, we club them together into a single case.
Case 1: a
For the final string to be \text{a}, we need to ensure that there are no capital letters in S at all.
That means, if there are any capital letters, we need to be able to transform them all to small ones.
Observe that c_1 can be transformed to c_2 only when 0 \leq v_{c_1} - v_{c_2} \leq f_{c_1}.
Since x\lt y, the 0 \leq v_{c_1} - v_{c_2} part is automatically satisfied when c_1 is capital and c_2 is small; so we only need to worry about the other condition.
v_{c_1} - v_{c_2} \leq f_{c_1} can be rewritten as v_{c_1} - f_{c_1} \leq v_{c_2}.
The LHS is a constant once c_1 is chosen, so our best chance of this equation being satisfied is when v_{c_2} is as large as possible.
Since we’re restricted to small letters, our best hope is to choose c_2 = \text{z}, giving v_{c_2} = x+25.
Now, let \alpha denote some capital letter. Let’s see when it can be transformed into \text{z}.
Certainly, we need v_{\alpha} - f_{\alpha} \leq x+25 to hold.
v_{\alpha} is fixed, so the only thing we can affect is f_{\alpha}.
In particular, note that for each distinct character \beta \gt \alpha present in S, we can get exactly one extra occurrence of \alpha by repeatedly bringing it to a previous character.
To that end, let d_{\alpha} denote the number of distinct elements of S that are \gt \alpha.
Then, \alpha can be converted to \text{z} if and only if v_{\alpha} - (f_{\alpha} + d_{\alpha}) \leq x+25.
Let \alpha_0 be the smallest \alpha for which this condition is true.
Recall that our objective was to ensure that there are no remaining capital letters in S.
So, if \alpha_0 is \leq the smallest capital letter in S, it’s possible to eliminate all capital letters; otherwise it isn’t.
If it is possible, the answer is \text{a}; otherwise move on to the following case.
Case 2: aa...aaA
We’re here because we weren’t able to eliminate every capital letter, so the answer will definitely end with \text{A}.
Our objective now is to have as many occurrences of 'a' as possible.
First, observe that each occurrence of 'a' that already exists can remain as-is.
Further, each distinct small letter other than ‘a’ can contribute one occurrence.
That only leaves instances of 'a' that arise as a result of converting capital letters to small ones.
Once again, observe that it’s always optimal to convert capital letters to 'z', so our target is fixed to x+25.
All we need to do is find the maximum number of such conversions - each one can “trickle down” to form a new occurrence of 'a'.
Notice that this process can be done as follows.
- Try to convert
'Z'to'z', if possible. If we can, great - otherwise, as long as there exists at least one'Z', it can be turned into one extra occurrence of a smaller character. - Try the same thing with
'Y', except we now (maybe) have one extra occurrence to work with. - Try the same thing with
'X', except we now have between 0 and 2 more occurrences to work with.
\vdots
There are several options, and at first glance it’s not clear which of them is optimal (and if a greedy choice will even work).
However, one way to overcome such situations is to just try all options, with the help of dynamic programming!
Let dp_{\alpha, x} denote the maximum number of conversions to 'z' if we’ve processed all characters \geq \alpha, and there are x ‘extras’ remaining.
This can be computed as follows:
- If \alpha is converted to
'z', we need to ensure v_{\alpha} - (x+25) \leq f_{\alpha}.- If this inequality is true, great: any extras remain, so we get dp_{\alpha + 1, x} + 1.
- Otherwise, we need to use some of the extras to increase the frequency of \alpha. Clearly, it’s best to use as few as possible.
So, if y = v_{\alpha} - (x+25) - f_{\alpha}, we transition from dp_{\alpha+1, x+y} + 1.
- If \alpha is not converted to
'z', any extras remain as they are; and we might even get one more depending on whether an occurrence of \alpha is present or not.
So, dp_{\alpha, x} transitions from dp_{\alpha+1, x} or dp_{\alpha+1, x-1}.
The maximum number of extra 'a' we can get is, of course, the maximum of dp_{\text{A}, x} across all x.
The dp only needs 26\times 26 states and \mathcal{O}(1) transitions from each, so it’s plenty fast.
TIME COMPLEXITY:
\mathcal{O}(N + 26^2) per testcase.
CODE:
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long
const int inf = 1e18;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, x, y;
cin >> n >> x >> y;
string s;
cin >> s;
bool sp = 0;
if (x > y) {
sp = 1;
swap(x, y);
for (auto &c : s) {
int x = (int)c - 'a';
if (x >= 0 && x < 26) c = 'A' + x;
else c = 'a' + x + 32;
}
}
int cA = 0;
bool got[26] = {0};
int cn[26] = {0};
int tot = 0;
for (auto c : s) {
int x = (int)c - 'A';
if (x >= 0 && x < 26) cn[x]++;
}
for (int i = 0; i < 26; i++) {
if (cn[i]) tot++;
}
bool ps = 0, ps2 = 0;
for (int i = 0; i < 26; i++) {
int cA = cn[i];
int req = y - x - 25 + i;
if (cn[i]) tot--;
cA += tot;
if (cA >= req) ps = 1;
if (cn[i]) {
tot++;
break;
}
}
string ans;
if (ps) {
ans.push_back('a');
}
else if (tot) {
string ex;
int yet = 0;
int dp[27];
for (int i = 0; i < 27; i++) {
dp[i] = -inf;
}
dp[0] = 0;
for (int i = 25; i >= 0; i--) {
int req = y - x - 25 + i;
int dif = max(0ll, req - cn[i]);
for (int j = 25; j >= 0; j--) {
int yet = dp[j];
if (yet >= dif) {
dp[j + 1] = max(dp[j + 1], dp[j] - dif);
}
if (cn[i]) dp[j]++;
}
}
int mx = 0;
for (int i = 1; i < 27; i++) {
if (dp[i] >= 0) mx = i;
}
for (int i = 0; i < mx; i++) ex.push_back('a');
ex.push_back('A');
fill(cn, cn + 26, 0);
for (auto c : s) {
int x = (int)c - 'a';
if (x < 26 && x >= 0) cn[x]++;
}
for (int i = 0; i < cn[0]; i++) ans.push_back('a');
for (int i = 1; i < 26; i++) if (cn[i]) ans.push_back('a');
ans += ex;
}
else ans = "a";
if (sp) {
for (auto &c : ans) {
int z = (int)c - 'a';
if (z >= 0 && z < 26) c = 'A' + z;
else c = 'a' + z + 32;
}
}
cout << ans << "\n";
}
}
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, x, y; cin >> n >> x >> y;
string s; cin >> s;
vector<int> f1(26), f2(26);
for (auto c : s) {
if (c >= 'a') ++f1[c-'a'];
else ++f2[c-'A'];
}
string prefer = "aA";
if (x > y) {
swap(x, y);
prefer = "Aa";
swap(f1, f2);
}
vector dp(30, vector(30, -1));
// dp[i][j] -> maximum number of shifts to small from characters i..., j 'extra' chars 'after' the shift
dp[26][0] = 0;
for (int i = 25; i >= 0; --i) {
int req = max(y+i - (x+25) - f2[i], 0);
// cerr << i << ' ' << req << '\n';
for (int j = 25; j >= 0; --j) {
if (dp[i+1][j] == -1) continue;
// y+i - x+25 <= f2[i] + extra
// Send to lower
// for (int k = j-req; k >= 0; --k) dp[i][k] = max(dp[i][k], dp[i+1][j] + 1);
if (j >= req) {
dp[i][j-req] = max(dp[i][j-req], dp[i+1][j] + 1);
if (i == 0) dp[i][0] = max(dp[i][0], dp[i+1][j] + 1);
}
// Don't send
if (f2[i] > 0) dp[i][j+1] = max(dp[i][j+1], dp[i+1][j]);
else dp[i][j] = max(dp[i][j], dp[i+1][j]);
}
}
if (dp[0][0] != -1) cout << prefer[0];
else {
int ct = 0;
for (int i = 1; i < 26; ++i) {
if (dp[0][i] != -1) ct = max(ct, dp[0][i]);
}
ct += f1[0];
for (int i = 1; i < 26; ++i) ct += f1[i] > 0;
cout << string(ct, prefer[0]) + string(1, prefer[1]);
}
cout << '\n';
}
}