How difficult is this problem?

#	User	Rating
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3443
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	158
5	-is-this-fft-	158
7	awoo	156
8	djm03178	154
8	TheScrasse	154
10	Dominater069	153

Well, codeforcers, it's quite a while since I visited here last time.

If you read this blog, you might know that, a few days ago, NOIP 2024 took place. On Luogu, the difficulties of the four problems are defined as Blue, Green, Purple and Purple. However, when I saw that problem A is blue, I became confused and couldn't understand why it's blue. The forum of this problem in Luogu is CHAOTIC. What I mean is, there are people consider this problem as a problem even a newbie (yes, codeforces newbie) can solve without difficulty, while others say this problem has a difficulty similar to problems in Provincial Team Selection. I'd like to ask you, how difficult is this problem? Here comes the statement:

An integer $$$n$$$ ($$$1\le n\le 10^5$$$) and four 01-strings with a length of $$$n$$$ are given, I will call them $$$a,b,c,d$$$ below.

Now, you want to let string $$$a$$$ and $$$b$$$ be as similar as possible. So, you can perform the following operations:

Operation $$$1$$$: choose an integer $$$i$$$ ($$$1\le i< n$$$), which satisfies $$$c_i=c_{i+1}=1$$$, then swap $$$a_i$$$ and $$$a_{i+1}$$$.
Operation $$$2$$$: choose an integer $$$i$$$ ($$$1\le i< n$$$), which satisfies $$$d_i=d_{i+1}=1$$$, then swap $$$b_i$$$ and $$$b_{i+1}$$$.

After performing the operations above for arbitrary times, possibly $$$0$$$ times, print the following value:

$$$ \max \sum_{i=1}^n [a_i=b_i] $$$

And here's my code which is able to pass all the samples Luogu given:

Code

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n, res, ta[2], tb[2];
string a, b, c, d;
void init_global()
{
}
void init_local()
{
    cin >> n >> a >> b >> c >> d;
    ta[0] = ta[1] = tb[0] = tb[1] = res = 0;
}
void run()
{
    for (int i = 0; i < n and c[i] == '1'; i++)
    {
        ta[a[i] - '0']++;
    }
    for (int i = 0; i < n and d[i] == '1'; i++)
    {
        tb[b[i] - '0']++;
    }
    for (int i = 0; i < n; i++)
    {
        if (!ta[0] and !ta[1])
        {
            if (c[i] == '1')
            {
                for (int j = i; j < n and c[j] == '1'; j++)
                {
                    ta[a[j] - '0']++;
                }
            }
            else
                ta[a[i] - '0']++;
        }
        if (!tb[0] and !tb[1])
        {
            if (d[i] == '1')
            {
                for (int j = i; j < n and d[j] == '1'; j++)
                {
                    tb[b[j] - '0']++;
                }
            }
            else
                tb[b[i] - '0']++;
        }
        if (ta[0] and tb[0])
        {
            res++, ta[0]--, tb[0]--;
            continue;
        }
        if (ta[1] and tb[1])
        {
            res++, ta[1]--, tb[1]--;
            continue;
        }
        if (ta[0])
        {
            ta[0]--, tb[1]--;
            continue;
        }
        ta[1]--, tb[0]--;
    }
    printf("%d\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    init_global();
    while (T--)
    {
        init_local();
        run();
    }
}

Please write how difficult do you think of this problem in comment, and a Codeforces difficulty value if you can. Thanks!

Comments (6)

Write comment?

mathema23

23 hours ago, # |

-10

2100 i guess

→ Reply

AkiLotus

22 hours ago, # |

← Rev. 2 →

+23

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.

Enchom

+13

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.

JulSjlv

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.

f20221318

17 hours ago, # |

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.

Here is my Code

#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;
}

arvindf232

16 hours ago, # |

+28

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.

shiny_shine's blog