The problem can be found here

My Thought Process

Okay, this seems like a pretty straightforward problem. We have $2n$ operations which is quite a lot. Since we’re only changing the prefix, we can make $a[n]$ into the correct bit and then ignore it and then try to make $a[n-1]$ into the correct bit and so on.

To make $a[n]$ into $b[n]$, if it is already the same, we can just look at $a[n-1]$. If not, we can check if the first letter is the opposite of $b[n]$, if it is, just select the $n$th prefix. If not, just select the the $1$st prefix before selecting the $n$th prefix.

This then is atmost $2n$ operations because each letter in $b$ takes atmost 2 operations to be corrected from $a$.

The idea seems pretty easy but implementing it seems a bit annoying.

Lets look at the case

\[01011\] \[11100\]

We should first select the prefix $0$ to change it into

\[11011\]

Then we select $11011$ to get

\[00100\]

Actually. Even though $a[n-1]$, we can correct it again using our algorithm. We really only need to keep track of the first letter in each array and the one at the end we need to correct. Let’s actually just look at indicies and just apply the algorithm. (only reversing change order)

\[1,2,3,4,5\] \[5,4,3,2,1\] \[2,3,4,5,1\] \[4,3,2,5,1\] \[3,4,2,5,1\]

The first letter then repeats in $1,n,2,n-1,\dots$.

Implementation

I think the implementation is pretty simple. We only need to keep track of the first letter or the index so we throw that in an array.

Then, we loop through $i$ and compare our first letter with the one we need to correct to see if its the opposite.

Some things to note:

  1. We need to substract 0 because they are chars.
  2. Keep track of a variable $c$ because everytime we are reversing the entire thing, everything is getting xor once.
  3. The code is in 0-index
#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

void solve() { 
    int n;
    cin >> n;

    string a;
    string b;
    cin >> a >> b;


    vector<int> f;

    int x = 0;
    int y = n - 1;

    for(int i = 0; i < n; ++i){
        if(i % 2 == 0){
            f.pb(x++);
        }
        else{
            f.pb(y--);
        }
    }

    vector<int> ans;

    int c = 0;
    for(int i = 0; i < n; ++i){
        x = f[i];
        if((a[x] - '0') ^ c == ((b[n-1-i]) - '0') ^ 1){
            ans.pb(n-i); 
        }
        else{
            ans.pb(1);
            ans.pb(n-i); 
        };

        c ^= 1;
    }

    cout << ans.size() << ' ';
    for(int i : ans){
        cout << i << ' ';
    }

    cout << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

See here for the solution and another implementation.