The problem can be found here

My Thought Process

I really liked this problem. Let’s first count the number of ‘?’ on the left half of the string and the right half of the string.

We realize that we can always pair each ‘?’ on each half. Each person can just can copy the last person’s number they change so the difference doesn’t change so its essentially the same problem.

Think of it this way, if one player has a winning strategy from that position, the player would want to keep that position the same.

So we can just subtract the minimum number of ‘?’ on both sides from both side and consider the side with more ‘?’s.

Now, how do Monocarp win? If the sum of the half with ‘?’ is already larger than the other half, obviously he always win no matter what the rest of the ‘?’ are.

Else, if its smaller, he has two choices. Try to make it so after all the ‘?’ are set, the number is smaller than the other half or greater than the other half. So he should always use ‘0’ or ‘9’. Likewise, Bicarp would want to prevent him from doing that so he would either use ‘9’ or ‘0’.

The only difference between these is that Monocarp goes first so it will be slightly different. See the code below for more details.

This is really informal but it does makes sense. See the comments of the editorial for a really nice proof.

Implementation

#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; string s;
    cin >> n >> s;
    int l = 0, r = 0;
    int a = 0, b = 0;

    for(int i = 0; i < n/2; ++i){
        if(s[i] == '?'){
            l++;
        }
        else{
            a += (s[i] - '0');
        }
    }

    for(int i = n/2; i < n; ++i){
        if(s[i] == '?'){
            r++;
        }
        else{
            b += (s[i] - '0');
        }
    }

    if(l == r){
        if(a == b){
            cout << "Bicarp" << endl;
        }
        else{
            cout << "Monocarp" << endl;
        }
    }
    else{
        if(l < r){
            swap(l, r);
            swap(a, b);
        }

        int c = l - r;

        if(a + (c/2) * 9 + (c % 2 == 1) * 9 > b){
            cout << "Monocarp" << endl;
        }
        else if(a + (c/2) * 9 < b){
            cout << "Monocarp" << endl;
        }
        else{
            cout << "Bicarp" << endl;
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    solve();

    return 0;
}

See here for the solution and another implementation.