Vladosiya orz

only purple and yellow testing?

Me waiting to get a minus again lol .... I dont know why i underperform div 3 and div 4 . Anyways can some one tell me any practice method to master div 2 D , i hardly able to solve them within 3 hrs in practice session .

Expect to solve at least 4

Hope to solve at least 5 and get 1250+ rating

UPD: Solved ABCDE

I wish I can AK this round >_<

Hopefully I will reach expert in this round... :)__

I am waiting for the tester to comment on this blog.

More people created problems than tested them :O

hope to reach pupil in this contest :D

No one for testing CYAN :(

I hope this contest to be cheating free.

last contest before school starts :(

welcome a new -100 in rate (¬_¬)

welcome a new -100 (¬_¬)

Wish I can get Expert on this contest!

lol guys you probably need some more testers)

contest no.2000!

don't know but the performance in div 2 is better than div 3, hope to reach expert in this div 3

Potato potato

hope for Asuna_Yuuki

As a participant, DangKhoizzzz orz__

OMG! Another Vladosiya round !

wapis blue banna hai mujhe.. (hopefully)

Hoping to break the 1400 barrier and becoming specialist this contest! Wishing everyone goodluck!

2000th Contest! It seems that Goodbye 2024 can't be contest No.2024......

As a tester, I wish you would enjoy the contest

I will full solve this round, ggez

Let's make the "As I am not a Tester .. " comment common.

Satyam is definitely not blue testing, lmao

satyam343 should not be allowed to do BLUE testing.

He is fake blue, he is actually Red.

That's like Donald Trump representing Poor of America.

It's better find another blue tester , satyam343 is actually red

Contest #2000 on Codeforces! What a milestone

Hope to solve 5 problems today. Good luck everyone!

I hope through this game, I can reach the Specialist

2000th CF Contest yay. Would be great if i somehow manage to become specialist.

Hope to reach 1300+ rating in this round

Here we go to Chess.com :D

Thousands of submissions for E in the last 20 minutes wow

Great contest! Good problems for a div 3

why am I reading the comments instead of solving E o.O

I still have 20 minutes left

stuck at F for an hour :) . Also 600 submissions on F in last 12 minutes? Yeah seems legit

Great Contest though , enjoyed :)

Well this round feels like true Div 3.
Good balanced contest.

Nice contest, but cheaters ruined it again

I can't find any counter example for my submission in D : 276247102

Whosoever tranlated the problem statement or created it, better don't please. E was awful like awful!

Got H last minute, phew. Feeling a little bit lucky.

Finally I solved 4 problems

H : Ksyusha and the Loaded Set can be solved using the tricks introduced in problem G: Penacony from last Div 3 Round. I talk more about the trick and the data structures used in this video

Define $$$dp[x]$$$ to be the longest streak of missing numbers starting at $$$x$$$. If a number is present in the set, you set $$$dp[x]$$$ to $$$0$$$. Otherwise, $$$dp[x] = 1 + dp[x + 1]$$$. Hence, you can populate this DP right to left after reading the initial numbers.

To answer any query, you just need to find the first $$$x$$$ such that $$$dp[x] \geq k$$$.

When you add an element, you need to refresh the DP table to the left of $$$x$$$. You can iterate over each element, and check if $$$dp[i] > |x - i|$$$. If it is, you need to subtract $$$dp[x]$$$ from all such $$$i$$$. Finally, set $$$dp[x] = 0$$$.

When you remove an element, you again need to refresh the DP table to the left of $$$x$$$. You set $$$dp[x] = dp[x + 1]$$$. Then, for each element to the left, check if $$$x$$$ was a bottleneck for the streak, i.e, if $$$dp[i] == |x - i|$$$. If it is, you increment $$$dp[i]$$$ by $$$dp[x]$$$.

Code for $$$O(N^2)$$$.

Now, to optimize it to $$$\mathcal{O}(n \cdot log^2(n))$$$, we need to figure out how to refresh the DP table efficiently. First, notice that $$$dp$$$ values of missing streak would decrease by 1 each step until it falls to 0 and then it starts at a big number and keeps falling. Hence, in type 1 and type 2 queries, when we say that we need to refresh the DP table to the left, we only have to refresh the elements after the last $$$0$$$. Hence, we need a data structure that can efficiently :

1. Find out the location of the last zero.
2. Add a delta in a range.
3. Query maxima

Sadly, no such data structures exist. But we faced this same issue in G: Penacony from last Div 3 Round. Notice that 0 is always a minima. Hence, we can binary search on the left, and keep discarding one half of the range if the minima of that range is 0. Hence, a lazy segment tree from Atcoder Library suffices, usage of which I have discussed in the video above.

Any hints on F?

Will greedy not work on F (greedily sort by a*b) ? Or if it works do we need to handle last rectangle case differently?

F: Thought greedy at first, but sample proved otherwise. Realized K was extremely small, and it's obvious that the answer will be deterministic from pos, k. Then just DP on that, taking the smaller of the rows or columns when you decrement k for each rectangle.

int dp[1001][101] = {};
int dfs(int pos, int k, vector<ai>& v) {
    if(pos>=v.size()) {
        if(k==0) return 0;
        return 1e9;
    }
    if(dp[pos][k] != -1) return dp[pos][k];
    int ans = dfs(pos+1,k,v);
    int cur = 0;
    int a = v[pos][0], b = v[pos][1];
    for (int i = 0; i < k; i++) {
        bool ok  = false;
        if(a<=b && a >= 0 && b) {
            cur += a;
            b--;
            ok = true;
        }
        else if (b<=a && b >= 0 && a) {
            cur += b;
            a--;
            ok = true;
        }
        if(ok) ans = min(ans,dfs(pos+1, k-(i+1), v)+cur);
    }
    return dp[pos][k] = ans;
}
void solve(){
    int n, k;
    cin >> n >> k;
    vector<ai> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i][0];
        cin >> v[i][1];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) dp[i][j] = -1;
    }
    int ans = dfs(0,k,v);
    if(ans<1e9) cout << ans << endl;
    else cout << -1 << endl;
}

Stuck on E since I could not figure the amount of times each point will be contained in a sub-square. But overall, really nice contest.

I was 10 minute too late for submitting E... feelsbadman

Wow I mean solving ABCD as a newbie and still get a negative delta

This was a fun round! Got stuck on F for a long time, I wrote dp that stored the fewest moves required for the current rectangle index and current score, but one test case gave an incorrect answer and I couldn't figure out why: 276291118

Why this code (https://mirror.codeforces.com/contest/2000/submission/276250584) for problem D failed on test case 7?
Any counter test case?

for G, l did binary search + dp approach and l am in doubt about the correctness, pls hack my solution if you can, thx! submission link

Good contest, I just performed really badly cause I couldn't figure out some edge case on D :(

my idea for F is
we can pick a greedily pick a rectangle whose one of the dimension is minimum across all $$$(ai, bi)$$$
suppose $$$ai$$$ is minimums we add $$$ai$$$ to our cost and and get 1 point and decrease other dimension by 1
$$$cost \ += \ ai$$$
$$$k \ -= \ 1$$$
$$$bi \ -= \ 1$$$
but it's giving 36 instead of 35 for last tc

Please help me find out why submission 276251214 in C++17 (GCC 7-32) Runtime Error but same code submission in C++20 (GCC 13-64) Accepted?

I couldn't even understand sample test cases on problem F

wtf

Can someone please explain me the 6th sample testcase for problem F.

Sample input :

3 25 9 2 4 3 8 10

Sample Output : 80

how did so many people solve ABCD wtf?

This contest was fun, I solved ABCD within around 1 hour, and I solved E with 10 minutes left. Hope to get 1250+ rating!

Imagine D without the last case it would be so much fun pain

My dp shows what I am feeling like. Missed an overflow leading to wrong answer and all this while i was thinking why can't I find an edge case. F.

Still a very great contest. Appreciated the problems with good enough difficulty. Thanks a lot to the authors and tester

wow! so many people had the same idea for e! and the same code too!