Hoping to cross 1700 in this contest ^-^

Hope I can reach Specialist qwq

Is there a big gap between the levels of B and C like old contests?

How is your E1 from today already skipped with no resubmissions? And how come your "first" contest 3 months ago was set by the same author?

There's no such thing as a coincidence

Yeah I thought of maybe till D(easy version) can be easy but since u warned I am gonna try till C

now that sounds scary

This really sounds scary.Will this haunt me for the rest of my life?

As a tester, I am zltzlt and Zunpet fan.

I was thinking of participating!

it means if you solve the question A, at the minute 0, you will gain 500 points. if you get a wrong answer verdict on that question the pointes you will get becomes lower, and over time in every minute gets passed, the maximum score that you can get also decreases.

some problems have subtasks which are marked in parentheses, the first is the score you get if you solve the easy version and the second is if you solve the hard version

This means

Problem A: 500 pts

Problem B: 750 pts

Problem C: 1000 pts

Problem D1: 1000 pts

Problem D2: 1250 pts

Problem E1: 1750 pts

Problem E2: 1000 pts

Problem F: 2500 pts

Point values decrease if u get one wrong or as time goes on.

good luck

I checked your stat on Codeforces Visualizer 4fun. Why on earth you solved 213 800-rated problems and only 9 1900-rated :)

no blame or something, just curious.

How it went brother?

Nice beta fish

these are not problem rating . these are the score you get from the problem.

I think if you solve 800 problems just for improving implementation,it would be better.

stucking is very common everyone gets stuck and reading editorial is not bad then just read the editorial understand it and then implement it simple. If in editorial there is a topic mentioned which u don't know then just read it first then implement the solution with that logic. It is obvious u will get stuck if u are solving higher rating problems

string forces

newbies cheaters

us bro us need alot of practice to solve faster than cheaters

Meanwhile,

rainboy [thinking] :===> aryanc403 ... who ! what ! where ! Am I supposed to care !

PS : I am also fan of Aryanc, but Rainboy has different Aura to him. so, please don't get offended.

It's easy to see that Turtle can achieve at least value x, iff there are at least [n/2] values i of array such that a[i] >= x.

Consider a similar game, but the move is "remove an element" for both players.

An optimal strategy is for Turtle to always remove the smallest remaining element and Piggy the largest remaining.

Observe that the given operation effectively boils down to "remove an element as long as it has a smaller (Turtle) / bigger (Piggy) element next to it. As such, the optimal strategy does not change for either player.

The idea of my solution is: Turtle will always remove the current smallest, and Piggy will always remove the current largest (My intuition was that a player should remove the element that is the most disadvantageous to him, or there will remain some element that is disadvantageous towards the end, thus not giving an optimal result to him)

im ngl i just guessed and it worked. my solution was to count the freq of each character, and then to print all the characters with the current max frequency.

I sorted the charachets in descending order of number of occurences.

    string s, x = "";
    int n;
    cin >> n >> s;
    pair<int, char> a[26];
    for(int i = 0;i<26;++i) {
        a[i] = {0, (char)('a' + i)};
    }
    for(const char& v:s) {
        a[(int)(v - 'a')].fi++;
    }
    sort(a, a + 26, cmp);
    while(true) {
        bool ok = true;
        for(int j = 0;j<26;++j) {
            if (a[j].fi > 0) {
                x+=a[j].se, a[j].fi--, ok = false;
            }
        }
        if (ok) {
            break;
        }
    }
    cout << x << endl;
    return;

How to do D1, I tried finding the maximum mex for f(0), then I print the answer mx*(k) for the highest k such that f(k)<=mx otherwise I added m*(m+1)-k*(k-1)/2 to the answer.

Because you can choose $$$max(f(i), x)$$$ $$$= 4$$$, it's not necessary to do the operation, without doing the operation you will have $$$x=4$$$

Zero operation is allowed.

i think that is like 2 or 3 times easier than C, what i can't rlly understand is how there are 10k solves for C...

with dp it feels easy

0 --> 1 --> 3

Use 2nd to get 0. Then use 1st to get 3.

First operation on the second array, 0->1 then second operation on the first array, 1->3

What was the easy guess for C? What i guessed (and worked) didn't look very obvious and took me 1 hour.

Hints for D1 and D2

What is the first thing that we know about mex? Mex of $$$n$$$ integers is at most $$$n$$$. Therefore, if we were to perform at least one operation, $$$x$$$ can grow no longer than the maximum $$$n$$$ in the input. Therefore, the constraints $$$m \leq 10^9$$$ essentially means that $$$m \leq 2 \cdot 10^5$$$, since after this point, it's optimal to not do any operations on $$$x$$$.

This gives us confidence to calculate the answer for each $$$f(i)$$$.

Consider any list. What happens when you apply the operation on it. Remember that the $$$mex(L)$$$ is missing from this list, therefore, if you don't provide $$$mex(L)$$$, it'd still be missing. Hence, you can only get back $$$mex(L)$$$.

But what if you do provide $$$mex(L)$$$ to fill in the gap? You'll get back the second missing element.

Hence, a list can only improve your answer equal to the second missing element. Hence, the answer is the maximum of the second missing element from each list.

But what if you are only allowed to use one list at most once. Then, you can think of it as a neural network, where the output of one layer is the input of the other layer. Then, create a directed graph where each list contributes on edge $$$m \rightarrow sm$$$, i.e, it is a neural network that takes in a missing element and outputs the second missing element.

Notice that this would be a DAG since edges are from small to large. Then, define $$$indp[u]$$$ to be the max vertex reachable when you start at vertex $$$u$$$. Clearly, $$$indp[u] = max(indp[child])$$$.

Also, define $$$outdp[u]$$$ to be the max vertex reachable when you don't start at $$$u$$$, However, using one operation, you can get the opportunity of starting at $$$u$$$, therefore, if there are more than one outdoing edge, then $$$outdp[u] = indp[u]$$$.

Then, $$$f(u) = max(indp[u], outdp[*])$$$ where $$$*$$$ is everything except $$$u$$$.