MERGEBS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Jeevan Jyot Singh
Tester: Aryan Choudhary
Editorialist: Lavish Gupta

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Dynamic Programming, Inversions

PROBLEM:

You have two binary strings A and B, both of length N. You have to merge both the binary strings to form a new binary string C of length 2 \cdot N. The relative order of characters in the original binary strings A and B should not change in the binary string C.

For example, if A = {\color{blue}01011} and B = {\color{red}10100}, one possible way to merge them to form C is: C = {\color{blue}0}{\color{red}1}{\color{red}0}{\color{blue}1}{\color{red}1}{\color{blue}0}{\color{blue}1}{\color{blue}1}{\color{red}0}{\color{red}0}.

Minimize the number of inversions in the merged binary string C.

As a reminder, a pair of indices (i, j) is an inversion for binary string C if and only if 1 \leq i \lt j \leq |C|, C_i = 1 and C_j = 0.

QUICK EXPLANATION:

We will use the above notation of pair of indices (i, j) to denote inversions.

  • Suppose you have already merged the substrings A[1 ... i] and B[1...j]. So the next two characters that you need to consider are A[i+1] and B[j+1]. Which character will you take next out of these two?

  • Let A[i+1] be 1, and we choose to take this character as the next character to merge. The new inversions that will be created in the future because of this step will be
    \# 0's in A[i+1 ... N] + \# 0's in B[j+1 ... N].

  • In other words, for these many indices j' in future, (i', j') will be an inversion pair, where i' = i+j+1, and j'> i'.
    The same argument holds for B[j+1].

  • Let A[i+1] be 0, and we choose to take this character as the next character to merge. There will be no new inversions that will be created in the future because of this step (because C_{i'} should be 1 for new inversions to be created in future that starts at this index).

  • By above explanation, we can have a dp[i][j] which denotes the number of inversions when A[i...N] and B[j...N] are merged. Note that it is little different than the above explanation, just to be consistent with how standard DPs like LCS are defined. We Calculate dp[i][j] in terms of dp[i+1][j], dp[i][j+1] and number of 0's in suffix of A and B.

EXPLANATION:

Such types of problems are usually based on Greedy or Dynamic Programming approaches.

We can start our analysis by considering the following situation. Let say we have already merged the substrings A[1 ... i] and B[1...j]. So the next two characters that we need to consider are A[i+1] and B[j+1]. The question is, which character should we choose?

Some greedy thinking can tell you that if either of one of A[i+1] or B[j+1] is 0, then we can take this character as our next character, as it will not increase the inversion count in future. However, if we have both A[i+1] and B[j+1] as 1, then we are stuck. Which 1 to take?

There can be some more greedy things that you can think of at this point, like maybe continue choosing those 1's which will lead to a 0 faster? But you will soon realize that all these greedy algorithms will fail.

This motivates us to think in the direction of Dynamic Programming. What happens when we choose, let say A[i+1]?
There are two main observations after this merge:

  1. The new inversions that will be created in the future because of this step will be
    \# 0's in A[i+1 ... N] + \# 0's in B[j+1 ... N].
  2. We now have A[i+2] and B[j+1] as our next two characters, and we essentially have the same problem again, with the reduced strings A[i+2 ... N] and B[j+1 ... N]!!

Same thing holds for B[j+1].
If A[i+1] is 0, and we merge A[i+1], then we do not create any new inversion.

The above explanation suggests us to have a 2-dimensional DP, say dp[i][j].
Let cnt_a[i] stores the number of 0's in $ in A[i...N], and cnt_b[i] stores the number of 0's in $ in B[i...N].

Let dp[i][j] denote the number of inversions when A[i...N] and B[j...N] are merged.
Then we will have the following transitions:

If A[i] is 0, and we merge this character, then dp[i][j] = dp[i+1][j].
If A[i] is 1, and we merge this character, then dp[i][j] = dp[i+1][j] + cnt_a[i] + cnt_b[j].

Similarly for B[j], and we take the minimum value of dp[i][j] over all these 4 cases.

TIME COMPLEXITY:

Calculating the arrays cnt_a and cnt_b will take O(N) time.
Calculating dp[i][j] will take O(1) time, provided that required dp values are calculates and stored.
So, the overall time complexity will be O(N^2)

SOLUTION:

Setter's Solution
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const double EPS = 1e-9;
const long long INF = 1e18;

const int N = 1e6+5; 

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, 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;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            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); }

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

// -------------------- Input Checker End --------------------

int32_t main()
{
    IOS;
    int T = readIntLn(1, 1000);
    int sumN = 0;
    while(T--)
    {
        int n = readIntLn(1, 1000);
        int m = n;
        sumN += n;
        string s = readStringLn(n, n); 
        string t = readStringLn(n, n); 
        s = '#' + s, t = '#' + t;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));    
        vector<int> ps(n + 1) , pt(m + 1);
        for(int i = 1; i <= n; i++)
            ps[i] = ps[i-1] + (s[i] == '1');
        for(int i = 1; i <= m; i++)
            pt[i] = pt[i-1] + (t[i] == '1');
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++)
        {
            dp[i][0] = dp[i-1][0];
            if(s[i] == '0')
                dp[i][0] += ps[i-1];
        }
        for(int j = 1; j <= m; j++)
        {
            dp[0][j] = dp[0][j-1];
            if(t[j] == '0')
                dp[0][j] += pt[j-1];
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(s[i] == '0')
                    dp[i][j] = min(dp[i][j], dp[i-1][j] + ps[i-1] + pt[j]);
                else
                    dp[i][j] = min(dp[i][j], dp[i-1][j]);
            
                if(t[j] == '0')
                    dp[i][j] = min(dp[i][j], dp[i][j-1] + ps[i] + pt[j-1]);
                else
                    dp[i][j] = min(dp[i][j], dp[i][j-1]);
            }
        }
        cout << dp[n][m] << endl;
    }
    assert(sumN <= 2000);
    readEOF();
    return 0;
}
Tester's Solution
/* 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;
};

lli sumN = 2e3;
T=readIntLn(1,1e3);
while(T--)
{

    const lli n=readIntLn(1,min(1000LL,sumN));
    sumN-=n;
    const string s=readStringLn(n,n);
    const string t=readStringLn(n,n);
    assert(isBinaryString(s));
    assert(isBinaryString(t));
    vi a(n+1),b(n+1);
    for(int i=0;i<n;++i){
        a[i+1]=a[i]+s[i]-'0';
        b[i+1]=b[i]+t[i]-'0';
    }
    vector<vi> dp(n+1,vi(n+1,-1));
    const lli ans=y_combinator([&](const auto &self,lli i,lli j)->lli{
        if(i<0||j<0)
            return INF;
        lli &ans=dp[i][j];
        if(ans!=-1)
            return ans;
        if(i==0&&j==0)
            return ans=0;
        ans=INF;
        const lli c=a[i]+b[j];
        if(s[i-1]=='0')
            ans=min(ans,c+self(i-1,j));
        else
            ans=min(ans,self(i-1,j));

        if(t[j-1]=='0')
            ans=min(ans,c+self(i,j-1));
        else
            ans=min(ans,self(i,j-1));

        return ans;
    })(n,n);
    cout<<ans<<endl;
}   aryanc403();
    readEOF();
    return 0;
}

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std ;
const int inf = 1000000000 ;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    int t ;
    cin >> t ;
    while(t--)
    {
        int n;
        cin >> n ;

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

        vector<int> cnt_a(n+1) , cnt_b(n+1) ;

        for(int i = n-1 ; i >= 0 ; i--)
        {
            cnt_a[i] = cnt_a[i+1] + (a[i] == '0') ;
            cnt_b[i] = cnt_b[i+1] + (b[i] == '0') ;
        }

        int dp[n+1][n+1] ;
        for(int i = 0 ; i <= n ; i++)
            for(int j = 0 ; j <= n ; j++)
                dp[i][j] = inf ;

        dp[n][n] = 0 ;

        for(int i = n ; i >= 0 ; i--)
        {
            for(int j = n ; j >= 0 ; j--)
            {
                if(i < n)
                {
                    if(a[i] == '0')
                        dp[i][j] = min(dp[i][j] , dp[i+1][j]) ;
                    else
                        dp[i][j] = min(dp[i][j] , dp[i+1][j] + cnt_a[i] + cnt_b[j]) ;
                }

                if(j < n)
                {
                    if(b[j] == '0')
                        dp[i][j] = min(dp[i][j] , dp[i][j+1]) ;
                    else
                        dp[i][j] = min(dp[i][j] , dp[i][j+1] + cnt_a[i] + cnt_b[j]) ;
                }
            }
        }
        
        cout << dp[0][0] << endl ;
    }
 
    return 0;
}
12 Likes

Can you provide a testcase where greedy fails.

6 Likes

9 posts were merged into an existing topic: Updates on curtailing plagiarism

6
101010
110000

1 Like

What’s wrong with this solution?
#include <bits/stdc++.h>

#include

using namespace std;

int main()

{

int t;

cin >> t;

while (t--)

{

    int n;

    cin >> n;

    string a, b;

    cin >> a;

    cin >> b;

    int count_a_0=0,count_a_1=0;

    int count_b_0=0,count_b_1=0;

    for(int z=0;z<n;z++){

        if(a[z]=='0'){

            count_a_0++;

        }

        else{

            count_a_1++;

        }

        if(b[z]=='0'){

            count_b_0++;

        }

        else{

            count_b_1++;

        }

       

    }

    int final = 0;

    int count = 0;

    int i = 0, j = 0;

    while (i < a.length() || j < b.length())

    {

        if (i < a.length() && a[i] == '0')

        {

            final += count;

            count_a_0--;

            i++;

        }

        else if (j < b.length() && b[j] == '0')

        {

            count_b_0--;

            final += count;

            j++;

        }

        else

        {

            if(i>=a.length()){

                 count+=1;

               

                j++;

            }

            else if(j>=b.length()){

                count+=1;

                i++;

            }

            else if(count_a_0==count_b_0){

                if(count_a_1<=count_b_1){

                    count+=1;

                    count_a_1--;

                    i++;

                }

                else{

                    count_b_1--;

                    count+=1;

                    j++;

                }

            }

            else if (count_a_0>count_b_0)

            {

                count += 1;

                count_a_1--;

                i++;

            }

            else{

                count+=1;

                count_b_1--;

                j++;

            }

        }

       

    }

    cout<<final << endl;

}

}

This works for my code. Can you give any other test case?

Can anyone please give a test case where greedy approach will fail, examples given in the comment works for my code:

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t,n;
	cin>>t;
	while(t--)
	{
	   cin>>n;
	   string s1,s2;
	   cin>>s1>>s2;
	   int c=0,z1=0,z2=0,i1=0,i2=0,j1,j2,c1,c2;
	   //cout<<"s1"<<s1;
	   //cout<<"s2"<<s2;
	   while(i1<n)
	   {
	       if(s1[i1]=='0')
	       z1++;
	       if(s2[i1]=='0')
	       z2++;
	       
	       i1++;
	   }
	   i1=0;
	   //cout<<"z1"<<z1;
	   //cout<<"z2"<<z2;
	   while(i1<n && i2<n)
	   {
	       if(s1[i1]=='1' && s2[i2]=='1')
	       {
	           if(z1>z2)
	           {
	               i1++;
	               c+=(z1+z2);
	           }
	           else  if(z1<z2)
	           {
	               i2++;
	               c+=(z1+z2);
	           }
	           else if(z1!=0)
	           {
	               
	               j1=i1+1;
	               j2=i2+1;
	               c1=s1[i1]-'0';
	               c2=s2[i2]-'0';
	               while(j1<n && c1==c2)
	               {
	                   c1+=s1[j1++]-'0';
	                   c2+=s2[j2++]-'0';
	               }
	               if(c1<c2)
	               {
	                  i1++;
	                  c+=(z1+z2); 
	               }
	               else
	               {
	                  i2++;
	                  c+=(z1+z2); 
	               }
	           }
	           else
	           {
	             break; 
	           }
	       }
	       else  if(s1[i1]=='0' && s2[i2]=='1')
	       {
	           i1++;
	           z1--;
	       }
	       else  if(s1[i1]=='1' && s2[i2]=='0')
	       {
	           i2++;
	           z2--;
	       }
	       //both 0
	       else
	       {
	           if(z1>z2)
	           {
	               i1++;
	               z1--;
	           }
	           else  if(z1<z2)
	           {
	               i2++;
	               z2--;
	           }
	          else if(z1!=0)
	           {
	               
	               j1=i1+1;
	               j2=i2+1;
	               c1=s1[i1]-'0';
	               c2=s2[i2]-'0';
	               while(j1<n && c1==c2)
	               {
	                   c1+=s1[j1++]-'0';
	                   c2+=s2[j2++]-'0';
	               }
	               if(c1<c2)
	               {
	                  i1++;
	                  z1--;
	               }
	               else
	               {
	                  i2++;
	                  z2--; 
	               }
	           }
	           else
	           {
	             break; 
	           }
	       }
	   }
	    while(i1<n)
	    {
	        if(z1==0)
	        {
	            break;
	        }
	        else
	        {
	            if(s1[i1]=='1')
	           {
	               c+=z1;
	           }
	           else
	           {
	               z1--;
	           }
	           i1++;
	        }
	    }
	    while(i2<n)
	    {
	        if(z2==0)
	        {
	            break;
	        }
	        else
	        {
	            if(s2[i2]=='1')
	           {
	               c+=z2;
	           }
	           else
	           {
	               z2--;
	           }
	           i2++;
	        }
	    }
	    
	   cout<<c<<endl;
	}
	return 0;
}

Can some one tell me the problem with just making the new string by adding as many zeroes till both strings have 1 and then adding the one which has more zeroes left after that index . etc.etc

ll n;

    cin>>n;

    string a,b;

    cin>>a>>b;

    ll aaa=stoi(a,0,2);

    ll bb=stoi(b,0,2);

   ll a0=n-__builtin_popcount(aaa);

   ll b0=n-__builtin_popcount(bb);

    ll z=a0+b0;

   

    ll i=0,j=0;

    ll aa[2*n]={0};

   

    while(i<n && j<n)

    {

       if (a[i]=='0' and b[j]=='0')

       {

           i++;

           j++;

           a0--;

           b0--;

       }

        else if (a[i]=='1' and b[j]=='1')

         {

              if (a0>b0)

              {

                  aa[i+j]=1;

                  i++;

              }

              else

              {

                  aa[i+j]=1;

                  j++;

              }

         }else if (a[i]=='0' and b[j]=='1')

         {

              a0--;

              i++;

         }else{

                b0--;

                j++;

         }

       

    }

    while(i<n)

    {

        aa[i+j]=a[i]-48;

        i++;

    }

    while(j<n)

    {

        aa[i+j]=b[j]-48;

       

        j++;

    }

    ll ans=0;

    l(i,0,2*n)

    {

        // cout<<aa[i]<<"|"<<i<<" ";

        if(aa[i]==0)

        {

            z-=1;

           

        }else{

            ans+=z;

        }

    }

    cout<<ans<<"\n";

I think the tests are weak. My O(n^3) DP solution passes. I coded this to check my logic and was hoping to optimize this using segment tree but O(n^3) passed.
Code Link: Solution: 56708097 | CodeChef

What should be the answer for this test case.
I’m getting 26 , is it correct?

Can someone plz explain me this doubt :
The editorial mentions that if we’ve merged A[1…i] and B[1…j], now we’ve to take either A[i+1] or B[j+1] but why cant we take both, I mean A[i+1] and B[j+1]

https://www.codechef.com/viewsolution/56740325 My Top Down Solution to the problem, if anybody is interested.

3 Likes

Logic : take substrings of one’s and zero’s and find the value which should be placed before since a string’s own contribution cannot be changed, all we can do is change the contribution in the of a string in the second string.

On your tc my code is giving 20.
But wa ;_;

/*    Author : Prakhar Rai    */
#include<bits/stdc++.h>
using namespace std;

typedef long long 		 ll;
typedef long double		 ld;

#define FIO         ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ln(s)	    ll(s.length())
#define sz(a)	    ll(a.size())
#define pb          emplace_back
#define fs          first
#define sc          second
#define vcll        vector<ll>
#define all(x)      x.begin(),x.end()
#define endl        "\n"
#define vc          vector
#define FOR(i,a,b)  for(ll i = a; i < b; i++)
#define pika(x)     cerr << #x << ' ' << x << endl;
#define yes         "YES"
#define no          "NO"

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 5;



void test_case() {
	ll n, p1(0), p2(0);
	cin >> n;
	string a, b, s = "";
	cin >> a >> b;

	while (p1 < n and a[p1] == '0') p1++;
	while (p2 < n and b[p2] == '0') p2++;

	ll fa = 1, fb = 1, ans = 0; // add individual contributions
	while (p1 < n and p2 < n) {
		ll a0, a1, b0, b1, sa, ea, sb, eb;
		a0 = a1 = b0 = b1 = 0;

		sa = p1;
		while (p1 < n and a[p1] != '0') a1++, p1++;
		while (p1 < n and a[p1] != '1') a0++, p1++;
		ea = p1;

		sb = p2;
		while (p2 < n and b[p2] != '0') b1++, p2++;
		while (p2 < n and b[p2] != '1') b0++, p2++;
		eb = p2;


		// cout << "a " << sa << ' ' << ea << endl;
		// cout << "b " << sb << ' ' << eb << endl;

		// add edge case - end one's
		// cerr << a0 << ' ' << a1 << endl;
		// cerr << b0 << ' ' << b1 << endl;

		if (a1 * b0 < b1 * a0) {
			s += a.substr(sa, ea - sa);
			p2 = sb;
		} else {
			s += b.substr(sb, eb - sb);
			p1 = sa;
		}

		// cout << s << endl;
	}

	if (p1 < n) while (p1 < n) s += a[p1++];
	if (p2 < n) while (p2 < n) s += b[p2++];

	// cout << ans << endl;
	// cout << s << endl;
	// s = "101010110110";
	ll len = ln(s);
	for (int i = 0; i < len; i++) {
		if (s[i] == '1') {
			ll z = 0;
			for (int j = i + 1; j < len; j++)
				if (s[j] == '0') z++;
			ans += z;
		}
	}
	cout << s << endl;
	cout << ans << endl;
}



int main() {
	FIO;
	int _tests;
	_tests = 1;
	cin >> _tests;
	for (int i = 1; i <= _tests; i++) {
		// cout << "Case #" << i << ": ";
		test_case();
	}
}

I’m getting Runtime Error in last 3 testcases , can someone please tell me what’s the problem.
import sys

for _ in range(int(input())):

    def rec(i, j, zeros, memo={}):

        if (i, j) in memo:
            return memo[(i, j)]

        if i >= n:
            x = s2[j:].count('0')
            count = 0
            for k in range(j, n):
                if s2[k] == '0':
                    x -= 1
                else:
                    count += x
            return count
        if j >= n:
            x = s1[i:].count('0')
            count = 0
            for k in range(i, n):
                if s1[k] == '0':
                    x -= 1
                else:
                    count += x
            return count

        else:
            if s1[i] == "1" and s2[j] == "1":
                memo[(i, j)] = zeros + min(rec(i + 1, j, zeros), rec(i, j + 1, zeros))
                return memo[(i, j)]
            elif s1[i] == "0" and s2[j] == "0":
                memo[(i, j)] = min(rec(i + 1, j, zeros - 1), rec(i, j + 1, zeros - 1))
                return memo[(i, j)]
            else:
                if s1[i] == "0":
                    memo[(i, j)] = min(rec(i + 1, j, zeros - 1), zeros + rec(i,j+1,zeros))
                    return memo[(i, j)]
                elif s2[j] == "0":
                    memo[(i, j)] = min(rec(i, j + 1, zeros - 1), zeros + rec(i+1,j,zeros))
                    return memo[(i, j)]


n = int(input())
s1 = sys.stdin.readline()
s2 = sys.stdin.readline()
z = s1.count('0') + s2.count('0')
print(rec(0, 0, z))

Can Anybody Tell Me in Which testcase This code will fail?
Is this code right or not?
Bottom Up DP Solution.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[1001][1001];
int solve(string a,string b,string c,int i,int j)
{
    // cout<<i<<" "<<j<<"\n";
    if(i==a.size() or j == b.size())
    {
        //count inversion and return that
        if(i==a.size())
        {
            c+=b.substr(j);
        }
        else if(j == b.size())
        {
            c+=a.substr(i);
        }
        // cout<<c<<"\n";
        int ans = 0;
        for(int i=0;i<c.size();i++)
        {
            if(c[i]=='0') continue;
            int cnt = 0;
            for(int j = i+1;j<c.size();j++)
            {
                if(c[j]=='0')
                {
                    cnt++;
                }
            }
            ans+=cnt;
        }
        return  dp[i][j] =  ans;
    }
    if(dp[i][j]!=-1)
    {
        return dp[i][j];
    }
    if(a[i] == b[j])
    {
        int op1 = solve(a,b,c+a[i],i+1,j);
        int op2 = solve(a,b,c+b[j],i,j+1);
        return dp[i][j] = min(op1,op2);
    }
    else
    {
        if(a[i]=='0')
        {
            return  dp[i][j] =  solve(a,b,c+a[i],i+1,j);
        }
        if(b[j]=='0')
        {
            return  dp[i][j] =  solve(a,b,c + b[j], i ,j+1);
        }
    }
    return  dp[i][j] =  0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
   
    while(t--)
    {
        memset(dp,-1,sizeof(dp));
        int n;
        cin>>n;
        string a,b;
        cin>>a>>b;
        string c;
        cout<<solve(a,b,c,0,0)<<"\n";
    }
    return 0;
}

8
00101010
10111010
Ans is 25

See my post above, it gives 25 too!

I think, runtime error seems to be caused due to maximum recursion depth getting exceeded.
For fixing this just add the following line after importing the sys module.

sys.setrecursionlimit(10 ** 6)

For more info, you can refer this

Thanks man it did worked.
That’s why i love this community.

can you give the resultant string
mine is
0010111010101010
and answer comes 31.