CONVSTR - Editorial

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. :slight_smile:

15 Likes

nice editorial sir. I couldn’t wait till morning to see where I went wrong!

4 Likes

I have tried the similiar approch but Got WA.
Can’t figure out where it went wrong.

Here is the link to the code.

https://www.codechef.com/viewsolution/33503749

Can someone please figure out where I went wrong. I couldn’t figure it out.
Sample test passed and checked other cases as well.
Link to code:
https://www.codechef.com/viewsolution/33505910

Got WA, the example cases and the test cases works fine.

Here is the link to my code.

https://www.codechef.com/viewsolution/33501569

My WA code which should’ve worked only for subtask 1.
Please tell me what I’ve done wrong.

i have similar approach to do this problem but only first subtask is passing,please tell me where i am wrong ,here is my code link:
https://www.codechef.com/viewsolution/33506612

1 Like

What is wrong in my approach-

https://www.codechef.com/viewsolution/33490977
I am getting TLE, can some suggest some remedies

https://www.codechef.com/viewsolution/33497509
here is my code it may help

1 Like

Can someone please figure out where i went wrong.
https://www.codechef.com/viewsolution/33499945

will check it now, thanks!

BRO,can u please little comment yout code…

Your code fails on
abcde , aabaa
Check your output

1 Like

Video Editorial of Convert String.
(Tester Approach)
:slightly_smiling_face::slightly_smiling_face:
3 Likes

https://www.codechef.com/viewsolution/33508813
Why only partially accepted?

On this case -
abcde
aabbe
smallest number of operations needed is 2
your code outputs 3

2 Likes

i think this case will give wrong answer.
4
aabc
aaab
check it out.

2 Likes

https://www.codechef.com/viewsolution/33482147
Can someone help me to figure out why I am getting WA in 1st subtask while getting AC in 2nd?

Thanks man, got it.