PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kryptonix171
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given a string S. You can do the following operations on it:
- Choose a subsequence that equals \text{"back"}, delete it, and insert a new character c at the front of S.
c, when converted to an integer between 1 and 26, should have at most two factors. - Choose a subsequence that equals \text{"front"}, delete it, and insert a new character c at the back of S.
c, when converted to an integer between 1 and 26, should have more than two factors.
Find the minimum possible length of S after performing several of these operations.
EXPLANATION:
First, observe that the characters b,a,c,k correspond to the integers 2, 1, 3, 11, all of which have \leq 2 factors.
On the other hand, the characters f,r,o,n,t correspond to 6, 18, 15, 14, 20, all of which have \gt 2 factors.
So, performing an operation of the one type doesn’t allow us to affect subsequences of other type at all — "back" and "front" don’t share characters, and deleting one subsequence doesn’t allow us to insert any character from the other one.
Essentially, we have two independent operations here: one working with the characters of "back", and the other with "front".
Let’s look at just the occurrences of "front".
Since the aim is to reduce the length, clearly we want to perform as many operations as possible - each operation reduces the length of the string by 4.
Let’s look at only the occurrences of characters f,r,o,n,t in S, and ignore everything else.
First, let’s forget about appending new characters to S, and think only about finding as many disjoint subsequences that equal "front" as possible.
Since all the characters are distinct, this can be done greedily, from left to right:
- Each time you encounter
f, start a new subsequence. - Each time you encounter
r, remove one occurrence off(if it exists) and replace it with an occurrence offr. - Each time you encounter
o, remove one occurrence offr(if it exists) and replace it with an occurrence offro. - Each time you encounter
n, remove one occurrence offro(if it exists) and replace it with an occurrence offron. - Each time you encounter
t, remove one occurrence offron(if it exists) and replace it with an occurrence offront, which is final.
Now, for the extra characters.
These can be any of f,r,o,n,t, so we can use them to finish as many existing prefixes of "front" as possible.
To maximize the number of times we’re able to make the final string, we go in descending order of length: try to complete fron if it exists, then fro, then fr, then f, and finally the empty string.
Note that each completion increases the number of extra characters by 1, which you shouldn’t forget to update.
Basically the exact same algorithm allows you to find the maximum number of times the "back" operation can be performed too - though you’ll need to work in reverse this time.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#define int long long int
#define debug cout<<"K"
#define mod 1000000007
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
map<string,int>subs;
int ans=n;
int backmoves=0;
int frontmoves=0;
//back
for(int i=n-1;i>=0;i--)
{
if(s[i]=='k')
{
subs["k"]++;
}
if(s[i]=='c')
{
if(subs["k"])
{
subs["ck"]++;
subs["k"]--;
}
}
if(s[i]=='a')
{
if(subs["ck"])
{
subs["ack"]++;
subs["ck"]--;
}
}
if(s[i]=='b')
{
if(subs["ack"])
{
subs["back"]++;
subs["ack"]--;
}
}
}
if(subs["back"])
{
ans-=subs["back"]*4;
backmoves+=subs["back"];
ans-=subs["ack"]*3;
ans-=min(backmoves-1,subs["ck"])*2;
backmoves-=min(backmoves-1,subs["ck"]);
ans-=min((backmoves-1)/2,subs["k"]);
backmoves-=min((backmoves-1)/2,subs["k"])*2;
if(backmoves%3==0)
backmoves=3;
else
backmoves=backmoves%3;
}
//front
for(int i=0;i<n;i++)
{
if(s[i]=='f')
{
subs["f"]++;
}
if(s[i]=='r')
{
if(subs["f"])
{
subs["fr"]++;
subs["f"]--;
}
}
if(s[i]=='o')
{
if(subs["fr"])
{
subs["fro"]++;
subs["fr"]--;
}
}
if(s[i]=='n')
{
if(subs["fro"])
{
subs["fron"]++;
subs["fro"]--;
}
}
if(s[i]=='t')
{
if(subs["fron"])
{
subs["front"]++;
subs["fron"]--;
}
}
}
if(subs["front"])
{
ans-=subs["front"]*5;
frontmoves+=subs["front"];
ans-=subs["fron"]*4;
ans-=min(frontmoves-1,subs["fro"])*3;
frontmoves-=min(frontmoves-1,subs["fro"]);
ans-=min((frontmoves-1)/2,subs["fr"])*2;
frontmoves-=min((frontmoves-1)/2,subs["fr"])*2;
ans-=min((frontmoves-1)/3,subs["f"]);
frontmoves-=min((frontmoves-1)/3,subs["f"])*3;
if(frontmoves%4==0)
frontmoves=4;
else
frontmoves=frontmoves%4;
}
ans+=backmoves+frontmoves;
cout<<ans<<"\n";
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int cal(string &s, string t){
int cnt = 0;
int n = s.size();
int m = t.size();
int a[m] = {};
for(int i = 0; i < n; i++){
if(s[i] == t[0]){
a[0]++;
}
for(int j = 1; j < m; j++){
if(s[i] == t[j] && a[j - 1] > a[j]){
a[j]++;
}
}
}
cnt = (m - 1) * a[m - 1];
for(int i = 0; i < m - 1; i++){
a[i] -= a[i + 1];
}
for(int i = m - 1; i > 0; i--){
while(1){
int mn = min(a[m - 1] / (m - i), a[i - 1]);
if(mn == 0){
break;
}
a[m - 1] -= (m - i - 1) * mn;
a[i - 1] -= mn;
cnt += (m - 1) * mn;
}
}
while(1){
int mn = a[m - 1] / m;
if(mn == 0){
break;
}
a[m - 1] -= (m - 1) * mn;
cnt += (m - 1) * mn;
}
return cnt;
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
int front = cal(s, "front");
//cout<<front<<"\n";
reverse(s.begin(), s.end());
int back = cal(s, "kcab");
//cout<<back<<"\n";
cout<<n - back - front<<"\n";
}
}
Editorialist's code (Python)
def solve(s, pattern):
n, m = len(s), len(pattern)
ct = [0]*(m+1)
ct[0] = 10**9
for i in range(n):
for j in range(m):
if s[i] == pattern[j]:
if ct[j] > 0:
ct[j] -= 1
ct[j+1] += 1
i = 0
while i < ct[m]:
for j in reversed(range(m)):
if ct[j] > 0:
ct[j] -= 1
ct[j+1] += 1
break
i += 1
return (m-1)*ct[m]
for _ in range(int(input())):
n = int(input())
s = input()
print(n - solve(s, 'front') - solve(s[::-1], 'kcab'))
