PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kryptonix171
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
simple
PREREQUISITES:
Dynamic Programming
PROBLEM:
You’re given strings S and P. P contains every character from a
to z
exactly once.
In one move, you can replace S_i with P_{27 - \text{ord}_P(S_i)}. Find the minimum number of moves needed to convert S into a sorted string.
EXPLANATION:
The main observation here is that performing the operation twice on the same index will just give us back the original character.
This is because:
- Let c be the character initially at index i.
Operating once will set S_i to P_x, where x = {27 - \text{ord}_P(c)}. - Operating again will set it to P_y, where y = 27 - \text{ord}_P(S_i).
However, after the first move S_i equals P_x - and \text{ord}_P(P_x) = x.
So, y = 27 - x = 27 - (27 - \text{ord}_P(c)) = \text{ord}_P(c).
So, S_i will get set to c, which is what it originally was.
Knowing that at most one operation will be applied to each index allows us to compute the answer using dynamic programming.
Let T_i denote the character that would be at index i if one operation is applied to it.
Let dp_{i, j} denote the minimum number of moves needed to turn the first i elements into a sorted sequence, where j = 0 means no operation was used on index i, and j = 1 means an operation was used.
We have dp{1, 0} = 0 and dp_{1, 1} = 1. Then, for i \gt 1:
- dp_{i, 0} is either dp_{i-1, 0} (if S_i \geq S_{i-1}) or dp_{i-1, 1} (if S_i \geq T_{i-1}).
If neither options are valid, let’s say dp_{i, 0} = \infty, and if both are valid take the minimum. - dp_{i, 1} can be computed similarly as either dp_{i-1, 0} + 1 or dp_{i-1, 1} + 1 by comparing T_i against S_{i-1} and T_{i-1}.
The final answer is \min(dp_{N, 0}, dp_{N, 1}).
If this minimum is \infty it’s impossible to make S sorted, so print -1 instead.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
void main_() {
int t;
cin>>t;
while(t>0)
{
int n;
cin>>n;
string s,p;
cin>>s>>p;
map<char,char>mp;
for(int i=0;i<26;i++)
{
mp[p[i]]=p[abs(25-i)];
//cout<<p[i]<<p[abs(25-i)]<<"\n";
}
int dp1[n];
int dp2[n];
int mx=2*n;
for(int i=0;i<n;i++)
{
dp1[i]=mx;
dp2[i]=mx;
}
dp1[0]=0;
dp2[0]=1;
for(int i=1;i<n;i++)
{
if(dp1[i-1]!=-1)
{
if(s[i-1]<=s[i])
{
dp1[i]=dp1[i-1];
}
if(s[i-1]<=mp[s[i]])
{
dp2[i]=dp1[i-1]+1;
}
}
if(dp2[i-1]!=-1)
{
if(mp[s[i-1]]<=s[i])
{
dp1[i]=min(dp1[i],dp2[i-1]);
}
if(mp[s[i-1]]<=mp[s[i]])
{
dp2[i]=min(dp2[i],dp2[i-1]+1);
}
}
}
int ans=min(dp1[n-1],dp2[n-1]);
if(ans==2*n)
cout<<"-1\n";
else
cout<<ans<<"\n";
t--;
}
}
static void run_with_stack_size(void (*func)(void), size_t stsize) {
char *stack, *send;
stack = (char *)malloc(stsize);
send = stack + stsize - 16;
send = (char *)((uintptr_t)send / 16 * 16);
asm volatile(
"mov %%rsp, (%0)\n"
"mov %0, %%rsp\n"
:
: "r"(send));
func();
asm volatile("mov (%0), %%rsp\n" : : "r"(send));
free(stack);
}
int main() {
run_with_stack_size(main_, 1024 * 1024 * 1024); // run with a 1 GiB stack
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s, t;
cin>>s>>t;
int ord[26];
for(int i = 0; i < 26; i++){
ord[t[i] - 'a'] = i;
}
int dp[n][2];
dp[0][0] = 0;
dp[0][1] = 1;
for(int i = 1; i < n; i++){
dp[i][0] = n + 1;
dp[i][1] = n + 1;
if(s[i] >= s[i - 1]){
dp[i][0] = dp[i - 1][0];
}
if(s[i] >= t[26 - ord[s[i - 1] - 'a'] - 1]){
dp[i][0] = min(dp[i][0], dp[i - 1][1]);
}
if(t[26 - ord[s[i] - 'a'] - 1] >= s[i - 1]){
dp[i][1] = dp[i - 1][0] + 1;
}
if(t[26 - ord[s[i] - 'a'] - 1] >= t[26 - ord[s[i - 1] - 'a'] - 1]){
dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1);
}
}
int ans = min(dp[n - 1][0], dp[n - 1][1]);
if(ans > n){
ans = -1;
}
cout<<ans<<"\n";
}
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input().strip()
p = input().strip()
mapper = {}
for i in range(26): mapper[p[i]] = p[-i-1]
x, y = 0, 1
for i in range(1, n):
nx, ny = n+1, n+1
if s[i] >= s[i-1]: nx = min(nx, x)
if s[i] >= mapper[s[i-1]]: nx = min(nx, y)
if mapper[s[i]] >= s[i-1]: ny = min(ny, x + 1)
if mapper[s[i]] >= mapper[s[i-1]]: ny = min(ny, y + 1)
x, y = nx, ny
if min(x, y) > n: print(-1)
else: print(min(x, y))