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	155
9	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!

	Rev.	Lang.	By	When	Δ	Comment
	en1		shiny_shine	2024-12-03 13:05:40	3335	Initial revision (published)

Rev.

Lang.

When

Comment

en1

shiny_shine

2024-12-03 13:05:40

3335

Initial revision (published)

History