# STRFLIP, STRFLIP2 - Editorial

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

# DIFFICULTY:

Easy-Medium, Medium

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.

# 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
#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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

vi a(n);
for(int i=0;i<n-1;++i)
return a;
}

// #include<atcoder/dsu>
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         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;
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;
};
lli sumN = 3e5;
while(T--)
{

sumN-=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();
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
#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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

vi a(n);
for(int i=0;i<n-1;++i)
return a;
}

// #include<atcoder/dsu>
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         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;
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;
};
lli sumN = 5e3;
while(T--)
{

sumN-=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();
return 0;
}

Setter's Solution - STRFLIP
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define LL long long
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 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) {
assert(ret >= L && ret <= R);
return ret;
}
long long readIntSp(long long L, long long R) {
}
long long readIntLn(long long L, long long R) {
}
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() {
sum_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() {
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?