STOT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: archit
Editorialist: raysh07

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given a binary string S, convert it to T using at most 3 \cdot N operations. In one operation, you can choose i (1 \le i < N) such that S_{i} = 1 and flip S_{i + 1}. Find the operation sequence if possible.

EXPLANATION:

Let us first observe when it is possible to convert S to T.

Suppose S_i = 1. Then, we can make S_{i + 1} = 1 as well (if it is 0, just do one operation at i). Proceeding similarly, we can actually make all S_j = 1 for all j > i to get S_1 S_2 ... S_{i - 1}1 1 .. 1

How is this useful? Well, we can then iterate from j = N to i + 1, and if S_j \ne T_j, we can simply do one operation on the index j - 1. This will flip S_j, and it is guaranteed S_{j - 1} = 1 because we iterated in reverse.

Thus, we can make the entire suffix S[i + 1, N] match T[i + 1, N] just because S_i = 1.

But notice, the above only works for the suffix of characters after the first 1 position in S. That is, let p denote the first 1 position in S; then we can arbitrarily change the characters S_{p + 1}, S_{p + 2}, ..., S_N but not S_1 S_2 .... S_{p}, hence S_i = T_i should be satisfied for all 1 \le i \le p without doing any operations.

We can check the condition with simple loop, and then convert S_{p + 1} ... S_N all to 1, and then loop in reverse equating it to T. Check the solution for more details. The solution uses at most 2 \cdot N operations.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist'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 p = n;
        for (int i = 0; i < n; i++){
            if (s[i] == '1'){
                p = i;
                break;
            }
        }
        
        bool good = true;
        for (int i = 0; i <= p; i++){
            if (s[i] != t[i]){
                cout << -1 << "\n";
                good = false;
                break;
            }
        }
        
        if (!good) continue;
        
        vector <int> ans;
        for (int i = p + 1; i < n; i++){
            if (s[i] == '0'){
                ans.push_back(i);
                s[i] = '1';
            }
        }
        
        for (int i = n - 1; i > p; i--){
            if (s[i] != t[i]){
                ans.push_back(i);
            }
        }
        
        cout << ans.size() << "\n";
        for (auto x : ans){
            cout << x << " ";
        }
        cout << "\n";
    }
    return 0;
}
2

for this sample input

1
12
100001000000
100000000000

your output is :

21
1 2 3 4 6 7 8 9 10 11 11 10 9 8 7 6 5 4 3 2 1

and my output is :

9
1 2 3 4 5 4 3 2 1

I am still confuse why my code is wrong:
can you please review (AI is not getting my point)

#include <bits/stdc++.h>

using namespace std;

void solve(int n, string s, string t) {
    int lastOne = -1;
    int ans = 0;
    vector<int> list;
    
    for(int i = 0; i < n; i++){
     
        if(s[i] != t[i]){
            if(lastOne == -1){
                cout << -1 << endl;
                return;
            }else if(t[i] == '1') {
                ans += (2 * (i - lastOne)) - 1;
                for(int l = lastOne + 1; l <= i; l++){
                    list.push_back(l);
                }
                for(int l = i - 1; l >= lastOne + 1; l--){
                    list.push_back(l);
                }
                s[i] = '1';
                lastOne = i;
            }
            
        }
        if(s[i] == '1'){
            lastOne = i;
        }
    }
    
    lastOne = -1;
    for(int i = 0; i < n; i++){
        if(s[i] != t[i]){
            if(lastOne == -1){
                cout << -1 << endl;
                return;
            }
            
        
            ans += (2 * (i - lastOne)) - 1;
            for(int l = lastOne + 1; l <= i; l++){
                list.push_back(l);
            }
            for(int l = i - 1; l >= lastOne + 1; l--){
                list.push_back(l);
            }
            
        }
        if(s[i] == '1'){
            lastOne = i;
        }
    }
    
    
    if(0 <= ans && ans <= (3 * n)){
        cout << ans << endl;
    }else{
        cout << -1 << endl;
        return;
    }
    if(list.size() == 0){
        return;
    }
    for(int i = 0; i < list.size() - 1; i++){
        cout << list[i] << " ";
    }
    cout << list[list.size() - 1] <<  endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s, t;
        cin >> s;
        cin >> t;
        solve(n, s, t);
    }
}
3

include <bits/stdc++.h>
using namespace std;

int main() {
int tt;
cin>>tt;
while(tt–){
int n,count=0,k=0;
cin>>n;
string s,t;
cin>>s>>t;
vectorvec;
for(int i=n-1; i>=0; i–){
if(s[i]==‘0’&&t[i]==‘1’){
if(i-1>=0){
if(s[i-1]==‘1’){
s[i]=‘1’;
count++;
vec.emplace_back(i);
}
}
}
else if(s[i]==‘1’&&t[i]==‘0’){
if(i-1>=0){
if(s[i-1]==‘1’){
s[i]=‘0’;
count++;
vec.emplace_back(i);
}
}
}
}
bool str=true;
for(int i=0; i<s.size(); i++){
if(s[i]!=t[i]){
str=false;
break;
}
}
if(str){
cout<<count<<“\n”;
for(int i=0; i<vec.size(); i++){
cout<<vec[i]<<" “;
}
cout<<”\n";
}
else{
cout<<-1<<“\n”;
}
}

}

here is my code logically my code give the answer but it show wrog testcases when submit it… can someone tell me why it is being wrong

4

Can anyone help to identify bug, logically it is correct but it shows wrong ans

    while (T-- > 0) {
        int N = sc.nextInt();
        sc.nextLine();
        String S = sc.nextLine();
        String G = sc.nextLine();

        if (S.equals(G)) {
            System.out.println(0);
            continue;
        }

        StringBuilder s = new StringBuilder(S);
        List<Integer> ops = new ArrayList<>();

        // Find the first '1'
        int firstOne = -1;
        for (int i = 0; i < N; i++) {
            if (S.charAt(i) == '1') {
                firstOne = i;
                break;
            }
        }

        if (firstOne == -1) {
            System.out.println(-1);
            continue; // impossible, no '1' to perform operation
        }

        // Simulate flipping everything after firstOne to 1
        for (int i = firstOne + 1; i < N; i++) {
            if (s.charAt(i) == '0') {
                s.setCharAt(i, '1');
                ops.add(i); // 0-based index; this means flip by previous i
            }
        }

        // Now align s with G
        for (int i = 1; i < N; i++) {
            if (s.charAt(i) != G.charAt(i)) {
                if (s.charAt(i - 1) == '1') {
                    s.setCharAt(i, G.charAt(i)); // flip it
                    ops.add(i); // 0-based index
                } else {
                    ops.clear();
                    ops.add(-1);
                    break;
                }
            }
        }

        if (ops.size() == 1 && ops.get(0) == -1) {
            System.out.println(-1);
        } else {
            System.out.println(ops.size());
            for (int op : ops) {
                System.out.print(op + " ");
            }
            System.out.println();
        }
    }