2100 i guess

Not sure about solution so I'd just speculate. Can this problem be solved greedily?

We can choose either $$$a$$$ or $$$b$$$ WLOG and fill it greedily from left to right in accordance with the supply of the current connected component in the non-chosen string. Like, for each string, a consecutive series of $$$1$$$ on its identity string ($$$c$$$ for $$$a$$$, $$$d$$$ for $$$b$$$) is a component, and every $$$0$$$ is a separate component.

If this solution was the case, I think the Codeforces rating would fall around 1600-1700. But proving and/or intuitively discovering this is odd on its own.

Div1 A maybe? Hard to estimate exactly since I don't know the Div2 difficulties nowadays, but I think it's pretty easy to see the greedy approach and why it works. I'd expect to AC it in ~10 minutes if it's given as Div1 A which sounds about par.

It's a greedy I figured out in 15 mins give or take. Somewhat annoying implementation. I would say between 1400 and 1700? I feel like I have seen either a div2 B or a C with annoying 0s and 1s counting.

Just made a Luogu account for this problem. I would say this is pretty easy problem like the first idea that came to my mind of just doing it greedily worked, It could have been hard to implement but I just abused DSU and did it pretty fast, I am pretty sure if you take away the implementation a newbie could very well come up with the idea, but I would rate it 1400-1700.

#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int> f;
    vector<vector<int>> sz;
    DSU(int n)
    {
        init(n);
    }

    void init(int n)
    {
        f.assign(n, 0);
        iota(f.begin(), f.end(), 0);
        sz.assign(n, vector<int>(2, 0));
    }

    int find(int a)
    {
        while (a != f[a])
            a = f[a] = f[f[a]];
        return a;
    }

    void add(int i, int v)
    {
        sz[find(i)][v]++;
    }

    void sub(int i, int v)
    {
        sz[find(i)][v]--;
    }

    bool same(int a, int b)
    {
        return (find(a) == find(b));
    }

    bool merge(int a, int b)
    {
        a = find(a);
        b = find(b);

        if (a == b)
            return false;

        f[b] = a;
        for (int v = 0; v < 2; v++)
            sz[a][v] += sz[b][v];
        return true;
    }

    int size(int a, int p)
    {
        return sz[find(a)][p];
    }
};

void solve()
{
    int n;
    cin >> n;
    string a, b, c, d;
    cin >> a >> c >> b >> d;

    DSU g1(n), g2(n);

    for (int i = 0; i < n; i++)
    {
        if (i + 1 < n && b[i] == b[i + 1] && b[i] == '1')
            g1.merge(i, i + 1);
        if (i + 1 < n && d[i] == d[i + 1] && d[i] == '1')
            g2.merge(i, i + 1);
        g1.add(i, a[i] - '0');
        g2.add(i, c[i] - '0');
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int leader1 = g1.find(i);
        int leader2 = g2.find(i);
        if (g1.size(leader1, 1) > 0 && g2.size(leader2, 1) > 0)
        {
            ans++;
            g1.sub(leader1, 1);
            g2.sub(leader2, 1);
        }
        else if (g1.size(leader1, 0) > 0 && g2.size(leader2, 0) > 0)
        {
            ans++;
            g1.sub(leader1, 0);
            g2.sub(leader2, 0);
        }
    }

    cout << ans << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

I think this is 1800

At first, I thought this problem is trivial, as you just go through and perform an arbitary match if you can. I thought it is an easy (guarnateed profit)>=(maximum cost) situation. I thought it was 1300 upto here.

Then, I realised this is wrong. There are situations where both 0 and 1 could be matched. And you could not decide it without serious lookaheads. This can happen when the number of remaining allowed matches is less than the potential matchings you could do. This would reject the simple greedy more than enough for my taste.

Turns out, it is still possible to solve from here: We just take keep the potential option if both can be matched. That is, after each matching, we can have "stuff that must be 0", "stuff that must be 1", "stuff that can be either 0 or 1 as you like".

If this were the only solution then it would be 1900. I would never have looked any further and just implement it out. However, seeing the simplest greedy is actually extremely subtle. It depends critically on the fact that a group of size $$$k$$$ would have $$$k$$$ opportunties to match with something else before. Making such number of matches must result in either (1) '0' or '1' being exhuasted, or (2) the numbers of '0's and '1's are at most the remaining number of matches you are allowed to perform. In both cases, all the matching can be conducted without any potential nontrivial choices.

If I am forced to discover this, I would even rate this as 2700 or higher.

My conclusion is: Most people that submitted this greedy either did not prove, or gave a wrong proof. There are some more involved, but certainly correct solutions, and many should have chosen them instead.

That said, guessing a greedy that then it passing is still a skill, so I think a 1800 rating is appropriate: however, it is far more volatile than what this rating suggests.