Codeforces Round 966 (Div. 3)

3 months ago, # ^ |

+10

change ur pfp back sir, keijo is too degenerate for u

→ Reply

xorfftdp

3 months ago, # ^ |

+16

why would you want to test as a cheater

→ Reply

xorfftdp

3 months ago, # ^ |

you can go test a div 5

→ Reply

3 months ago, # ^ |

yeah, cuz cheaters<newbies

→ Reply

3 months ago, # ^ |

IoI will always be a dream for cheater's

→ Reply

3 months ago, # ^ |

sorry idk the context but why's everyone calling @puupil a cheater? was he caught cheating or something?

→ Reply

3 months ago, # ^ |

Some good people release E solution during the contest It had a bug that is used to hack all cheaters who copied (go to hack section and view hacked E you will se pattern in code)

→ Reply

3 months ago, # ^ |

damn this is down bad

how do you know he did that though, did someone post a blog?

→ Reply

3 months ago, # ^ |

No blogs posted it's just observation and those who know know (it is what it's is)

→ Reply

3 months ago, # ^ |

oh you meant blatant racism, understood. thanks!

→ Reply

3 months ago, # ^ |

Bro this is not racism see his hacked submission E ( Stop assuming things I told you observer if you can't understand this do some problem instead of commenting)

→ Reply

3 months ago, # ^ |

System testing is going on so view after that

→ Reply

3 months ago, # ^ |

← Rev. 2 →

i asked you how you knew about it and you said iykyk, i guess it's a language barrier so i apologize, sorry.

i did check for his hack on E before commenting but didn't find any hack, maybe because of system testing.

→ Reply

Abhiraj_231010203

3 months ago, # |

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 .

→ Reply

phsads

3 months ago, # ^ |

are you consistent at div2Cs yet

→ Reply

Abhiraj_231010203

3 months ago, # ^ |

No , 60 % solvable in general .

→ Reply

agr_pranjal

3 months ago, # ^ |

Bhai mujhe bhi tips batadiyo ****

→ Reply

ss_inha

3 months ago, # ^ |

Abhiraj bhai yeh sub kya kar re ho app padhai likhai karo jakar

→ Reply

3 months ago, # |

← Rev. 4 →

-7

Expect to solve at least 4

Hope to solve at least 5 and get 1250+ rating

UPD: Solved ABCDE

→ Reply

DavidGoggins

3 months ago, # ^ |

Good Luck

→ Reply

calculus0129

3 months ago, # ^ |

NOICE

→ Reply

3 months ago, # ^ |

← Rev. 2 →

-8

thx, I solved E with 10 mins left, which I'm really happy about.

I tried upsolving F and I failed, so this is probably the best I could have done.

I always seem to underperform Div.2 and Div.2+Div.1 and overperform Div.3 and Div.4

→ Reply

calculus0129

3 months ago, # ^ |

Im glad to hear that you've done it:) Guess you would be really happy then.

I was solving F for about 40 minutes, but it was hard in implementation + because of sleepiness (It was about 2 a.m. in my time). So I solved only ABCDE too.

I guess both you and I could prepare Div2 and later by solving some Div2 problems from the problemset prior to the contest.

GL to you for this one. Hope you could promote back to pupil!

→ Reply

meisgood

3 months ago, # ^ |

← Rev. 2 →

well i think in this round G is easier than F. during the contest i have no idea of how to solve F as greedy wont work and i was shocked when i saw most people use DP to solve...

→ Reply

calculus0129

3 months ago, # ^ |

NOICE, dude!

→ Reply

proAakash

3 months ago, # ^ |

how so pro?

→ Reply

AlRntn

3 months ago, # ^ |

congrats to solve ABCDE

→ Reply

larush

3 months ago, # |

I wish I can AK this round >_<

→ Reply

H_R_K

3 months ago, # |

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

→ Reply

MO_Tamer

3 months ago, # |

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

→ Reply

ziad-abdou1

3 months ago, # ^ |

why you don't join contest

→ Reply

rangerscowboys

3 months ago, # |

More people created problems than tested them :O

→ Reply

IFti_101

3 months ago, # |

hope to reach pupil in this contest :D

→ Reply

abhi_98x

3 months ago, # |

No one for testing CYAN :(

→ Reply

Saitamaaaa

3 months ago, # |

I hope this contest to be cheating free.

→ Reply

Hamza_taigo

3 months ago, # |

welcome a new -100 (¬_¬)

→ Reply

eason919

3 months ago, # |

Wish I can get Expert on this contest!

→ Reply

shevlopmes

3 months ago, # |

lol guys you probably need some more testers)

→ Reply

Vladosiya

3 months ago, # ^ |

+30

We had the whole night to fix this :)

→ Reply

DLSdufer

3 months ago, # |

+26

contest no.2000!

→ Reply

alpha_6124

3 months ago, # |

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

→ Reply

singhprajjawal87

3 months ago, # ^ |

same with me also may be i think more cheater in div 3 than div 2 because of hard question codeforces should find some permanent solution from this

→ Reply

Salah7_a

3 months ago, # |

hope for Asuna_Yuuki

→ Reply

Asuna_Yuuki

3 months ago, # ^ |

hope for Salah7_a

→ Reply

huanjua

3 months ago, # |

As a participant, DangKhoizzzz orz__

→ Reply

DangKhoizzzz

3 months ago, # ^ |

hello

→ Reply

huanjua

2 months ago, # ^ |

ily bbg

→ Reply

kalpitdon7

3 months ago, # |

OMG! Another Vladosiya round !

→ Reply

_kRaT0s_

3 months ago, # |

wapis blue banna hai mujhe.. (hopefully)

→ Reply

1aksh730

3 months ago, # |

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

→ Reply

OIaspirant2307

3 months ago, # ^ |

atb to you, setting the same goal for me :prayge:

→ Reply

Grammar_hbw

3 months ago, # |

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

→ Reply

Kirkon

3 months ago, # |

As a tester, I wish you would enjoy the contest

→ Reply

whyalwaysmezzz

3 months ago, # |

I will full solve this round, ggez

→ Reply

amon_get

3 months ago, # |

Satyam is definitely not blue testing, lmao

→ Reply

papa-ka-para

3 months ago, # |

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.

→ Reply

-2.71

3 months ago, # |

-11

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

→ Reply

EntityPlantt

3 months ago, # |

+13

Contest #2000 on Codeforces! What a milestone

→ Reply

RomanLeshchuk

3 months ago, # |

Hope to solve 5 problems today. Good luck everyone!

→ Reply

Supper2002

3 months ago, # |

I hope through this game, I can reach the Specialist

→ Reply

VISH9756

3 months ago, # |

Hope to reach 1300+ rating in this round

→ Reply

Salah7_a

3 months ago, # |

Here we go to Chess.com :D

→ Reply

aayush249

3 months ago, # |

Thousands of submissions for E in the last 20 minutes wow

→ Reply

aayush249

3 months ago, # ^ |

My rank doubled over the last 20-30 minutes.

→ Reply

Thirdreigncitizen

3 months ago, # |

-12

Great contest! Good problems for a div 3

→ Reply

zer0_123

3 months ago, # |

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

I still have 20 minutes left

→ Reply

3 months ago, # |

← Rev. 2 →

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

Great Contest though , enjoyed :)

→ Reply

MaroMaxor

3 months ago, # ^ |

i think 30 mins ago it was 2000 subs or smt like that

→ Reply

3 months ago, # ^ |

2000 on F ???

→ Reply

MaroMaxor

3 months ago, # ^ |

oh mb i thought u meant E

→ Reply

3 months ago, # ^ |

ah nvm

→ Reply

Thirdreigncitizen

3 months ago, # ^ |

← Rev. 2 →

it is 1400, still huge amount for a div 3

→ Reply

3 months ago, # |

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

→ Reply

MKasirloo

3 months ago, # |

Nice contest, but cheaters ruined it again

→ Reply

3 months ago, # ^ |

yeah

→ Reply

Stuck_On_Gray

3 months ago, # |

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

→ Reply

MJavad

3 months ago, # ^ |

← Rev. 2 →

6
1 1 1 1 1 1
LLRRLR

→ Reply

MJavad

3 months ago, # ^ |

Your code will be fine with the minimum change.

Code

ans+=max(0ll,prf[rs[r]]-(ls[l]>0?prf[ls[l]-1]:0ll));

276325664

→ Reply

frissky9

3 months ago, # |

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

→ Reply

3 months ago, # ^ |

disagree, it was pretty clear.

→ Reply

DuongForeverAlone

3 months ago, # |

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

→ Reply

focus_2024

3 months ago, # |

Finally I solved 4 problems

→ Reply

adaptatron

3 months ago, # |

+11

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 :

Find out the location of the last zero.
Add a delta in a range.
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.

→ Reply

adaptatron

3 months ago, # ^ |

On second thought, you don't even need to query min/max using Lazy segtree. The last $$$x$$$ where $$$dp[x] = 0$$$ would simply be determined by finding the upper bound of existing elements and looking to the left. Hence, you just need a segment tree to do range increments and range maxima. So overall time complexity becomes $$$O(N \cdot log(N))$$$.

→ Reply

nskybytskyi

3 months ago, # ^ |

I used a segtree to maintain the longest missing segment on a range. You'll need to additionally store range length, longest missing prefix and suffix: 276231982. Finding the first missing segment of length $$$k$$$ corresponds to binary earching on a segtree, which atcoder library conveniently provides in $$$O(\log n)$$$.

→ Reply

DuongForeverAlone

3 months ago, # ^ |

For me, I saw that we need to find the minimum number $$$x$$$ in the current set such that the difference between $$$x$$$ with its right element is strictly greater than $$$k$$$. The answer is $$$x + 1$$$. I used a segment tree with minimum query to find such $$$x$$$. 276290172

→ Reply

leshless

3 months ago, # |

Any hints on F?

→ Reply

3 months ago, # ^ |

→ Reply

yashnator

3 months ago, # ^ |

← Rev. 3 →

Calculate the costs of increasing a point by 1 in each rectangle for all n + m axes. It is min(dim(x), dim(y)) at each turn.

Then do a simple dp iterating on 'i'th rectangle, solving for 'j' points and taking 'x' first axes from the 'i'th rectangle

Submission for reference

→ Reply

kai-zen

3 months ago, # ^ |

Do you try to think of the problem first in a recursive way and then try to optimize it using DP, or you are able to think of the DP solution right away? If yes, how?

→ Reply

LightGran

3 months ago, # ^ |

For a given rectangle find the minimum number of cells to paint to achieve a gain of $$$t$$$ points. $$$t \leq k$$$. To compute this , you will paint cells in a way so that first $$$a$$$ rows are first $$$b$$$ columns are painted so that $$$a + b = t$$$. Note that minimum cells = $$$ n * b + m * a - a * b$$$ where $$$n$$$ is number of rows and $$$m$$$ is columns. After that this problem is similar to knapsack.

→ Reply

kruelcratos

3 months ago, # ^ |

← Rev. 2 →

Do DP

with states taking the first i rectangles and getting atleast j points then check for minimum among all possibilities of taking x rows and y columns and reduce time by adding the check that $$$x+y \leq k$$$

the number of operations performed is simply $$$x*b + y*a - x*y$$$

→ Reply

Atma_

3 months ago, # |

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

→ Reply

3 months ago, # ^ |

No, because k can be really small and you can have a big a*b, and a small a*b, but to get k, the smaller a*b can be completed in less moves.

→ Reply

3 months ago, # ^ |

Can you explain a little more please, still not clear to me. Thanks

→ Reply

3 months ago, # ^ |

← Rev. 2 →

The person above didn't clearly explain their greedy strategy. There are many greedy variations that get WA, so if you have a concrete greedy strategy I can try to come up with a countercase.

→ Reply

3 months ago, # ^ |

← Rev. 2 →

I always take the rectangle with smallest side (lets say a, b where a<b), now the cost of increasing points by 1 is a (Since I'll fill all the squares along the side a). Once I perform this operation my sides become a, b-1. I insert { min(a,b-1), max(a,b-1) } back in my multiset unless a and b both are zero.

→ Reply

3 months ago, # ^ |

← Rev. 4 →

Input: $$$2 ~~ 9 \newline 4 ~~ 32 \newline 5 ~~ 7$$$

Your output: $$$36$$$

Correct output: $$$33$$$

→ Reply

3 months ago, # ^ |

Okay got it. Thanks

→ Reply

sandbag

3 months ago, # |

← Rev. 2 →

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.

Code

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;
}

→ Reply

ImAman

3 months ago, # ^ |

Can you pls check where am i going wrong in my implementation. Thanks!

Code

int ind(pii rect,int score){
    if(score==0)
        return 0; 
    int h=rect.first;
    int w=rect.second;
    int ans=INT_MAX;
    for(int i=1;i<=min(h,score);i++){
        // i rows,score-i col
        int j = score-i;
        if(j>w)
            continue;
        ans=min(ans,i*h+j*w-i*j);
    }
    return ans;
}

int cnt(int i,int k,vector<vector<int>>&dp,vector<pii>&rect,int n){
    if(k==0)
        return 0;
    if(i==n)
        return INT_MAX;
    if(dp[i][k]!=-1)
        return dp[i][k];
    int ans=INT_MAX;
    rep(j,0,k){
        int t = cnt(i+1,k-j,dp,rect,n);
        if(t!=INT_MAX){
            int s = ind(rect[i],j);
            if(s!=INT_MAX){
                t+=s;
                ans=min(ans,t);
            }else{
                break;
            }
        }
    }
    return dp[i][k]=ans;
}

void solve() {      

    int n,k;
    cin>>n>>k;
    vector<pii>rect(n);
    cin>>rect;
    vector<vector<int>>dp(n+1,vector<int>(k+1,-1));
    int ans=cnt(0,k,dp,rect,n);
    ans=ans==INT_MAX?-1:ans;
    cout<<ans<<endl;

}

→ Reply

ImAman

3 months ago, # ^ |

nvm, figured it out.

→ Reply

Mega6776

3 months ago, # |

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.

→ Reply

3 months ago, # |

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

→ Reply

3 months ago, # ^ |

so sad I don't have enough speeeeeeed

→ Reply

3 months ago, # |

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

→ Reply

Le_Gusto

3 months ago, # |

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

→ Reply

Le_Gusto

3 months ago, # ^ |

Figured out the problem, I was getting 86 instead of 80, because I fixed the row and column sizes for every score for the rectangle. For example, for 2 points I would fill a 3x3 rectangle with 3+3 operations, when it could be colored with 3+2, since 3x3 becomes 3x2 after the first operation. Worked perfectly after accounting for this

→ Reply

3 months ago, # |

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

→ Reply

pranp_24

3 months ago, # ^ |

Need to use long for prefix sum array

→ Reply

Summer_Wind

3 months ago, # ^ |

You have declared prefixsum to be of type int, but with n = 2e5 and ai <= 1e5, prefixsum can exceed INT_MAX and cause an overflow.

→ Reply

3 months ago, # ^ |

Yeah realised just now after seeing the failed test case, when i got 2 WA then i left the contest thinking if this is not correct then i cannot think another now, now i regret :(

Just a silly mistake, how dumb i am :(

→ Reply

devvikram22

3 months ago, # ^ |

use #define int long long

→ Reply

3 months ago, # ^ |

Will it be a nice practice to use long long instead of int everywhere? Is there any cons doing that?

→ Reply

3 months ago, # ^ |

It will be a little bit slower and use more memory, however it is extremely unlikely that you will TLE or MLE because of that.

→ Reply

3 months ago, # ^ |

Oh, Okay, thanks.

→ Reply

devvikram22

3 months ago, # ^ |

never found tle or mle so can use. at worst only mle not tle

→ Reply

qwqIdontHaveAgf

3 months ago, # |

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

→ Reply

Karim__2

3 months ago, # ^ |

can you explain the first test case please .

→ Reply

iiTzRoyal

3 months ago, # ^ |

← Rev. 2 →

I think g can be solved by dijkstra, it's a beautiful problem.

→ Reply

kunalc1

3 months ago, # |

+13

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

→ Reply

eresharora

3 months ago, # ^ |

← Rev. 2 →

Your solution is correct,but In this line of your code score += mult[i] * nums[i] both mult[i] and nums[i] are integer so their product is also integer,you should declare nums and mult by long long integer.

→ Reply

kunalc1

3 months ago, # ^ |

Oh my goodness, thank you!! For some reason I thought that 2e10 would fit in an integer data type but it doesn't. Thanks again! :)

→ Reply

alpha1215

3 months ago, # |

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

→ Reply

LightGran

3 months ago, # ^ |

It is to be solved using knapsack.

→ Reply

polaris16

3 months ago, # ^ |

Did you find how for last TC, 35 is the answer instead of 36?

I tried similar approach where I tried to get 18 points by filling 6X2 and 8X3, or is there any simpler test case that shows that it can't be solved greedily?

→ Reply

ayush118

3 months ago, # ^ |

Use all rows and columns of (2,6) and (4,5) and use 1 column of (8,3)

→ Reply

polaris16

3 months ago, # ^ |

Thanks

→ Reply

kmparvez

3 months ago, # |

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?

→ Reply

3 months ago, # ^ |

This line int j = rs.size()-1; is the issue when the string has no 'R' character, because rs.size() returns an unsigned type, you should cast it like this (int)rs.size()-1;

I guess the the C++20 compiler helped you out on that

→ Reply

kmparvez

3 months ago, # ^ |

Thank you so much.

→ Reply

alpha1215

3 months ago, # ^ |

.size() uses unsigned int so 0 — 1 will overflow
276296054

→ Reply

kmparvez

3 months ago, # ^ |

Thank you so much.

→ Reply

tickbird

3 months ago, # |

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

wtf

→ Reply

dhruv0902

3 months ago, # |

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

→ Reply

wqweto

3 months ago, # ^ |

← Rev. 2 →

I didn't submit it because I was getting 86 here no matter how I tweaked. I cannot manually find a solution with 80 pixels too.

Edit: Just figured it out. On the 8x10 tile you can score 7 for cost of 50 pixels like this: https://dl.unicontsoft.com/upload/pix/ss_problem_f.png

→ Reply

pagol

3 months ago, # ^ |

← Rev. 2 →

Take 9 2 for cost of 18 and points equal to 11. Then 4 3 for a cost of 18+12=30 and points equal to 11+7=18. After that, every time add min(a,b) to the operation and points increase by 1. Also, subtract 1 from max(a,b) until points are greater than or equal to k.

Though for this problem greedy will failed( i guess).

→ Reply

dhruv0902

3 months ago, # ^ |

Thanks for the help wqweto and pagol.. was really helpful.

→ Reply

3 months ago, # |

how did so many people solve ABCD wtf?

→ Reply

3 months ago, # |

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

→ Reply

3 months ago, # ^ |

Indeed it was fun, even I submit E 10 minutes later I still feel very enjoyable.

Coding until the last minute

→ Reply

3 months ago, # |

+16

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

→ Reply

3 months ago, # |

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

→ Reply

3 months ago, # |

+12

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

→ Reply

Thirdreigncitizen

3 months ago, # ^ |

-18

its most likely cheaters, 5000 solved E in a div 3 isnt normal

→ Reply

3 months ago, # ^ |

Yeah, I was shocked by how many people solved E.

→ Reply

3 months ago, # ^ |

I do think E have some dp trick or math trick, it should be a quick one for experienced players (but not me tho, E cost me 1.5hrs rofl)

→ Reply

3 months ago, # ^ |

2d prefix sum :P

→ Reply

3 months ago, # ^ |

bruh I used brute force and got AC in 343 ms

→ Reply

3 months ago, # ^ |

yep it is, was clueless in the contest so I just brute force all the way and get the math formula (cost a lot of time for testing everything)

→ Reply

NexTopper

3 months ago, # ^ |

2D differance array.

→ Reply

ibrahimwq

3 months ago, # ^ |

u can calculate weight of each cell by pure arithmetic

→ Reply

3 months ago, # ^ |

lmao i spent a while but the parity of k threw me off so i gave up on that

→ Reply

3 months ago, # ^ |

yeah, that's what I did

→ Reply

3 months ago, # ^ |

idk how you did, but essentially for any cell, you can very easily calculate in how many subsquares its gonna appear, and if you just put all of that in an array and sort it in descending order, you can sort the heights in descending order as well, and then multiply biggest height with biggest multiplier, 2nd biggest with 2nd biggest etc..

→ Reply

cuanim

3 months ago, # ^ |

can easily calculate in how many subsquares its gonna appear

Any hints on how to calculate this? I was trying to derive a formula but failed ;-;

→ Reply

OmarAboutaleb77

3 months ago, # ^ |

← Rev. 3 →

You can calculate how many subsquares will contain a cell by calculating the minimum and maximum possible x and y for the top left square of a subsquare of size k by k by that contains that cell . If you need more hints I can help you.

→ Reply

jha_rishi

3 months ago, # ^ |

yes please, for topX = max(0, i-k+1) and topY = max(0, j-k+1) but not able to understand how to find bottom one

→ Reply

OmarAboutaleb77

3 months ago, # ^ |

Both your minX and minY are correct. For the maxX and maxY, there are two things bounding it: i and j, and the distance from the edge of the grid. So maxX = min(i,n-k) and maxY = min(j,m-k).

→ Reply

cuanim

3 months ago, # ^ |

Ah yeah that does make sense. I think I have an idea on how to approach it now

Thanks, I'll try solving it myself later.

→ Reply

3 months ago, # ^ |

well you can see that in best case scenario it would be K*K, and in the worst case scenario(if its a corner cell) its 1*1. you can also see that the cell thats in the center always has the max possible multiplier, while the ones that are closer to the edges gradually decrease. consider that, and try to derive a formula from there

→ Reply

cuanim

3 months ago, # ^ |

Yep I noticed that while writing it down but couldn't generalize it, it's fine I think I'll sleep on it and try it later. Thanks for reply btw

→ Reply

Safawt

3 months ago, # ^ |

← Rev. 2 →

An alternate solution that I feel is simple is that if you take it to one dimension, in each row now its no longer a k sided square but a window of size k that moves along the array you can increment the starting positions of the windows and decrement their ends, so you can iterate over every cell, say its at index i, and if i + k < columns, then you can increment arr(i) and decrement arr(i+k), and if i + k == columns, then only increment arr(i) because you dont need to close off the window from the right (it will be after the array’s end), and after youre done you iterate over this array and calculate the prefix sum array, and this will make the values at each cell represent the number of windows that cover it Do this for a grid over all rows, then do this same thing but on a different grid over all columns, and then multiply the values in the corresponding cells, and this value represents how many K sided squares will cover this cell

→ Reply

zer0_123

3 months ago, # ^ |

I had this same idea but it felt too brute force (that it would not pass the time limit) so I didn’t try it.

→ Reply

3 months ago, # ^ |

n*m over all test cases is 2*10^5, so you can kinda see that they were aiming for an n*m solution

→ Reply

zer0_123

3 months ago, # ^ |

oh I did not notice that. Makes sense.

→ Reply

Astroflexx

3 months ago, # |

+13

Amazing contest! Problems were true Div3 rated.

Thanks a lot for the round myav Gornak40 senjougaharin Vladosiya and all testers!

→ Reply

https://codeforces.me/contest/2000/submission/276270036 https://codeforces.me/contest/2000/submission/276291750

3 months ago, # |

I hope to become specialist in this round but chances of drop are high too at 5k rank

→ Reply

101fk_cheaters101

3 months ago, # ^ |

+19

Please add "By cheating" also in this comment lol.

Your last Div 2 's C was also copied from telegram/YT isnt ?

→ Reply

3 months ago, # ^ |

-21

Nope it wasn't coz the code here is quite short. So similarities are natural. Additionally, the variables used are also directly picked from the question. If I copied from yt/telegram I would have solved till G. Nor would I have submitted this late.

→ Reply

101fk_cheaters101

3 months ago, # ^ |

+10

So you wanted me to make a dedicated blog ?

btw you are atleast brave(or maybe stupid enough?) to cheat that casually and have your name , college name etc .

→ Reply

3 months ago, # ^ |

-19

Having my name, college name etc is enough of an evidence that I won't do anything that stupid on a website that's public and doesn't erase past records and shows your code to everyone. Although I can say look at my submission map, problems solved, submission time of codes etc, I won't and will try to be objective here.

For small codes, we can't really figure out if someone has cheated because ideas are likely to be the same all over.

You might notice a difference in coding style of both the links. Now consider the two possibilities here — assuming that I cheated, I could have done 2 things —

a) Copy the code as it is. This clearly ain't the case because the two codes in the link you gave have different structures (the second being my signature style that might be verified by checking my previous submissions)

b) So this brings us to the second case — I did minor changes (not the gpt ones like variable change). So I was smart enough to manually type the code in my coding structure but not smart enough to change the variables? Wouldn't I try to make them as different as possible from the original source I am copying from if I already took the burden of doing the hard part ie restructuring it? And about the similar variable names, as I said they are the standard ones I normally use (check some of my past subs like using cnt for count to save time) and the rest being picked from problem itself.

The coding style of the code you shared seems radically different to mine (infact idk fs what ll means maybe coz I never had the need to use it) so in that case I wouldn't have removed it had I copied it from here since idk what it does and how removing it would effect my program (but would give you a benefit of doubt for this one since I can't prove that idk what ll is xD).

Now with all due respect I'd request you to please reply a strong counter to it OBJECTIVELY without assumptions or in case you do have to make them, make it statistical enough to have a high probability of occurrence with (preferably) quoting data.

Additionally, your profile is quite new, created just at the time you replied to my comment which hints at the sole purpose of replying to me as the purpose of its creation (maybe because you yourself are a cheater who is scared of being caught had you come from a real account? Maybe someone who actually copied from the source you mentioned?) But anyways I won't make wild assumptions like that but this but the part of you creating this account just for the purpose of making this comment is a fact as it can be cross checked from the time frames there above mentioned. Idk what's the intent behind it but fs there is something you are scared of for which you didn't reply with your real acc.

Additionally, I'd take the part of you pointing out specifically at my profile picture and me mentioning the name of my college as a try to create pressure via blackmailing (cyberbully in simple words) so would henceforth request MikeMirzayanov to check it out (and also manually review my code and the one stated above to crosscheck and ask for further clarifications if needed).

I do get people getting pissed off from cheating but there is a clear difference between asking for clarification politely and attacking someone directly with giving threats in response restorting to cyberbullying. Creating a fake account just for the purpose of doing so further adds suspicion for it being done for a malicious intent.

→ Reply

3 months ago, # ^ |

That "infact idk fs what ll means maybe coz I never had the need to use it" is kinda sus though

Are you saying that you don't know what "long long" is? You literally have a #define int long long in your code so you should know that #define ll long long also does the same thing, using a shorter name for the type

→ Reply

3 months ago, # ^ |

-12

Actually I have been coding in a standard template since the start of my cp journey so always used int for long long (except in initial days when I worked in C). Not much idea about macros except how they work. And that other code used 2 different macros for long long so idk of that or how the two are different

→ Reply

Subarna1

3 months ago, # ^ |

I have two questions for you:

Why you used global array in 276291750 and 276236011 where as you mostly used vector (local vector) like you used in this 275625615?
Why you delete some of your code from your template in Solution E?

PS: I'm not accusing anything here; I'm just genuinely curious.

→ Reply

3 months ago, # ^ |

← Rev. 4 →

-13

Declaring an array locally may exceed the size limit since it is stored in a stack in C++. How did I know it is the particular case? By testing it and failing twice (mle is a pain to debug coz cph doesn't show any output. Nor codeium explains it in most cases)

PS — Using extensions like cph and codeium arent against the rules afaik.

In fact you might try giving it a shot yourself. If you use VS Code, just copy paste my code there and cut that array declaration part from the global scope and paste it in local scope. The program will likely crash. I do use local arrays but it isnt really a good practice to do so (i am just habituated) because it can lead to issues like this where your program just crashes abruptly and you might not be able to figure out why it went wrong.

Now coming to the deleted code part, well in one of the attempts of correcting the code when I was selecting to erase my code (the previously written code) parts of my template was also selected and got deleted. Yeah i could have done Ctrl+Z but there were like 5 mins on the clock, i was kinda panicked and then it clicked why the program might have crashed (global array issue. i knew this because it happened before once in one of the problems of binary search on answer recently of spoj called paul's conjecture) so i just started typing not caring of whats lost (some got auto generated my codeium, an extension installed on my vs code which sort of remembers your previous code and makes typing quick) and as you can see i made my submission in the last minute with 10 secs left on timer.

but why did i use a static array in the 1st place when i normally use a vector? well i use vectors most of the times but not all the times. you can say i sort of switch between arrays and vectors (favoring vectors more though xD) but i do use arrays in some cases like you might see my solution to B in this contest where i used an array instead of vector to store boolean values. And you cant say that code is copied because i even saw the solutions of various PCD channels and none used the particular approach which I used for B so it is in a way unique (not the best though)

EDIT — AND YES SINCE YOU BROUGHT IN THE ARRAY PART I NOTICED JUST NOW THAT ARRAYS ARE ALSO DECLARED DIFFERENTLY. IN THE LEAK CODE THE ARRAY IS DECLARED BY KEEPING A CONST CALLED M. THAT AINT THE STYLE I USE IF YOU LOOK AT MY OLD TEMPLATES I HAVE ALWAYS USED MINIMAL CONSTS ONLY FOR THINGS LIKE INF AND MOD. ALSO, THE VALUE OF DECLARING ARRAY IS DIFFERENT IN THE SOURCE COUDE IT IS 1E5+7 AND IN MINE IT IS 1000000 BECAUSE I (AND NATURALLY ANYONE UNLESS A SPECIAL CASE NORMALLY DECLARES ARRAYS IN POWERS OF 10). THAT SERVES AS ANOTHER TESTIMONIAL FOR THE ORGANIC NATURE OF MY CODE!!!

→ Reply

vjudge257

3 months ago, # ^ |

Why did you get mad at the end? I mean tbh the guy is not even wrong. I've seen several people with the same exact code as yours and the same exact definition of the global array and etc... So how come that the 3 codes the guy pointed out at all have similarity with other people? Or do you call that a "coincidence"?

→ Reply

3 months ago, # ^ |

← Rev. 2 →

@vjudge for the similarities in the code as my first comment says, it is clearly possible with a really good probability because the length of the code is fairly short. For a 8-10 line code it is impossible to have significant differences because the logic is pretty much straight forward. Now I am no where claiming E was an easy problem. But sometimes hard problems are straight too it's just that they are hard because you take time to figure out the chain of thoughts. Try to compare problem As you might find many people having similar codes because in small codes it is impossible to spot much differences.

For the global array part, as I stated in another of my comments, it is because of the nature of the problem. You are a newbie so you might not know (no offense even I came to know of it a few weeks back at pupil) that using a local array sometimes gives MLE that crashes your program and this is the case here so using a global array becomes evident.

And for many people having same codes for global array declaration, maybe you are right I didn't do a research on similar codes to the one this guy sent and it might be true it was leaked (but again we can't figure it out as this code is short) but even it's the case, my array declaration is different from the one he shared. There's no similarity between the two and they are radically different for using both different techniques and values as far as the given code is concerned. The first code declares a constant M with a values and uses that to declare the array. That's a technique I have never used and even in my submission I have declared the array directly. Also, check out the value of const in the array in the code above and compare it with the value in mine. Even they both are different. So how in any way is global array declaration same in both of these?

EDIT — And I didn't really get mad at the end I got panicked which any one does when time is running out. The ones who don't are extremely calm people and they are exceptions

→ Reply

Astroflexx

3 months ago, # |

Did anyone else use DSU for problem C lol?

→ Reply

Acanikolic73

3 months ago, # ^ |

I didnt use but i realy thinking about dsu , but i realize that a div3 C must be something eazy

→ Reply

tangdong_

3 months ago, # |

someone hack my F, its O(n * k^3) 276277213

→ Reply

3 months ago, # ^ |

← Rev. 2 →

thats 10^9 which should fit into bounds though right?

→ Reply

whiitex

3 months ago, # |

During contest, in problem E, I could only see green and yellow cells in the test sample. Was it only my problem?

→ Reply

3 months ago, # ^ |

common

→ Reply

3 months ago, # ^ |

No, the picture was edited later in the contest

→ Reply

3 months ago, # ^ |

the moment announcement was sent there was 6000 submission

→ Reply

Siranticorz

3 months ago, # |

← Rev. 3 →

+39

Fun fact: among the 7 "trusted" participants who solved all the problems, almost half of them are being untrustworthy, rank 4,5,6 submitted the same code except that they changed the variable names.

→ Reply

3 months ago, # ^ |

The 'trusted participant' thing is there to prevent alts conquering the scoreboard. It can't do anything against cheats.

→ Reply

zrnstnsr

3 months ago, # |

Don't know why the last sample of G is 2 for quite a while until I see During the phone call, you cannot ride the bus, but you can walk along any streets, make stops , or stay at home.

→ Reply

IHateDP001

3 months ago, # ^ |

← Rev. 2 →

Can u please reiterate what u said? if we start at t=2, 2nd and 4th city will have their timestamps as 3 and 5 resp and we have to attend phone call for duration 5-7, so how are we able to cross to 5th city in <= t0?

I am sorry, I am dumb, I just saw that phone call is only for the duration 5-6. So we can wait at 4th city.

→ Reply

zrnstnsr

3 months ago, # ^ |

phone call is 5-6, not 5-7

→ Reply

b00s

3 months ago, # ^ |

can you explain, why the sample testcase 1 answer is 0. I think we can wait upto 19 minutes and then take the bus route 1 — 5 which will cost 30 minutes, and we will arrive on 5 at 49 minutes ?

→ Reply

3 months ago, # |

← Rev. 2 →

276274588 and 276288231 LMAOOO, how does this not get caught in plag checks?

Another one 276288851

→ Reply

vinhdangquoc729

3 months ago, # |

← Rev. 2 →

Many submissions for problem F contain this strange block of code, and now they're receiving WA hacks.

Spoiler

int V = C[40][70][70];
for (int i = 0; i < N + 5; ++i) {
    for (int j = 0; j < K + 5; ++j) {
        D[i][j] = V;
    }
}

→ Reply

TOMAS_SHELBY

3 months ago, # |

why greedy dont works for F? If sort pairs {min(a,b), max(a, b)}, fill that smallest side, +1 point for smallest side, in moment that will be square and thats anyway easiest way to got +1 point

→ Reply

3 months ago, # ^ |

This thing right?

// this is code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    multiset<pair<int,int>> s1;
    multiset<pair<int,int>> s2;

    int n,k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int x,y;
        cin >> x >> y;
        s1.insert({x,y});
        s2.insert({y,x});
    }
    int cost = 0;
    while(k>0){
        auto pr1 = *s1.begin();
        auto pr2 = *s2.begin();

        int x1 = pr1.first;
        int y1 = pr1.second;
        int y2 = pr2.first;
        int x2 = pr2.second;

        if(x1 == x2 and y1 == y2){
            s1.erase(s1.begin());
            s2.erase(s2.begin());
            if(x1 == 1 and y1 == 1){
                k-=2;
                cost += 1;
                
            }
            else{
                if(x1 <= y1){
                    k -= 1;
                    cost += x1;
                    s1.insert({x1,y1-1});
                    s2.insert({y1-1,x1});
                }
                else{
                    k -= 1;
                    cost += y1;
                    s1.insert({x1-1,y1});
                    s2.insert({y1,x1-1});
                }
            }
        }
        else{
            if(x1 <= y2){
                k -= 1;
                cost += x1;
                s1.erase(s1.begin());
                s2.erase(s2.find({y1,x1}));
                s1.insert({x1,y1-1});
                s2.insert({y1-1, x1});
            }
            else{
                k -= 1;
                cost += y2;
                s2.erase(s2.begin());
                s1.erase(s1.find({x2,y2}));
                s1.insert({x2-1,y2});
                s2.insert({y2, x2-1});
            }
        }

        if(s1.empty() and k>0){
            cout << "-1\n";
            return;
        }
        
    }
    cout << cost << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

→ Reply

MuhammedShoeib

3 months ago, # ^ |

must use dp

→ Reply

TOMAS_SHELBY

3 months ago, # ^ |

explain please how to get 35 in last test case

→ Reply

msvardhan19

3 months ago, # ^ |

coloring all cells of 5 x 4 and 6 x 2 rectangles would give you 9 and 8 points costing you 20, 12 operations.

now color one row of 8 x 3 rectangle, you get 1 point at a cost of 3 operations.

→ Reply

wizardrabbit

3 months ago, # ^ |

+40

Sure, here you go!

→ Reply

VitaliiV

3 months ago, # |

Hackforces

→ Reply

ChuanSWTtest

3 months ago, # |

← Rev. 2 →

+11

About problem F,why so many people define the size of a three-dimensional array as 40*70*70？ 276276544 276285014 276272465 276274621 276287283 276287474 276279626 276276752

→ Reply

tangdong_

3 months ago, # ^ |

+38

probably clueless cheaters

→ Reply

3 months ago, # ^ |

← Rev. 2 →

absolute cheating, i also tagged some submissions 4 comments above. Is it possible for someone else to see what hacks are being made by someone else during the hacking phase?

→ Reply

3 months ago, # ^ |

i dont think so, but its fine, since all of the submissions will be tested on every successful hack later.

→ Reply

3 months ago, # ^ |

oh didnt know that , then its pretty cool :) fuck them cheaters

→ Reply

shiinamashiro_

3 months ago, # ^ |

HACK ALL OF THEM!

→ Reply

zeena.

3 months ago, # ^ |

276275956 this one also lmfao

→ Reply

aditya0610

3 months ago, # |

Enjoyed the Round!! Thanks

→ Reply

21Cash

3 months ago, # |

Loved the round. Will be one of my fav cf rounds. Great algorithmic problems. Truly Loved it.

→ Reply

https://codeforces.me/contest/2000/submission/276288423

3 months ago, # ^ |

ABCDE is good, probably comeback for FGH tomorrow. There's so many positive comments on them I will try to upsolve them for 1-2 days.

→ Reply

JasonMendoza2008

3 months ago, # |

← Rev. 3 →

+13

Truly beautiful problem F. Spent the whole contest on it and could only upsolve it. It truly made my day, thank you myav, Gornak40, senjougaharin and Vladosiya!!

→ Reply

rsFalse

3 months ago, # |

-29

Hint for D:

Hint

→ Reply

khalit7

3 months ago, # |

GOT wrong answer in problem A because the input included spaces!

I got a runtime error in Problem A of this contest because one of the test cases was "10 " (10 with a space). is this intended ?

I couldn't see how the problem description explains this?

but overall the contest was great!! would appreciate it if someone can clarify the situation with problem A

Thanks!

→ Reply

Snoudin

3 months ago, # ^ |

It is not necessary intended, but in general you should write code that allows extra spaces, tabs, etc unless statement clearly states about exact gaps. I.e. "integers in lines are separated by a single space".

The only reason tests are not always being checked on such formatting is because code that fails on them is usually bad code.

→ Reply

LMeyling

3 months ago, # ^ |

When using input = sys.stdin.readline you always get an \n at the end. When using int() or .split() this gets dropped, but for strings it stays there. You can see this if you do print(list(input())).

To avoid this you can just do: input = lambda: sys.stdin.readline().rstrip()

→ Reply

ryucc

3 months ago, # |

Having the discussion stream start before the open hacking phase ends feels wrong. But I guess most people don't hack anyways.

→ Reply

delwar_03_

3 months ago, # |

← Rev. 3 →

Wasted 20mints in F implementing Binary Search :(

BTW problems were good tbh :p

→ Reply

Ami_Nul

3 months ago, # ^ |

same :)

→ Reply

riteshfyi

3 months ago, # |

Problem C, States that the value of m<=10^5 and n<=10^5 and t<=10^4, the time limit is 2seconds, then how is the solution of O(t*m*n) being accepted??

→ Reply

forgot_past

3 months ago, # ^ |

It is guaranteed that the sum of n across all test cases does not exceed 2⋅10^5 , and that the **sum of the lengths of all strings does not exceed 2⋅10^5** .

→ Reply

Heisenberg2020

3 months ago, # ^ |

-9

Those'll get hacked. Just wait!

→ Reply

gareeeeeeeeeeeeeeeev

3 months ago, # |

how to solve the problem E?

→ Reply

Bnahmad23

3 months ago, # ^ |

The limits on N*M <= 200,000 means you can traverse the grid.

Traversing the grid lets you calculate how many sub-rectangles would contain each position.

Thus you assign the larges values to the position repeated most

→ Reply

gareeeeeeeeeeeeeeeev

3 months ago, # ^ |

thanks

→ Reply

cookies..

3 months ago, # |

Where's the editorial.. why they have not uploded it yet :(

→ Reply

think_man

3 months ago, # ^ |

Hacking phase is on for next 9 hours, Maybe thats why.

→ Reply

RapidSaurabh

3 months ago, # ^ |

I think it will be uploaded after hacking phase finishes.

→ Reply

WOWWA

3 months ago, # |

Can anyone enlighten me as to why this doesn't work?

→ Reply

Christine_Davain

3 months ago, # ^ |

Consider $$$n = m = 100$$$, and $$$k = n - 1$$$. This way not so many squares will fit in the rectangle, so for, say, $$$i, j = 50$$$ the count is incorrect.

→ Reply

WOWWA

3 months ago, # ^ |

ah ok thanks sad i didnt see it during contest XD

→ Reply

srrow_xhr

3 months ago, # |

any one solve problem F in greedy and priority ? I debugged according to this idea, but did not pass，and I just want to know whether this idea is legal ?

→ Reply

Abdo_Ibrahim7

3 months ago, # |

← Rev. 2 →

the statements of problems is not clear i take long time to understand it, and i miss some to get

→ Reply

3 months ago, # ^ |

seems like skill issue

→ Reply

whyalwaysmezzz

3 months ago, # ^ |

you talk too much while being a specialist

→ Reply

3 months ago, # ^ |

while you talk too much for being skipped in epic div1+2

→ Reply

3 months ago, # ^ |

← Rev. 2 →

Id rather be specialist, than cheat to expert. also how are you not ashamed to comment when you got skipped last contest?

→ Reply

AloneMusk

3 months ago, # |

Can someone explain me why this code for H is giving TLE.

For every segment which is not present in the array, I am storing its size and the index where the segment begins from. I am storing the best (minimum index) in an array and building a minimum query segment tree on it, and I am also storing all other indexes in a set corresponding to its segment size to handle the '-' and '+' queries later.

Next, for each '+ x' or '- x' query, I am updating the segment tree and the map according to the new segments formed and unformed. Here, I am doing insertions and deletions on sets whose complexity is O(logn) time. And for the '?' query, we need a segment of size atleast k and with minimum index, which I am finding using the segment tree, which should be O(logn).

So, the overall time complexity of my code should not be worse than O(nlogn + qlogn).

Sorry, if someone is going through my ridiculously chaotic code.

→ Reply

_Kee

3 months ago, # ^ |

Your create a $$$2 \cdot 10^6$$$ element vector for every test case, and there're $$$10^4$$$ cases, which are obviously too many.

→ Reply

AloneMusk

3 months ago, # ^ |

Thanks to point it out, can't believe I missed this.

→ Reply

__Waled

3 months ago, # ^ |

← Rev. 2 →

I came up with the same logic. Carelessly, not paying attention for the high constant factor. I tried the same logic with coordinate compression technique, and now waiting for the endless system testing and queue :<

P.S it got Accepted

→ Reply

InfinityX

3 months ago, # |

In Problem E, why can the same code be Accepted in Java 21, but result in Time Limit Exceeded (TLE) in Java 8?

→ Reply

Steven-_-AbuAlkhair

3 months ago, # |

how solutions with O(n*k*100*100) passes in F?

→ Reply

3 months ago, # |

+14

My G hack explanation: https://codeforces.me/blog/entry/132653

→ Reply

eeshaansethia

3 months ago, # |

Why didn't I get a rating after this contest?

→ Reply

Mohit_Kukreja

3 months ago, # ^ |

It is yet to be tested again. Wait for some 10 hours more xD

→ Reply

3 months ago, # |

Can E be solved when the constraints of n and m are order of 10^9 ?

→ Reply

Mohit_Kukreja

3 months ago, # ^ |

I believe atleast a traversal of N*m is required so, it wont really be possible in my opinion.

→ Reply

Dark_knight1234

3 months ago, # ^ |

its works for NMlog(NM) since N & M both are 10^5

→ Reply

3 months ago, # ^ |

I do believe it can be solved with some math magic... which will bring this E to at least G-H level (waiting for editorial to show us the math magic)

→ Reply

Dark_knight1234

3 months ago, # |

← Rev. 2 →

When will the ratings be published?

→ Reply

_A_K_47

3 months ago, # ^ |

is system testing done or only hack phase finished yet??

→ Reply

Dark_knight1234

3 months ago, # ^ |

system testing is going on now.

→ Reply

123ducanhanhduc123

3 months ago, # |

I solved 3 problems but why I don't have a rating? I'm a newbie.

→ Reply

https://codeforces.me/contest/2000/submission/276259792

3 months ago, # ^ |

the ratings haven't been published yet, wait a little while

→ Reply

123ducanhanhduc123

3 months ago, # ^ |

Thanks!

→ Reply

blue_m00n_eoy

3 months ago, # |

I'm trying to upsolve the Problem D — Right Left Wrong. Problem is my submission 276359457 is giving TLE while a similar logic, but one using 1-based indexing is getting accepted and I'm unable to understand how. 276137058

Can someone please help me understanding why it might be the case.

→ Reply

towley

3 months ago, # ^ |

in your code, findRangeSum() is O(r — l + 1) for range [l, r] while the latter code uses prefix sum to provide O(1) lookup

→ Reply

blue_m00n_eoy

3 months ago, # ^ |

Hi Towley. Thanks for taking out the time to check my submission. But I too have used prefix sum to find out the range sum.

int findRangeSum(vi sum, int l, int r){
    int ans = sum[r];
    if(l > 0){
        ans -= sum[l-1];
    }
    return ans;
}
int _find(vi &arr, string &str){
    vi cSum = arr;
    for(int i=1; i<n; i++){
        cSum[i] += cSum[i-1];
    }
 ......
 ......
    ans += findRangeSum(cSum, i, j);

}

Would be great if you or somebody can take another look at it. This is really driving me crazy.

→ Reply

tangdong_

3 months ago, # ^ |

this is because you're passing vector as a whole, instead of as a reference in findRangeSum, which creates a new vector hence it'll take O(n) instead of O(1)

→ Reply

blue_m00n_eoy

3 months ago, # ^ |

You are a saviour, boss. I can't thank both of you enough. Also learnt something new about c++ vectors. :-)

→ Reply

Rohan217

3 months ago, # |

← Rev. 6 →

A not so elegant brute force solution also exists for problem G.

We can run a Dijkstra from the nth intersection (Using only bus service). After the Dijkstra calculates the minimum distance to all the intersections, we take those intersections which are at a distance <= (t0 - t2). This ensures that we are not using bus services during our phone call. From these selected intersections, we can run a multisource Dijkstra (This time we can only walk through the routes). We repeat the same process of selecting some specific nodes, and then run a third Dijkstra which corresponds to the bus route taken before the phone call.

My implementation breaks the above scenario into two cases. Case 1: We use the bus service first, then we walk along a route, and then we again use a bus service. Case 2: We use the bus service first, then we walk along a route. However a clever implementation won't require us to do so.

Link to Implementation: 276362277

→ Reply

techwiz911

3 months ago, # ^ |

Thanks for the writeup, this was indeed my approach as well. Your 2nd case is redundant though as the problem ensures that l1<l2 for all edges, meaning its always faster to take the bus compared to walking. Here is a (codewise) efficient implementation 276460009

→ Reply

Rohan217

3 months ago, # ^ |

Thanks for pointing it out!

→ Reply

jaitrika

3 months ago, # |

can some pls tell me why my code for D fails?

276271810

→ Reply

wowoto

3 months ago, # ^ |

← Rev. 5 →

https://codeforces.me/contest/2000/submission/276366110 Overflow. "i < j must also be satisfied in the if condition."

→ Reply

jaitrika

3 months ago, # ^ |

got it thanks man!

→ Reply

zhanbh07

3 months ago, # |

could someone tell me where my submissions are going wrong? thanks

https://codeforces.me/contest/2000/submission/276239337

→ Reply

SoonOOv

3 months ago, # ^ |

For your B submission you put an if statement specifically for cases when n = 1 or n = 2, this is fine, but what's wrong is that you are putting it before you take the next input which is the array of passenger, so for example if the case were like this:

3 1 2

It should output "YES" for the first and "NO" for the second, but since the first have n = 1, you printed "YES" before actually taking the next 1, so for the second one you take that n = 1 (and printed "YES" again) when it should've been n = 3.

→ Reply

zhanbh07

3 months ago, # ^ |

i see. thanks for pointing that out!

→ Reply

sarodesparsh

3 months ago, # ^ |

← Rev. 2 →

Basically, you are outputting NO multiple times per test case. The 2nd for loop shouldn't run if already flag = 1 from 1st loop.

→ Reply

zhanbh07

3 months ago, # ^ |

oh no, i see. a silly oversight. thanks!

→ Reply

sarodesparsh

3 months ago, # |

← Rev. 3 →

[deleted comment]

→ Reply

Asacker

3 months ago, # |

Is this rated , if yes then why doesn't it shows on my profile btw this was my first contest . Does anyone know about this

→ Reply

i_would_win

3 months ago, # ^ |

it will take 10-12 hours more I guess because thats what happens in div 3 and div 4

→ Reply

Asacker

3 months ago, # ^ |

Oh ok thanks

→ Reply

276286062 276283663 276290958

3 months ago, # |

See #4, #5, #6 in the official list:

276277048 276273889 276281919

The cheating is getting out of control, becoming too widespread, and taking the fun out of participating in these contests. Anyone found cheating should not just be skipped for that contest but be life banned from this platform. If that is too harsh, at the very least, put their rating to 0, and let them start again. The current system is too lenient and encourages cheating.

→ Reply

3 months ago, # ^ |

Cheater detection phase is after the contest. Just wait a little and be patient.

→ Reply

3 months ago, # ^ |

Ok, thank you to explain.

→ Reply

3 months ago, # ^ |

i've started giving contests quite recently, and i was wondering, how much of an impact do the cheaters actually have on the ratings after the cheating detection phase is over? is it a huge difference? i don't expect more than 5% people to be cheating honestly so i'm not sure

→ Reply

3 months ago, # ^ |

Still not fixed.

→ Reply

3 months ago, # ^ |

What's with the hurry? It usually takes a few days until the admins do the plag check, then the caught ones' solutions will be skipped, and once in a few weeks the admins will rollback recent rating changes and finally unrate them. It's not something that's done just immediately.

→ Reply

3 months ago, # ^ |

Ok, thank you.

→ Reply

3 months ago, # ^ |

← Rev. 2 →

fr man, plus cp is supposed to be a wholesome sport where everyone encourages each other to get better, and cheaters aren't just ruining the sport they are making it toxic too. if i had a +1 rating every time i saw racist comments i'd be tourist lmao

→ Reply

tnatsnoc

3 months ago, # |

Why do man people make comments about cheaters Who could explain that to me？Thanks！

→ Reply

3 months ago, # ^ |

Because Codeforces had an enormous increase in cheating in the last few months, so much so that nowadays there are up to a few thousand cheaters per round. Also, some people are cheating all the way up to International Master.

→ Reply

mittalmohit2003

3 months ago, # |

I gave yesterday's div 3 contest but now I'm unable to see my submissions.

→ Reply

GongKai

3 months ago, # |

So happy. I will be blue after this contest

→ Reply

vidux

3 months ago, # |

Just wandering about problem E if there is a better way of calculating how many times subsquares overlap in a cell that runs faster than O(n*m). Was thinking of simply calculating how many cells that are covered by x subsquares exist but I dont know if its possible. Also whats the name of this concept (wandering since Ive encountered similar problems on math competitions, and had to compute them by hand)

→ Reply

ZengDingjun_EggArmy

3 months ago, # |

-17

I will be rank 1st and beat tourist and jiangly in this contest

→ Reply

wutDing

3 months ago, # |

why Time Limit Exceeded 276190376

→ Reply

vidux

3 months ago, # ^ |

Since the testcases cant be seen just yet I would guess that it got TLE because you used unordered_map. It is generally faster than a regular map but worst case is worse. So somebody probably made a hack to exploit this fact. Read https://codeforces.me/blog/entry/62393 or just use the regular map

→ Reply

wutDing

3 months ago, # ^ |

thanks,i use unordered_map since i think regular map will sort(log(n)) and i dont need sort.however it TLE.

→ Reply

DonSilvio

3 months ago, # |

Sadly, I failed to write a good "key not in the map" check in C and got hacked, but during the upsolving, I came up with a rather elegant way of circumventing the failure: check out the code — I use a wrapper struct to define a default int value: 276398448.

→ Reply

Nick9

3 months ago, # ^ |

Kinda nuts it wasn't in a pretest, but hard to blame someone other than myself (my solution was hacked too). I think it's possible to just add 1E9 + 1 to received number.

→ Reply

3 months ago, # ^ |

I mean a .find() function exists though...In C++20 there is also a .contains() function

→ Reply

DonSilvio

3 months ago, # ^ |

In this particular case it would be much less elegant and had to be put in several areas of code which would make it harder to comprehend.

→ Reply

https://codeforces.me/contest/2000/submission/276189043

3 months ago, # ^ |

Uhhh, that I don't know, I used .find() and I don't think it's less "elegant" than writing a new wrapper struct or something

This is that part of my code

auto it = atos.find(a[i]);
if (it != atos.end() && it->second != s[i]) {
    return false;
}

auto it2 = stoa.find(s[i]);
if (it2 != stoa.end() && it2->second != a[i]) {
    return false;
}

atos[a[i]] = s[i];
stoa[s[i]] = a[i];

→ Reply

Double2D

3 months ago, # |

https://codeforces.me/contest/2000/submission/276220371 he copy code in : https://www.youtube.com/watch?v=hZxQUtFcjTQ

→ Reply

manideepreddy666

3 months ago, # |

← Rev. 2 →

I participated in this contest and solved 1 problem and it was accepted during the contest, but it showing In queue in My submissions

→ Reply

sbhm_prksh

3 months ago, # ^ |

Because system is testing all the submission once again after the completion of hacking period.

→ Reply

Double2D

3 months ago, # |

https://codeforces.me/contest/2000/submission/276220371 he copy code in : https://www.youtube.com/watch?v=hZxQUtFcjTQ

→ Reply

sapkota3001N

3 months ago, # |

MY rating is not been updated?

→ Reply

weiron_RX

3 months ago, # |

← Rev. 2 →

I got runtime error, probably because I am uncorrectly wrote condition when string size is not equal to array size (276152133). But there is a test in the samples which have a string shorter than array size, but my solution passed it. Why?

→ Reply

Wrking_on_procastination

3 months ago, # |

When will ratings get published?

→ Reply

weiron_RX

3 months ago, # ^ |

only when the system testing is over

→ Reply

k200154

3 months ago, # |

can someone explain test cases 4 and 7 of G? I am getting 79 and 1 but the actual answers in both cases are 80 and 2 respectively.

→ Reply

WrathionTBP

3 months ago, # |

Would love to know why this greedy approach doesn't work on problem F.

276333164

The idea was to calculate the max cost to obtain the max score on each rectangle, then sort the cost (ascending order) and in case of two rectangles with the same cost, sort by score (descending). Then binary search the score k (obtaining the position i), and check if the sum of scores from of the sorted rectangles from 0 to i is able to obtain k or k+1, then the cost is the cost from the sorted rec 0 to i. If the score from 0 to i result is greater than k+1, then the answer is from 0 to i-1 + intelligent score points in the i-th rectangle.

It's giving WA on test 3, but can't see the case that is failing, if someone has an insight why this won't work or need more info LMK.

(I know it should be solved by DP, but was sure that this greedy approach should work :c)

→ Reply

iammiddha

3 months ago, # |

Anyone else getting runtime error on testcase 16 in D problem after system testing

→ Reply

WOWWA

3 months ago, # |

Can anyone explain why this TLEs?

→ Reply

The_Dragon_Warrior

3 months ago, # ^ |

← Rev. 2 →

check out the solution: https://codeforces.me/contest/2000/submission/276177969

Since there are 3 conditions, try to write 3 separate section of code. If 1st condition doesn't match no need to think about 2 and 3. Just stop if a condition fails. This way you can optimize the solution.

→ Reply

N-I-H-A-L

3 months ago, # |

← Rev. 5 →

Vladosiya, 276250408 During contest, I submitted this code and got runtime error with exit code -1073741819, and just now, I submitted the EXACT SAME CODE, 276428579 and it got accepted. Please help

edit: later it got same runtime error again T_T

but not on the same test case as earlier. This time it makes sense because of out of bounds, but how come it earlier fail on test 15 and now it passes it?

Can someone please tell me what is that error code and why does it randomly occur at any time?

→ Reply

Aditya3001

3 months ago, # ^ |

WTF!!!!

→ Reply

b_a_d_m_a_n

3 months ago, # ^ |

Consider the case where all letters are 'R'. Your code will access an out of bounds array index which is undefined behaviour.

→ Reply

N-I-H-A-L

3 months ago, # ^ |

Makes sense, why did it give error in test 15 earlier, but now it passed on that and gave error on 16?

→ Reply

b_a_d_m_a_n

3 months ago, # ^ |

Luck. Just because an out of bounds array index is accessed doesn't mean that the program is guaranteed to crash immediately at that point. In some cases your program managed to reach the end without crashing and return the correct value but in other cases your program read a bad memory address which had no permissions to read and thus crashed before being able to terminate correctly.

→ Reply

i_would_win

3 months ago, # |

where is editorial??

→ Reply

1nvince

3 months ago, # |

Could you please tell me why I was hacked in question C? I think my time complexity is in line with the regulations, it should be O(n * m * logn), where n * m <= 2e5. Here's my answer: https://codeforces.me/contest/2000/submission/276152431

→ Reply

harshith_04

3 months ago, # |

Why are submissions being picked randomly from the queue?

→ Reply

Rostcraft

3 months ago, # |

← Rev. 4 →

~~In problem C only lowercase latin letter are allowed, why exact same solution that uses unordered_map works, while original one with vector doesn't?~~

Edit; I forgot that elements of the array can be -1.

→ Reply

k200154

3 months ago, # |

What's wrong with this solution for F?

→ Reply

21Cash

3 months ago, # |

Will be a memorable 2000th CF Round for me. I finally became a specialist. It really feels great.

→ Reply

raghav275

3 months ago, # |

Can anyone help me understand why it is throwing TLE?

https://codeforces.me/contest/2000/submission/276439386

→ Reply

Shoeib

3 months ago, # ^ |

use map instead of unordered_map, unordered_map with random data/bad hash function cause many collisions that leads to O(n) for a single lookup

→ Reply

raghav275

3 months ago, # ^ |

Thanks! This costed me 2 penalties lol. But the same code in java threw tle as well

→ Reply

Cp_Geek

3 months ago, # ^ |

Thanks, even I got TLE on using unordered_map :(

→ Reply

olegmak

3 months ago, # ^ |

unordered_map is fine when used with random data, but it can be hacked by crafting a sequence of inputs that all hash into the same bucket. Read how to protect yourself from such hacks: https://codeforces.me/blog/entry/62393

→ Reply

Manish_Jangir

3 months ago, # |

can anyone pls tell why is this code getting runtime error? Problem D

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rf(i,a,b) for(ll i=b-1;i>=a;i--)

/* When a man learns to love he must bear the risk of hatred */
/* I don't know WTF am I doing */
/* Now I hate You */

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t;cin>>t;
    while(t--){
        ll n;cin>>n;
        vector<ll> a(n);
        f(i,0,n){
            cin>>a[i];
        }
        string str; cin>>str;
        vector<ll> leftsig,rightsig;
        f(i,0,n){
            if(str[i]=='L')leftsig.push_back(i);
            else rightsig.push_back(i);
        }
        ll left = 0;
        ll right = rightsig.size()-1;
        ll sum = 0;
        
        while(left<leftsig.size() && right>=0 && leftsig[left]<rightsig[right]){
            sum += accumulate(a.begin()+leftsig[left],a.begin()+rightsig[right]+1,0LL);
            left++;
            right--;
        }
        cout<<sum<<endl;

    }   
    
}

and also any issue with this approach for the question if you find any.

→ Reply

Thunder_strom007

3 months ago, # |

Can anyone tell me why this code giving me TLE in problem H https://codeforces.me/contest/2000/submission/276365420

→ Reply

harshith_04

3 months ago, # |

You don't need to learn Segment Tree to solve H, here's my submission 276496494 that runs in 1200ms :)

→ Reply

ckrian__223

3 months ago, # |

For Problem F, Binary Search + DP? If I can score >= K points for some "mid" amount of operations, then i can Score >= K points for all >= mid amount of operations. This led me to think Binary search, now the only part left is the question "Can i score >= K points with this mid amount of operations?". This is where I am stuck. Anyone with the same approach? welp

→ Reply

SOMANSH24

3 months ago, # |

← Rev. 2 →

In problem B "Seating in a Bus", whenever I try to run individual test case, it is giving me desired answer but when i run all test case, it is failing in the last testcase.Can someone point out when i am making mistake-276490271 Thanks!!

→ Reply