This is great. So much cleaner than the binary-search + prefix/suffix solution I implemented.

https://codeforces.me/contest/1976/submission/264856786

Here's a neat little solution for F, I observed that all points on the circle perimeter are touching one another, so we can just "trace" the circle and bfs every point within the correct distance. Very easy solution when you do it this way.

void solve(){
    int r;
    cin >> r;
    map<array<int, 2>, int> vis;
    queue<ai> q;
    q.push({0, r});
    int ans = 0;
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        if (vis[{i, j}]++) continue;
        int sq = sqrt(i*i+j*j);
        ans += (r <= sq && sq < r+1);
        for (int a = -1; a <= 1; a++) {
            for (int b = -1; b <= 1; b++) {
                int new_sq = sqrt((i+a)*(i+a) + (j+b)*(j+b));
                if (new_sq >= r && new_sq < r+1) q.push({i+a, j+b});
            }
        }
    }
    cout << ans << endl;
}

Consider you are trying to add 20 to one of your arrays. Array a.back() is 50, and array b.back() is 30. It is better to add 20 to the back of array b because the 50 may be more useful in the future.

No, you could just greedily decide whether to put the ith element in set a or b.

A lucky streak or the road to CM? :) https://codeforces.me/profile/tn757

.

G2 is great.

https://codeforces.me/blog/entry/70237

I did a lot of drawings of the sample cases, and observed that a good strategy seemed to be greedily pairing the employees at deepest depth with the deepest available employee. So we go through the employees from deepest to highest, always pairing the employee with the deepest available employee. Two employees at the same depth are always compatible, and we know that an employee at a higher depth is compatible as long as there is more than 1 employee at that higher depth, so we keep track of all depths with more than 1 available employee.

F was an interesting problem for me... still not sure how to approach it but came up with this proof-by-AC solution lol

typedef array<int, 2> ai;
void solve(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n+5);
    for (int i = 2; i <= n; i++) {
        int sup;
        cin >> sup;
        adj[sup].push_back(i);
        adj[i].push_back(sup);
    }
    queue<ai> q;
    q.push({1, 0});
    map<int, int> mp;
    map<int, int> vis;
    while(!q.empty()) {
        auto temp = q.front();
        q.pop();
        if(vis[temp[0]]++) continue;
        mp[temp[1]]++;
        for(auto i : adj[temp[0]]) q.push({i, temp[1]+1});
    }
    int ans = 0;
    priority_queue<int> pq;
    set<int, greater<int>> ok;
    for (int i = 0; i < n; i++) {
        if(mp[i] > 1) ok.insert(i);
    }
    for (auto i : mp) {
        pq.push(i.first);
    }
    while (!pq.empty()) {
        auto temp = pq.top();
        pq.pop();
        ans += mp[temp]/2;
        mp[temp] %= 2;
        ok.erase(temp);
        if (mp[temp] && ok.size()) {
            auto it = ok.begin();
            ans++;
            mp[*it]--;
            if(mp[*it] <= 1) ok.erase(*it);
        }
    }
    cout << ans << endl;
}

2^n is greater than the summation of 1+2+4+8+...2^n-1 so you can be greedy about using your smaller powers because they can never contribute to be a bigger one

Does problem A remind anyone of king opposition in chess? Wish I solved it during contest.

Almost got hacked for C, my first submission was just using ints to keep track of the penalty which passed pretests. But then I remembered getting hacked for problems with calculations in the 100000^2 range and resubmitted with long longs shortly after.

I had this issue too,

for (int i = b; i !=a; i=par[i])
{ 
    if(i<=M)ans.push_back(i);
}

is terminating incorrectly for you, I would reexamine the part of the code that deals with this and find where your infinite loop is occurring

I'm not really sure, I just observed that any component with edges equal to vertices must be counted. So I just used DFS and added the size of the adjacency list of each node visited then divided by 2 to check if edges equaled vertices visited.

I feel like E was more classic, I thought of the solution almost instantly due to studying some USACO this year. Granted I only had 20 minutes for F and I believe I saw the idea, but I couldn't put together a solution for it in time.

Another way is to count the number of components where the number of edges is equal to the number of vertices. I noticed the pattern quickly because it felt similar to a USACO silver problem I had seen before.

For permutations starting with the max number, you can generate all possible arrays starting with max-1 in n^2 time. For permutations not starting with the max, you can generate all possible arrays starting with the max in n^2 time. Then just sort all the arrays you generated.

Hm, my initial idea was to sort the array and binary search the greatest possible value that could be included and then add how many ways you could choose m-2 numbers from the set of numbers between the first number and the greater number to the asnwer.

Same, I really tried to force an O(n) with casework until I just gave up and bruteforced every array starting with the best possible number.

I did a simple DFS + handshaking lemma to make for easy counting

Really good contest to return to Codeforces after a month of exams! Looks like it will also take me back to specialist :) I didn't have time to do F, was it some nCr + binary search?

Just realized that's why my solution passed so quickly, my loop started at 1 which was always an answer lol.

:clown: I was in the first 60 solves for C and had 0 penalties then took 2h for A and B with 4 penalties

What was the intended solution for div2A? I couldn't think of anything and figured brute force would probably result in around sqrt(n) complexity by brute forcing until I find an I such that gcd(x-1, abs(y-i)) = 1. This ended up working for me.

I think C was a little pretty, I didn't like B though.

Congratulations to YocyCraft for becoming GM after this round, assuming you pass system tests!

My idea for B was to make sqrt n blocks of size sqrt n, then find the block with the minimum cost. Then I checked that block and its left and right adjacent blocks. Does this capture the idea of sqrt decomposition? This is the first problem I've tried it on.

I think it's funny my first sqrt decomposition solution was for a problem B. Not sure if it's correct though or testcases are just weak. The problems were interesting, maybe just a little unbalanced. Shame this round had so many technical difficulties.

Question, when a problem has an easy and hard version with scores of (1500 + 2000), does that mean the easy version of the problem is about as hard as a problem worth 1500 points and the hard version is about as hard as a problem worth 3500 points? Or is there no correlation?

Good round! Sadly I ran out of time for D and I think I would have been able to solve with ~10 more minutes.

Will a scoring distribution be announced?

I thought competitive programming was interesting so I tried to participate in Leetcode and Codeforces contests. Leetcode had a lower barrier of entry for me, so I spent a month doing medium DP Leetcode problems then a month doing medium graph problems. These first 2 months were a struggle but I began to improve after that and now I just participate in contests and upsolve when I have time. Also I had no math/programming background as I am still in highschool.

Thanks

Think about the case like:

4

6

2

We can't discern between the 6 and 2 because they give the expected value of 8. So we need to take the sum of all numbers higher than the value ahead of it and also the sum of all numbers lower than the value ahead of it. We can solve this problem by sorting so that there are no lower numbers in front of it.

Hint: I solved it by sorting each column and using prefix sums

This contest was held at 4 am for my timezone, I tried using segment tree for A and fenwick tree for B before I came to my senses xD

Thank you.

My code works for that case, here it is if you want to take a look at it, I'd appreciate it if you could find a counter case

#include <bits/stdc++.h>
using namespace std;
ifstream fin("in");
ofstream fout("out");

// #define cin fin
// #define cout fout
int main(){
    string s;
    cin >> s;
    long long n = s.length();
    string e = "bessie";
    long long j = 5;
    long long cnt = 0;
    long long ans = 0;
    long long cnt2 = 0;
    long long brute = 0;
    set<long long> lb, le, ls, li;
    long long lastCnt = 0;
    for(long long i = s.length()-1; i >= 0; i--){
        if(s[i] == 'b') lb.insert(i);
        if(s[i] == 'e') le.insert(i);
        if(s[i] == 's') ls.insert(i);
        if(s[i] == 'i') li.insert(i);
        if(s[i] == e[j]){
            j--;
            if(j==-1){
                j = 5;
                long long last = *le.lower_bound(i);
                last = *ls.lower_bound(last);
                last = *ls.lower_bound(last+1LL);
                last = *li.lower_bound(last);
                last = *le.lower_bound(last);
                lastCnt = cnt;
                cnt += n-last;
                
            }
        }
        if(s[i] == 'b'){
            bool ok = true;
            long long last = n;
            auto it = le.lower_bound(i);
            if(it!=le.end()) last = *it;
            else ok = false;
            it = ls.lower_bound(last);
            if(it!=ls.end()) last = *it;
            else ok = false;
            it = ls.lower_bound(last+1);
            if(it!=ls.end()) last = *it;
            else ok = false;
            it = li.lower_bound(last);
            if(it!=li.end()) last = *it;
            else ok = false;
            it = le.lower_bound(last);
            if(it!=le.end()) last = *it;
            else ok = false;
            if(ok){
                cnt = lastCnt;
                cnt += n-last;
            }

            
        }
        ans += cnt;
    }
    // int k = 0;
    // for(int i = 0; i < s.length(); i++){
    //     k = 0;
    //     cnt = 0;
    //     for(int j = i; j < s.length(); j++){
    //         if(s[j] == e[k]){
    //             k++;
    //             if(k == 6){
    //                 cnt++;
    //                 k = 0;
    //             }
    //         }
    //         brute += cnt;
    //     }
    // }
    cout << ans;
    // cout << endl << brute << endl;
}

I was almost sure it was integer overflow, but I made sure everything was a long long so many times.

I only binary searched to the nearest bessie completion. Then I added n-(last index) to my running count. So I only did 5 binary searches per index, so it would be n log n. I couldn't prove this to be correct, but like I said I tried a bunch of random strings and it matched the brute force every time.

I tried to do some binary search from each 'b' to the next index of the next 'e' to next index of the next 's', 's', 'i', 'e'... for silver P3 and only passed the n<4000 cases. I wrote a brute forcer to check my binary search algorithm and couldn't find a countercase to it the entire time. Did anyone AC it with a similar approach?

Expect to score 650 points. Maybe I will have a 3% chance of promotion? :')

Very cool. Wish I had thought of that.

Can anyone explain how they quickly proved D? I thought about the correct greedy solution but couldn't prove it.

Opposite, couldn't solve D but got the idea for C fairly quickly

Who else facepalmed when they saw the announcement reminding the condition that the price tags have to be continuous?

Does anyone know if the Chinese servers also went down? I know Leetcode CN is separated from Leetcode but is still accounted for in ratings.

I thought it was tree rerooting + bfs, couldn't figure it out in time though.

I just memoized all states using DFS. If we are at a position and it is a 1, we can either continue or delete it and incur the cost. There is a third option of swapping with the number in front of it if it is a 0 and we have no other 1's to the left. If we are at a position and it is a 0, we can delete it and incur the cost. If there are no 1's the left, we can either continue or swap it with the number in front of it. The memoization will look like memo[pos][has_0][swapped] for each state

Can someone help me prove my solution for C? I thought my solution was an elegant linear time solution but it did rely on one claim I was only probably sure was true. My claim was that: for any number 0 <= k <= n*(n+1)/2, and with access to the numbers 1...n, we can always greedily choose the largest n that fits and add it to the sum until we reach k. If this claim is true, then we can solve C using the following strategy:

Initialize an array of length n, all 0s

If we "set" index i of the array, then it will create n-i positive subarrays. We set the largest indices that fit into the sum of k.

Now we iterate through the array backwards and set the values such that the set indices make every subarray ahead of them positive and the unset indices make every subarray ahead of them negative.

Solution: 198783142

I didn't prove that we can always make k greedily using the numbers 1...n, but I thought it might be true because it felt similar to the Div 4 G problem.

Thanks, this is a lot cleaner

I don't think anyone solved D with an uglier DP solution than mine. 198822901

Agreed, I drew a square pattern on a piece of paper, brute forced the answer to n = 9, then decided to take a guess and output sqrt(n-1).

Thanks, this sounds much easier

Output sqrt(n-1)

I used standard dp with memoization for: position, whether there was a previous 1 in the array, and whether we swapped

Can someone teach me or refer me to a resource where I can learn to make my DP not ugly? I learned DP on Leetcode and for multidimensional DP I will do something like:

int dp[MAX_N][b][c][d] = {};

memset(dp, -1, sizeof dp);

But this doesn't work on Codeforces because testcases may be <= 1e5 and initializing the DP array for this many testcases results in TLE. So on Codeforces like this contest's problem D I ended up using:

vector<vector<vector<vector<vector>>>> memo(s.length(), vector<vector<vector<vector>>>(2, vector<vector<vector>>(2, vector<vector>(2, vector(2, -1)))));

But surely there's a better way to do this, right?

I received 10 penalties because I set INF to 1e16 for problem D. Feel free to laugh :') https://imgur.com/a/F5VcnwL

Is there any optimization for the odd case? Or is it just [0, 0, 0, 0...]?

I couldn't even solve the subtask for C, generating any array that satisfies the condition, let alone a minimum distance one. All I could think of was an array of all 0's.

If I were to guess it is some weird floating point precision error? This code works as expected

#include <bits/stdc++.h>
using namespace std;
 
long long inf = (long long)1e18+1;

int main() {
    cout << inf << '\n';
}

I think it should be legal. From my experience, I think the solving strength of ChatGPT is <1100, and to use it for harder problems requires you to know what you're doing. For example, I could maybe coax it to solve a 1600 rated problem, but at that point I would have to know the main idea of the problem already. It wouldn't be very useful to me for 2000+ rated problems.

I reached max penalty for B and wrote random code until I saw green.

A's problem statement was deceptively simple, I thought there should be a two liner solution but I couldn't find one. However, I think I did come up with an elegant sorting solution for A:

void solve(){
    int n;
    cin >> n;
    vector<string> v;
    for(int i = 0; i < 2*n-2; i++){
        string temp = "";
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end(), [] (string& a, string& b){return a.length()<b.length();});
    bool ok = true;
    for(int i = 0; i < v.size()-1; i+=2){
        reverse(v[i+1].begin(), v[i+1].end());
        if(v[i] != v[i+1]) ok = false;
        
    }
    if(ok) cout << "YES" << endl;
    else cout << "NO" << endl;
}

A was unique for a problem A. I actually solved C faster than A and B, so I thought C was cute. B made me want to pull my hair out. I basically reached the maximum penalty then bashed it until I saw AC.

Your second if statement seemed dubious to me. The || s[n-1] == 'w' isn't evaluated in the order you think it is. I recommend using parentheses when using && and || in the same if statement. Fixed solution: 195885580

Probably due to undefined behavior which is present in your code. You should replace while(s[i] == arr[cur]) with while(i<s.length() && s[i] == arr[cur]). Also, your cur variable can go past 3, so you are accessing index 4 of {'m', 'e', 'o', 'w'} which is undefined. Fixing these undefined behavior lets the code pass in C++ 17. Why it passes when you delete the map? We can't ever know for sure, undefined behavior doesn't guarantee the code will be wrong, it just means it might not work as expected sometimes.

Fixed code with map included that passes in C++ 17: 195846468

Looks like this would have been my expert round had I not made a stupid error and got a penalty for overflow on problem C. Still, I won't cry about +100 delta :)

Failed System Test

Amazing, I have never seen so many FST on a problem A

You are iterating through the frequency map with a for auto loop. When you check for a key that doesn't exist, it is created with a default value of 0. But creating a key while iterating through the map with a for loop is undefined behavior.

I also thought it seemed similar to the classic number of swaps to sort problem. I wasn't completely sure so I wrote a casework solution instead but cool to see it works!

Yes, that was my concern too. But since we don't have to return the order of the picks, then we just need to prove that some optimal picking order exists such that you can use all of the max values before the 0s. I didn't prove it, but I didn't see why some optimal picking order shouldn't exist which implies the priority queue sum is optimal.

Wow, our ideas were really similar!

My casework solution for E1 lol, it actually helped me realize the general solution for E2 and only needed a few tweaks.

void solve(){
    int n, k;
    cin >> n >> k;
    string a, b;
    cin >> a >> b;
    string x = a, y = b;
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    if(x != y){
        cout << "NO" << endl;
        return;
    }
    if(a == b){
        cout << "YES" << endl;
        return;
    }
    if(a.length() >= 6){
        cout << "YES" << endl;
        return;
    }
    if(a.length() <= 3){
        cout << "NO" << endl;
        return;
    }
    if(a.length() == 4){
        swap(a[0], a[3]);
        if(a == b) cout << "YES" << endl;
        else cout << "NO" << endl;
        return;
    }
    if(a.length() == 5){
        if(a[2] == b[2]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

A great Div 3 as always. My best ever contest performance.

A: Pretty trivial, just remove duplicates

B: Process all the good pairs, then for letters with >= 2 occurrences use a k to make them good.

C: Standard priority queue, I took a risk and didn't prove it however. (also got a penalty because I forgot to use long long >.<)

D: Another solution I didn't prove, but I used memoization and checking for !memo[i][s[i]+2] to increment answer

E: I did casework for the easy version, then generalized it for the hard version.

Sorry that happened to you. I've seen many more false bans on Leetcode than on Codeforces. I'm pretty sure the bans need manual approval though, so I always comment in the source of my template if I found it online for programming competitions now.

I thought D looked easier than C, but I only had 8 minutes to read it :(

How did you plan to use a segment tree with constraints <= 1e9?

C was an insightful problem for me. I thought at first I would need some complicated range query data structure but then I remembered being amazed that 1791F - Range Update Point Query could be solved with just a std::set. So I drew inspiration from that problem and decided to simplify my ideas and came up with a neat priority queue solution.

void solve(){
    int n;
    cin >> n;
    vector<long long> v(n, 0);
    for(int i = 0; i < n; i++) cin >> v[i];
    vector<long long> t(n, 0);
    for(int i = 0; i < n; i++) cin >> t[i];
    vector<long long> ans;
    long long sum = 0;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for(int i = 0; i < n; i++){
        long long len = pq.size();
        long long res = t[i]*(len);
        res += min(t[i], v[i]);
        while(pq.size() && pq.top() < sum+t[i]) {
            res -= min(t[i], sum+t[i]-pq.top());
            pq.pop();
        }
        ans.push_back(res);
        pq.push(v[i]+sum);
        sum += t[i];
    }
    for(auto i : ans) cout << i << " "; cout << endl;
}

I did the case work on paper: let mx be the most multiples of (m+1) that we can buy without overbuying. Then the answer is the minimum of {n*b, (mx+1)*(a*m), (a*m*mx)+(n-(m+1)*mx)). I wish my binary search solution worked so I could have solved it earlier.

if(predicted_delta < 0) cout << "I think it should be unrated.";

else cout << "I think it should be rated.";

I used two pointers -- while(l < r && flag), flag = false, if a[l] or a[r] = min or max, increment l or decrement r, increment min or decrement max, and set flag to true. Then output l and r as the answer,

I couldn't figure that out, I just had a counter and incremented it by 1 every time I outputted a number lol

I didn't prove it, but I solved it in a few minutes by greedily going max_sum, max_sum-1, max_sum-2... min_sum, min_sum+1, min_sum+2.. max_sum-1. I was surprised it worked.

A funnily embarassing contest for me -- A >> B > C for me. I solved the problems in the order C, B, A and got 5 WA on A before getting it. My math solution had a bug I couldn't find, so I tried to binary search the amount potatoes to buy for 'a' coins, which obviously didn't work. Then I thought the function was unimodal, so I tried ternary search on the potatoes, which still didn't work! Finally, I decided to scrap my mess of a code and prove a solution on paper and then implement it. It was less stressful after the 4th WA anyways, since I already hit the maximum penalty for a problem... Finally I solved Problem A, 76 minutes into the contest! I am proud of my persistence and disgusted at my stupidity.

Put all negative integers into an array. Greedily choose all positive integers. Sort negative array by least value. Greedily choose minimum negative integer until you can't anymore.

In my opinion expert is attainable with some speed and being comfortable with applying these algorithms:

DFS

BFS

DSU

Binary Search

Memo DP

Sieve

Binary Exponentiation / Inv Mod

Prime Factorization

Thanks, I realized that a little after posting the comment

Thanks for the help, I realized my error.

Thanks, I overlooked that even if there is a cake that ends at position 5.0 and a cake that begins at position 6.0, there is still a gap because positoins 5.1 — 5.9 are empty. I wrongly assumed they would be contiguous.

Actually, I am wrong. The interval [1,5] ends at 5.0 and the interval [6, 10] begins at 6.0. So there is a gap at 5.1 to 5.9. Thank you!

Can't side-by-side cakes allow a dispenser to cover 2 cakes? If the width of cakes were 2, and there were cakes at positions 3 and 8, then the intervals [1, 5] and [6, 10] are covered. 3+2 < 8-2

Doesn't the cake at position 3 span from [0, 6] and the cake at position 10 span from [7, 13]? So if the dispenser is center at position 7, it should cover [6, 8] which is within both intervals?

Can someone explain this testcase for div2 b to me?

1

3 3 1

3 10 25

7 23 27

The correct answer is NO but aren't all cakes getting chocolate and none is spilling over? The dispenser at position 7 gives chocolate to the cakes at position 3 and position 10 and the dispensers at 23 and 27 give chocolate to the cake at position 25.

I forgot the unusual start time, I guess this will be a no-sleep-forces round for me :')

I noticed this too, my C passed main tests with 500 ms but now barely squeaks by with 1950 ms.

Very cool that F can be solved with set and DSU. I got stuck on BIT implementation because I don't have a template for it and have only solved a few CSES problems using it. Forgot about the limitation of 3 change operations. Thought G2 would be DP, but the binary search solution is quite elegant. 10/10 problemset overall.

Very cool that F can be solved with set and DSU. I got stuck on BIT implementation because I don't have a template for it and have only solved a few CSES problems using it. Forgot about the limitation of 3 change operations. Thought G2 would be DP, but the binary search solution is quite elegant. 10/10 problemset overall.