Great. Contest are rare lately. Is it because of ICPC on the platform?

As a participant, I will appreciate the work of authors and testers. Thank you for the contest!

Thanks for the contest!!. That's my 2nd educational round. Let Go!!

Hope for stable servers.

Feeling like after 1 year I will participate in a CF Contest. These days contests are rare.

My first educational round since 3 months ago. Will I be able to solve 4 problems?

glhf!

You better not leave the rating like last time.

Hoping to learn new techniques and methods regardless of rating changes.

MUDA MUDA MUDA MUDA

I have 192 points to candidate master, hope to get more rating points tonight.

I hope that I can get more ratings this round.

If you hack someone you will get points?

Is the site getting hanged due to DDoS?

This is the closest I've been to being an expert XD

Solved A-E. Problem F has simple O(n*m) solution but I don't know how to optimize it.

A: Each '?' provides 10 options except the '?' at the beginning of the string, which provides 9 options. Also the first char of string cannot be '0'.

B: Because a!=a', we can find the minimum index L and maximum index R that a and a' differ at that position. Then the answer must contains [L, R]. To find the longest possible subarray, we need to extend [L, R] to left and right while a' is non-decreasing on this range.

C: Consider for all possible selection of remained character. Let c be the remained char, we can find all maximal blocks without c, and consider them seperately. For each block, let it's size be L, then we need 1+floor(log(L)) to remove it, and the answer depends on the maximum size of blocks.

D: Let r be the furthest cell we move to, and t be the number of segments we used, then the cost is r+2t. If we ignore a segment [l, r](and possibly make t decreased by 1), we will make r be increased by at least r-l+1, so we can assume that only segment with size 1 is ignored. Then for each possible segment which could contain the furthest cell, we calculate the number of 1-size segments before it, and the number of cells we can ignore (which is (sum of size of segments) — k), then we know there are how many segments we can ignore if we stop in this segment.

E: If we always remove the most right valid pair of brackets, we can see that the cost is the sum of depth of each pair of brackets, which means if we let '(' be 1 and ')' be -1, and s[i] be the array of prefix-sum, the cost is sum(str[i]==')')(s[i]) (the sum of prefix-sums at positions of right brackets). Therefore, we can see how to reduce the cost: If we move a right bracket from i to the right of j (j<i), we make s[i] on range [j+1, i-1] be reduced by 1, and changed s[i] to s[j]-1. If we move a left bracket from i to the right of j (j>i), we make s[i] on range [i+1, j] be reduced by 1. Also these moves must remain s[i]>=0 for all i. Therefore, we can consider for every possible i and find the optimal j by range minimum query and binary search, then we solved the problem for k=1. For k>1, I used greedy approach (which means simply solve the k=1 version for k times) and it passed the pretest (however I can't prove it).

What was D ? fully ruin my contest -_-

Very good string problem for C. I like it.

F was cool, thanks!

Maybe my solution for problem E is incorrect, but I don't understand why $$$k\leq 5$$$

Misread E for about 20mins(because of my poor English carelessness,I thought I could choose "some brackets"),and tried to solve F by dp with data structures but failed.So I missed a great chance to enter the top 10 in rated contestants.Sad :(

So could someone teach me how to solve F? thx >-<

For F, I manage to solve it except for this one part:

How to find the number of m-tuples that add up to n such that at least j numbers is greater than k? Find this for all j from 0 to m.

With this, you can change the question to how many different ways to place the empty space, then depending on the number of regions of empty space > k, you multiply some power of 2. (Fix the tree to always fall left if possible).

problem E completely ruins the problemset. 400ish solves wtf.. I have never seen that much solves for E, especially in educational rounds.

If I pass the system tests, I will become expert today for the first time

Weak pretests in D

Could someone help with my submission for D?

202882450

Screencast with commentary

Who is author of problem C and who specifically prepared the samples?

E is a nice problem: cost of the brackets can be interpreted as the area under the graph of prefix sum of the sequence :) (1/2 (Area - n/2) to be precise)

Problem D:
Getting WA on TestCase 2
Suggest some counter Case. Unable to figure out the mistake.

is D just greedily skipping and picking segments T-T

https://mirror.codeforces.com/contest/1821/submission/202880565
can any help to find my mistakes or find any anti test. (: its differ on 1215th on test-2.. -_-

Can anyone please give me a counter example for my submission for problem D.

UPD: Aced with Greedy. Thank you everyone for the help. (adityagamer thanks for test case).

What's the issue with this more general solution for D that doesn't explicitly use the special len=1 case but should still take it into account?

I liked D, nice problem

Am I the only one who solved D with sqrt decomposition+ greedy :d I figured there would be an easier solution but sqrt seemed fun :d

Can someone give me a counter test to this submission for problem D? Thanks in advance.

Can anyone share a dp solution for D?

Can anyone tell me what is wrong with my C https://mirror.codeforces.com/contest/1821/submission/202883081 am using same approach as in editorial and is running fine for every case i can think of

how to solve C?

In problem D, can anyone please explain why the correct output of this case is 22 but not 23?

1
4 10
1 4 9 15
1 6 13 19

Can someone explain why this approach fails for problem D. I am just trying to minimse the number of segments that needs to be taken by removing the segments with lowest differences. Link to submission Thank you in advance.

void solve()
{
    ll n , k , available = 0;
    cin >> n >> k;
    vector<vector<ll>> vt(n+1 , vector<ll>(2));
    for(ll i = 1; i <= n; i++) cin >> vt[i][0];
    for(ll i = 1; i <= n; i++) 
    {
        cin >> vt[i][1];
        available+=(vt[i][1]-vt[i][0]+1);
    }
    sort(vt.begin(), vt.end());

    if(available < k)
    {
        cout << -1 << endl;
        return;
    }

    ll previous = 0 , ans = mx , curr;
    vector<ll> aux(n+1 , 0);
    for(ll i = 1;i<=n;i++) aux[i] = aux[i-1]+(vt[i][1]-vt[i][0]+1);
    for(ll i = 1;i<=n;i++)
    {
        ll idx = upper_bound(aux.begin() , aux.end() , k+previous) - aux.begin();
        if(aux[idx-1] >= k+previous)
        {
            curr = vt[idx-1][1];
            curr += 2*(idx-i);
            ans = min(ans , curr);
        }
        
        if(idx <= n)
        {
            curr = 2*(idx-i+1);
            curr += vt[idx][0] + (k+previous-aux[idx-1]-1);
            ans = min(ans , curr);
        }
        previous = aux[i];
    }

    cout << ans << endl;
}

this is my solution for problem D. Plz somebody explain what is wrong with this approach.