Hello! Codeforces Round 966 (Div. 3) will start at Aug/13/2024 17:40 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of **open hacks**. After open hacks all accepted solutions will be rejudged on successful hacks.

You will be given **6-8 problems** and **2 hours and 15 minutes** to solve them.

Note that the **penalty** for the wrong submission in this round is **10 minutes**.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participant of the third division*, you must:

- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Problems have been created and written by our team: myav, Gornak40, senjougaharin and Vladosiya.

We would like to thank:

MikeMirzayanov for help with ideas and Polygon and Codeforces platforms.

FairyWinx, TheScrasse, Be_dos for red testing.

irkstepanov, Kirkon, ikrpprppp, Kaey, Bruteforceman for yellow testing.

trgt26 for green testing.

Good luck!

**UPD**: Editorial is out.

Vladosiya orz

only purple and yellow testing?

why dont u ask them if they need cheater testing

yeah cuz you want to cheat as a tester

yeah cuz they dont want cheaters like you testing

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

why would you want to test as a cheater

you can go test a div 5

yeah, cuz cheaters<newbies

IoI will always be a dream for cheater's

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

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)

damn this is down bad

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

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

oh you meant blatant racism, understood. thanks!

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)

System testing is going on so view after that

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.

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 .

are you consistent at div2Cs yet

No , 60 % solvable in general .

Bhai mujhe bhi tips batadiyo ****

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

Expect to solve at least 4

Hope to solve at least 5 and get 1250+ rating

UPD: Solved ABCDE

Good Luck

NOICE

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

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!

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...

NOICE, dude!

how so pro?

congrats to solve 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.

why you don't join contest

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.

welcome a new -100 (¬_¬)

Wish I can get Expert on this contest!

lol guys you probably need some more testers)

We had the whole night to fix this :)

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

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

hope for Asuna_Yuuki

hope for Salah7_a

As a participant, DangKhoizzzz orz__

hello

ily bbg

OMG! Another Vladosiya round !

wapis blue banna hai mujhe.. (hopefully)

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

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

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

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 milestoneHope to solve 5 problems today. Good luck everyone!

I hope through this game, I can reach the 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

My rank doubled over the last 20-30 minutes.

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 :)

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

2000 on F ???

oh mb i thought u meant E

ah nvm

it is 1400, still huge amount for a div 3

Well this round feels like true Div 3.

Good balanced contest.

Nice contest, but cheaters ruined it again

yeah

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

6

1 1 1 1 1 1

LLRRLR

Your code will be fine with the minimum change.

Code276325664

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

disagree, it was pretty clear.

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

Finally I solved 4 problems

H : Ksyusha and the Loaded Setcan 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 videoDefine $$$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 :

Sadly, no such data structures exist. But we faced this same issue in

G: Penaconyfrom 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 fromAtcoder Librarysuffices, usage of which I have discussed in the video above.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))$$$.

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)$$$.

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

Any hints on F?

DP

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

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?

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.

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$$$

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

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.

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

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.

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.

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

Your output: $$$36$$$

Correct output: $$$33$$$

Okay got it. Thanks

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.

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

Codenvm, figured it out.

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

so sad I don't have enough speeeeeeed

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

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

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

Any counter test case?

Need to use long for prefix sum array

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.

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 :(

use

`#define int long long`

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

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.

Oh, Okay, thanks.

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

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

can you explain the first test case please .

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

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

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.

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! :)

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

It is to be solved using knapsack.

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?

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

Thanks

Please help me find out why submission 276251214 in

C++17 (GCC 7-32)Runtime Error but same code submission inC++20 (GCC 13-64)Accepted?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

Thank you so much.

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

276296054

Thank you so much.

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

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

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).

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

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!

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

Coding until the last minute

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

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!

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

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

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)

2d prefix sum :P

bruh I used brute force and got AC in 343 ms

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)

2D differance array.

u can calculate weight of each cell by pure arithmetic

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

yeah, that's what I did

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..

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

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.

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

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).

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.

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

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

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

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.

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

oh I did not notice that. Makes sense.

Amazing contest! Problems were true Div3 rated.

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

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

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

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

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

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.

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 .

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.

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.

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.

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 typeActually 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

I have two questions for you:

PS:

I'm not accusing anything here; I'm just genuinely curious.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.

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!!!

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"?

@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

Did anyone else use DSU for problem C lol?

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

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

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

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

common

No, the picture was edited later in the contest

the moment announcement was sent there was 6000 submission

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.

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

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.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

waitat 4th city.phone call is 5-6, not 5-7

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 ?

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

Another one 276288851

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

Spoilerwhy 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

This thing right?must use dp

explain please how to get 35 in last test case

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.

Sure, here you go!

Hackforces

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 276276752probably clueless cheaters

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?

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

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

HACK ALL OF THEM!

276275956 this one also lmfao

Enjoyed the Round!! Thanks

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

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.

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!!

Hint for

D:HintE.Hint for E:

HintB.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!

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.

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()`

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

Wasted 20mints in F implementing Binary Search :(

BTW problems were good tbh :p

same :)

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??

`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** .`

Those'll get hacked. Just wait!

how to solve the problem E?

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

thanks

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

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

I think it will be uploaded after hacking phase finishes.

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

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

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.

ah ok thanks sad i didnt see it during contest XD

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 ?

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

seems like skill issue

you talk too much while being a specialist

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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)

When will the ratings be published?

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

system testing is going on now.

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

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

Thanks!

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.

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

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.

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

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)

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

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

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

Thanks for pointing it out!

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

276271810

https://codeforces.net/contest/2000/submission/276366110 Overflow. "

`i < j`

must also be satisfied in the`if`

condition."got it thanks man!

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

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

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

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:

2

1

1

3

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.

i see. thanks for pointing that out!

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

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

[deleted comment]

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

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

Oh ok thanks

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

276286062 276283663 276290958

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.

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

Ok, thank you to explain.

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

Still not fixed.

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.

Ok, thank you.

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

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

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.

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

So happy. I will be blue after this contest

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)

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