PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Vivek Chauhan
Tester: Radoslav Dimitrov
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
Greedy (slightly).
PROBLEM
Given two strings A and B of length N, determine if we can convert string A to string B using following operation minimum number of times.
Each operation is defined as
- Choose a non-empty subset of positions S.
- Find minc = min(A_x) for all x \in S
- Replace A_x = minc for all x \in S
QUICK EXPLANATION
- In each operation, minc \leq A_x for all x \in S, so if we have A_x < B_x for any position x, there’s no possible way to convert string A to string B
- Also, if there’s some character present in B not present in A, we cannot convert string A to string B.
- In all other cases, it is possible to convert. Let’s consider all positions where A_x \neq B_x and among these, consider all B_x. The minimum number of operations needed is the number of distinct characters among these.
- Consider all characters in this set in reverse order, and apply the operation on all positions having B_x same as the current character, and add one position where A_x is the same as current character.
EXPLANATION
Let’s figure out the impossible cases.
Firstly, we can see that each operation replaces A_x by some characters c where c \leq A_x. So, if for any position, we have A_x < B_x, we can never achieve that and thus, the answer becomes impossible.
Example
aaa aab
Secondly, the operation replaces A_x by c where c is present in string A. Hence, if there’s any character in B not present in A, then the answer is impossible.
Example
aac aab
We can prove that the answer is possible in every other case.
Another observation we need is that in each operation, all positions are updated to same character. So, if we consider all positions where B_x < A_x, the number of distinct characters among such B_x is the minimum number of operations since in each operation, we can group all such positions by B_x and apply operations.
For each operation grouped by ch = B_x, we choose those positions as subset for current operations. Additionally, to ensure min(A_x) = ch, we also need to add some position y in subset such that A_y = ch. Calling it special position for this operation.
Lastly, we need to decide the order of operations.
Example
abc aab
Decide the order of operations.
Correct output
2
2 1 2
2 0 1
We can prove that it is optimal to apply operations in decreasing order of ch as it doesn’t affect candidate positions for special positions for subsequent operations.
TIME COMPLEXITY
The time complexity is O(A+N) where A = 26 is the size of the alphabet.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 200005;
char en = '\n';
ll inf = 2e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
ll res = 1;
x %= mod;
while (n) {
if (n & 1)
res = (res * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}
void update(string &a, vector<ll> op) {
char c = 'z';
for (ll &x : op)
c = min(c, a[x]);
for (ll &x : op)
a[x] = c;
}
vector<vector<ll>> res;
ll solve(string a, string b, ll n) {
vector<int> indices[30];
for (int i = 0; i < n; i++)
indices[b[i] - 'a'].emplace_back(i);
bool visited[n + 5];
memset(visited, false, sizeof(visited));
for (int i = 25; i >= 0; i--) {
if (indices[i].empty())
continue;
vector<ll> curr;
for (ll j = 0; j < n; j++) {
if (!visited[j] && (a[j] - 'a') >= i)
curr.emplace_back(j);
}
bool good = true;
for (int &x : indices[i]) {
visited[x] = true;
if ((a[x] - 'a') != i) {
good = false;
}
}
if (good)
continue;
update(a, curr);
res.emplace_back(curr);
}
if (a != b) {
return -1;
}
return res.size();
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
while (t--) {
ll n;
cin >> n;
string a, b;
cin >> a >> b;
res.clear();
ll val = solve(a, b, n);
if (val == -1) {
cout << -1 << en;
continue;
}
cout << res.size() << en;
for (vector<ll> &x : res) {
cout << x.size() << " ";
for (ll &y : x)
cout << y << " ";
cout << en;
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int n;
string a;
string b;
void read() {
cin >> n;
cin >> a;
cin >> b;
}
void solve() {
vector<vector<int> > ans;
for(int i = 0; i < n; i++) {
if(a[i] < b[i]) {
cout << -1 << endl;
return;
}
}
for(char c = 'z'; c >= 'a'; c--) {
vector<int> pos;
bool ok = 0;
for(int i = 0; i < n; i++) {
if(b[i] == c && a[i] != c) {
pos.pb(i);
}
}
if(!ok && !pos.empty()) {
for(int i = 0; i < n; i++) {
if(a[i] == c) {
ok = 1;
pos.pb(i);
}
}
}
if(!ok && !pos.empty()) {
cout << -1 << endl;
return;
}
if(!pos.empty()) ans.pb(pos);
for(int i: pos) {
a[i] = c;
}
}
cout << SZ(ans) << endl;
for(auto li: ans) {
cout << SZ(li) << " ";
for(int x: li) cout << x << " ";
cout << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class CONVSTR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), T = 26;
String A = n(), B = n();
ArrayList<Integer>[] op = new ArrayList[T];
for(int i = 0; i< T; i++)op[i] = new ArrayList<>();
boolean possible = true;
int[] pos = new int[T];
Arrays.fill(pos, -1);
for(int i = 0; i< N; i++){
pos[A.charAt(i)-'a'] = i;
if(A.charAt(i) != B.charAt(i)){
if(A.charAt(i) < B.charAt(i))possible = false;
else op[B.charAt(i)-'a'].add(i);
}
}
for(int i = 0; i< T; i++)if(!op[i].isEmpty() && pos[i] == -1)possible = false;
if(possible){
int ans = 0;
for(int i = 0; i< T; i++)if(!op[i].isEmpty())ans++;
pn(ans);
for(int i = T-1; i >= 0; i--){
if(op[i].isEmpty())continue;
p(op[i].size()+1);
p(" "+pos[i]);
for(int x:op[i])p(" "+x);pn("");
}
}else pn(-1);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CONVSTR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
