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://codeforces.net/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://codeforces.net/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.

Nice contest! You can find the video editorial for Problem A, Problem B, Problem C and Problem D here- here

Maybe this sounds like a stupid question, but why are div 1 users included in the official standings?

Can anyone please explain why this code gives RE in GNU C++20 202863602, but AC in Clang++20 202892668.

Later I changed vector<pair<int, int>> v to vector v which stores only differences and it gave AC on GNU too, but I don't see a reason why this would give RE.

Can someone pls explain how the expected output for this input is 11?

1
3 4
1 4 6
2 4 7

Can someone please prove or hack my solution to problem E which I did in O(n)?

Approach: Find pairing between individual brackets. For example in (()) first bracket is paired with fourth and the second with third. Find this using stack. Simply eliminate the top-k pairs of brackets where pairs are farthest apart. The answer is the cost of the resultant string.

What's up with the server?

Can someone explain to me why greedy with min-priority-queue works for problem D? Having a hard time grasping it.

Can anybody tell what's wrong with my code and on which testcase it is failing. https://codeforces.net/contest/1821/submission/202836388

for problem b

14

3 4 2 1 4 5 2 1 8 7 6 5 4 3

1 2 3 4 4 5 2 1 3 4 5 6 7 8

the output is 1 14 it should be 8 14 right I am unable to understand the question can someone please help

Registed 6 years ago， and become master finally. And still huge gap to grandmaster. Cheer for myself.

Can someone help me with C, I am getting TLE in test case 8. My submission

During the contest I got AC for this code: https://codeforces.net/contest/1821/submission/202855933

While not optimised, I believed that it was sufficient to pass the time limits (I had ~700ms runtime), so I did not optimise it further.

After the contest it got TLE due to high constant factor of using set()

I changed the code and now it works: https://codeforces.net/contest/1821/submission/202930258

It is pretty unfortunate as I really thought that my original solution was optimised enough for the testcases, how could I tell if I should always optimise my code beforehand? Should I always optimise my code even if it passes the pre-tests?

thank you

Does E problem's "extract" mean for one time I can take a pair of matching braclets "(......)" ? If take ONE braclet each time how can I pass the example?

can we use DP to solve D.

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
 
#define all(x) x.begin(), x.end()
#define nl cout<<"\n"
#define ar  array
#define PRECISION 9
#define fast_IO ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define clock() cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

#ifdef LOCAL
#include "../Library/debug.h"
#else 
#define dbg(...) "OM BHOLE"
#endif

#define int long long

const int mxN = 2e5+57;
ll dp[mxN][2];
int n, k;
ll go(int i, int ch, ll t, vector<ar<int,2>> &a, ll s){
    // dbg(i, ch, t, s);
    if(t >= k){
        return a[i-1][0] + s + 1 - 1;
    }
    if(i == (int)a.size()){
        if(t < k){
            return 1e18;
        }
        return a[i-1][0] + s + 1 - 1;
    }
    if(dp[i][ch] == -1){
        ll ans = 1e18;
        ll need = k - t;
        ll can = a[i][1] - a[i][0] + 1;
        ll ns = min(need, can);
        if(ch == 0){
            ans = min(ans, go(i+1, 1, t + a[i][1]-a[i][0] + 1, a, ns) + 1);
            ans = min(ans, go(i+1, 0, t, a, s));
        }
        else{
            ans = min(ans, go(i+1, 1, t + a[i][1]-a[i][0] + 1, a, ns) + 1 + 1);
            ans = min(ans, go(i+1, 0, t, a, s) + 1);
        }
        dp[i][ch] = ans;
    }
    return dp[i][ch];
}

void solve(){
    cin >> n >> k;
    vector<ar<int,2>> a(n);
    ll sum = 0;
    for(int j = 0; j < 2; j++){
        for(int i = 0; i < n; i++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        sum += (a[i][1] - a[i][0] + 1);
    }
    if(sum < k){
        cout << -1 << "\n";
        return;
    }
    sort(all(a));
    vector<ar<int,2>> b;
    int l = a[0][0], r = a[0][1];
    for(int i = 1; i < n; i++){
        if(a[i][0] > r+1){
            b.push_back({l,r});
            l = a[i][0];
            r = a[i][1];
        }
        else{
            r = a[i][1];
        }
    }
    b.push_back({l, r});
    // dbg(b);
    ll ans = 2e18;
    for(int i = 0; i < 2; i++){
        for(int j = 0; j <= n+10; j++){
            for(int k = 0; k < 2; k++){
                dp[j][k] = -1;
            }
        }
        ll need = k;
        ll can = b[0][1] - b[0][0] + 1;
        ll ns = min(need, can);
        if(i) ans = min(ans, go(1, 1, b[0][1] - b[0][0] + 1, b, ns) + 1);
        else ans = min(ans, go(1, 0, 0, b, 0));
    }
    if(ans == (ll)1e18){
        cout << -1 << "\n";
    }
    else cout << ans << "\n";
}


signed main(){
    if (0) cout<<fixed<<setprecision(PRECISION);
    fast_IO;
    int T=1;
    cin>>T;
    while(T--){
        solve();
        clock();
    }
    return 0;
}

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

Why hasn't the tutorial been released yet?

Wondering solution of D by using binary search

hey in E why k is only till 5 is it too confuse us? or make implementation easier?