STRFLIP, STRFLIP2 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Utkarsh Gupta
Tester: Aryan Choudhary
Editorialist: Lavish Gupta

DIFFICULTY:

Easy-Medium, Medium

PREREQUISITES:

None

PROBLEM:

*This problem is similar to the problem "STRFLIP2". The only difference between them is the number of moves allowed — in this problem, up to N moves can be made.

You are given a binary string A of length N, which we treat as being 1-indexed.

In one move, you are allowed to

  • Pick a contiguous substring (i.e. A[L:R] for some 1 \leq L \leq R \leq N) of A that contains at least one0’ and at least one1
  • Flip all the characters of the chosen substring (i.e. change every 0 to 1 and every 1 to 0)

You are also given a target string B of the same length as A.

Determine if it is possible to convert A to B by applying a sequence of moves as described above.

If it is possible to convert A to B, then find a sequence of no more than N moves that accomplishes this.
It can be shown that whenever it is possible to convert A to B, then it is possible to do so using no more than N moves.

If there are multiple answers, you can print any of them.

QUICK EXPLANATION:

First Observation

Let’s assume A is not equal to B.
We cannot apply any operation on the string A if it contains all 0's or all 1's. Similarly, if B contains all 0's or all 1's, we can never convert A into B.

When is it impossible to convert A to B?

Extending our observation 1 we can definitely say that if either A or B contains all 0's or all 1's and they are not equal then we cannot make them equal. Suppose both A and B contains at least one 0 and at least one 1. Can we always convert A to B? The answer is Yes!
Let’s look at the following approach.

Approach for N operations

Since we have N operations it looks like we can fix one index in each operation. Lets say we have some index x and x+1 such that A[x] \neq A[x+1].
Now using these two indices, we can first fix the indices [1 ... (x-1)], and [(x+2) ... N] (by always including indices x and x+1 in the chosen substring).
Finally, we will try to fix A[x] and A[x+1].

What should be the value of x

Note that at the end, we want to fix A[x] and A[x+1]. As we know, A[x] \neq A[x+1], it would be good if B[x] \neq B[x+1], so that we can easily fix both x and x+1 in at max one single operation.

So, we want to find such x : B[x] \neq B[x+1]. If A[x] = A[x+1] for this x, then we can choose one of A[1...x], A[(x+1)...N], and flip this substring to make A[x] \neq A[x+1]

Approach for N/2+10 operations

Term N/2 suggests that we should fix 2 indices in each operation. Lets try to modify the above approach.
Instead of using x and x+1 indices, let’s try to use N/2 and N/2 + 1 to make the whole string equal.
Now instead of fixing one index we will try to fix one index in left half (i.e. [1 ... N/2 - 1]) and one index in right half (i.e. [N/2 + 2 ... N].
Lets say L is the leftmost index such that A[L] \neq B[L] ( Let L = N/2 if there is no mismatching index in left half).
Similarly R is the rightmost index such that A[R] \neq B[R] (Let R = N/2+1 if there is no mismatching index in right half).
Now flipping [L,R] will fix two indexes (L and R). So after approximately N/2 operations we would have fixed every index apart from N/2 and N/2+1.

Fixing N/2 and N/2+1

Let x be any index such that B[x] \neq B[x+1].
If x=N/2 then flipping \{N/2, N/2+1\} will do our job.
Now let x < N/2, then flipping [x ... (N/2+1)] and [x ... N/2] would make values of A[N/2] = A[N/2+1]. Now we can fix x and x+1 which could be easily fixed.

EXPLANATION:

TIME COMPLEXITY:

SOLUTION:

Tester's Solution - STRFLIP
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>


#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder


#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

struct S {
    // # of 0 / # of 1
    long long zero, one, inversion;
};

// swapping flag
using F = bool;

S op(S l, S r) {
    return S{
        l.zero + r.zero,
        l.one + r.one,
    };
}

S e() { return S{0, 0}; }

S mapping(F l, S r) {
    if (!l) return r;
    // swap
    return S{r.one, r.zero};
}

F composition(F l, F r) { return (l && !r) || (!l && r); }

F id() { return false; }

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
auto isBinaryString=[&](const string s)->bool{
    for(auto x:s){
        if(x!='0'&&x!='1')
            return false;
    }
    return true;
};
T=readIntLn(1,1e5);
lli sumN = 3e5;
while(T--)
{

    const lli n=readIntLn(1,sumN);
    sumN-=n;
    const string s=readStringLn(n,n);
    const string t=readStringLn(n,n);
    assert(isBinaryString(s));
    assert(isBinaryString(t));
    if(s==t){
        cout<<0<<endl;
        continue;
    }
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
    for(int i=0;i<n;++i){
        if(s[i]=='0')
            seg.set(i,S{1,0});
        else
            seg.set(i,S{0,1});
    }
    vii ans;
    auto change=[&](const lli l,const lli r){
        ans.pb({l,r});
        seg.apply(l,r+1,true);
    };

    auto getChr=[&](const lli pos)->char{
        const auto g=seg.get(pos);
        return g.one+'0';
    };


    lli ps=-1;
    for(int i=0;i+1<n;++i){
        if(t[i]!=t[i+1]){
            ps=i;
            break;
        }
    }

    if(ps==-1){
        cout<<-1<<endl;
        continue;
    }

    if(s[ps]==s[ps+1]){
        bool fl=false;
        for(int i=0;i+1<n;++i){
            if(s[i]!=s[i+1]){
                if(i<ps)
                    change(i,ps);
                else
                    change(ps+1,i+1);
                fl=true;
                break;
            }
        }
        if(!fl){
            cout<<-1<<endl;
            continue;
        }
    }

    for(int i=0;i<ps;++i){
        if(getChr(i)==t[i])
            continue;
        change(i,ps+1);
    }

    for(int i=n-1;i>ps;--i){
        if(getChr(i)==t[i])
            continue;
        change(ps,i);
    }
    for(int i=0;i<n;++i)
        assert(getChr(i)==t[i]);
    assert(sz(ans)<=n);
    cout<<sz(ans)<<endl;
    for(auto x:ans)
        cout<<x.X+1<<" "<<x.Y+1<<endl;
}   aryanc403();
    readEOF();
    return 0;
}
Tester's Solution - STRFLIP2
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
auto isBinaryString=[&](const string s)->bool{
    for(auto x:s){
        if(x!='0'&&x!='1')
            return false;
    }
    return true;
};
T=readIntLn(1,2e3);
lli sumN = 5e3;
while(T--)
{

    const lli n=readIntLn(20,min(1000LL,sumN));
    sumN-=n;
    string s=readStringLn(n,n);
    const string t=readStringLn(n,n);
    assert(isBinaryString(s));
    assert(isBinaryString(t));
    if(s==t){
        cout<<0<<endl;
        continue;
    }

    vii ans;
    auto change=[&](const lli l,const lli r,const bool fl){
        ans.pb({l,r});
        if(fl){
            for(int i=l;i<=r;++i)
                s[i]^=1;
        }
    };

    auto getChr=[&](const lli pos,const bool fl=false)->char{
        return s[pos]^fl;
    };


    lli ps=-1;
    for(int i=0;i+1<n;++i){
        if(t[i]!=t[i+1]){
            ps=i;
            break;
        }
    }

    if(ps==-1){
        cout<<-1<<endl;
        continue;
    }
    const lli mid=n/2;
    if(s[mid]==s[mid+1]){
        bool fl=false;
        for(int i=0;i+1<n;++i){
            if(s[i]!=s[i+1]){
                if(i<mid)
                    change(i,mid,true);
                else
                    change(mid+1,i+1,true);
                fl=true;
                break;
            }
        }
        if(!fl){
            cout<<-1<<endl;
            continue;
        }
    }

    lli l=0,r=n-1;
    bool flag=false;
    while(true){
        while(l<mid&&getChr(l,flag)==t[l]){
            s[l]^=flag;
            l++;
        }
        while(r>mid+1&&getChr(r,flag)==t[r]){
            s[r]^=flag;
            r--;
        }
        if(l==mid&&r==mid+1)
            break;
        change(l,r,false);
        flag^=1;
    }

    s[mid]^=flag;
    s[mid+1]^=flag;
    flag=0;

    if(getChr(mid)!=t[mid]){
        if(getChr(mid+1)!=t[mid+1])
            change(mid,mid+1,true);
        else{
            if(ps+1<mid){
                change(ps,mid-1,true);
                change(ps,mid,true);
            }
            else if(ps+1==mid){
                change(mid,mid+1,true);
                change(ps,mid+1,true);
                change(ps,mid,true);
            } else if(ps==mid){
                /*
                    In this case we have -
                    getChr(mid)!=getChr(mid+1)
                    t[mid]! = getChr(mid)
                    t[mid+1] = getChr(mid+1)
                    Its impossible because these conditions implies t[mid]==t[mid+1]
                    ps by definition is t[ps]!=t[ps+1]
                */
                assert(false);
            } else{
                change(mid,ps+1,true);
                change(mid+1,ps+1,true);
            }
        }
    } else {
        if(getChr(mid+1)!=t[mid+1]){
            if(ps<mid){
                change(ps,mid,true);
                change(ps,mid+1,true);
            }
            else if(ps==mid){
            /*
                In this case we have -
                getChr(mid)!=getChr(mid+1)
                t[mid] == getChr(mid)
                t[mid+1] != getChr(mid+1)
                Its impossible because these conditions implies t[mid]==t[mid+1]
                ps by definition is t[ps]!=t[ps+1]
            */
                assert(false);
            } else if(ps==mid+1){
                change(mid,mid+1,true);
                change(mid,ps+1,true);
                change(mid+1,ps+1,true);
            }
            else{
                change(mid+1,ps+1,true);
                change(mid+2,ps+1,true);
            }
        }
    }

    for(int i=0;i<n;++i)
        assert(getChr(i)==t[i]);
    assert(sz(ans)<=n/2+10);
    cout<<sz(ans)<<endl;
    cerr<<sz(ans)<<" "<<n/2+10<<endl;
    for(auto x:ans)
        cout<<x.X+1<<" "<<x.Y+1<<endl;
}   aryanc403();
    readEOF();
    return 0;
}
Setter's Solution - STRFLIP
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define LL long long
LL seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
#define rand(l, r) uniform_int_distribution<LL>(l, r)(rng)
clock_t start = clock();

#define getchar getchar_unlocked

namespace IO {
long long readInt(char endd) {
    long long ret = 0;
    char c = getchar();
    while (c != endd) {
        ret = (ret * 10) + c - '0';
        c = getchar();
    }
    return ret;
}
long long readInt(long long L, long long R, char endd) {
    long long ret = readInt(endd);
    assert(ret >= L && ret <= R);
    return ret;
}
long long readIntSp(long long L, long long R) {
    return readInt(L, R, ' ');
}
long long readIntLn(long long L, long long R) {
    return readInt(L, R, '\n');
}
string readString(int l, int r, char endd = '\n') {
    string ret = "";
    char c = getchar();
    while (c == '0' || c == '?' || c == '1') {
        ret += c;
        c = getchar();
    }
    assert((int)ret.size() >= l && (int)ret.size() <= r);
    assert(c == endd);
    return ret;
}
}
using namespace IO;

const int TMAX = 1'00'000;
const int N = 1'00'000;
const int SUM_N = 3'00'000;

int sum_n = 0;
void solve() {
    int n = readIntLn(1, N);
    sum_n += n;
    string s = readString(n, n);
    string t = readString(n, n);
    if (s == t) {
        cout << "0\n";
        return;
    }
    bool all_same = true;
    int I;
    for (int i=1;i<n;++i) {
        if (t[i] != t[i-1]) {
            all_same = false;
            I = i;
            break;
        }
    }
    if (all_same) {
        cout << "-1\n";
        return;
    }
    all_same = true;
    for (int i=1;i<n;++i) {
        if (s[i] != s[i-1]) {
            all_same = false;
            break;
        }
    }
    if (all_same) {
        cout << "-1\n";
        return;
    }
    vector<array<int, 2>> ans;
    if (s[I] == s[I-1]) {
        for (int i=I+1;i<n;++i) {
            if (s[i] != s[I]) {
                ans.push_back({I, i});
                for (int j=I;j<=i;++j) s[j] = '1' + '0' - s[j];
                break;
            }
        }
    }

    if (s[I] == s[I-1]) {
        for (int i=I-2;i>=0;--i) {
            if (s[i] != s[I-1]) {
                ans.push_back({i, I-1});
                for (int j=i;j<I;++j) s[j] = '1' + '0' - s[j];
                break;
            }
        }
    }

    assert(s[I-1] != s[I]);
    int swapped = 0;
    for (int j=n-1;j>I;--j) {
        if (swapped) s[j] = '1' + '0' - s[j];
        if (s[j] != t[j]) {
            swapped ^= 1;
            ans.push_back({I-1, j});
            s[j] = t[j];
        }
    }
    if (swapped) {
        s[I-1] = '1' + '0' - s[I-1];
        s[I] = '1' + '0' - s[I];
        swapped = 0;
    }
    for (int j=0;j<I-1;++j) {
        if (swapped) s[j] = '1' + '0' - s[j];
        if (s[j] != t[j]) {
            swapped ^= 1;
            ans.push_back({j, I});
            s[j] = t[j];
        }
    }
    if (swapped) {
        s[I-1] = '1' + '0' - s[I-1];
        s[I] = '1' + '0' - s[I];
        swapped = 0;
    }
    if (s[I] != t[I]) {
        ans.push_back({I-1, I});
        s[I-1] = '1' + '0' - s[I-1];
        s[I] = '1' + '0' - s[I];
    }
    for (int i=0;i<n;++i) assert(s[i] == t[i]);
    cout << ans.size() << '\n';
    assert((int)ans.size() <= n);
    for (auto &e : ans) cout << e[0] + 1 << " " << e[1] + 1 << '\n';
}

int main() {
    int T = readIntLn(1, TMAX);
    while (T--) {
        solve();
    } 
    assert(sum_n <= SUM_N);
    // assert(getchar() == EOF);
    cerr << fixed << setprecision(10);
    cerr << (clock() - start) / ((long double)CLOCKS_PER_SEC) << " secs\n";
    return 0;
}
3 Likes

It would have been much better if the code provided was free from macros

9 Likes

nice “constructive” round

For the input:
1
4
0111
1001
The editorial codes give the output:
1
1 3

How is this valid?
Shouldn’t the answer be “-1”?

Power of the editorialist maybe?!

In the given constraints the minimum length of given strings are 20 . So its not a valid input
but still the answer is correct try to do the operation on paper!