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 milestone
Hope 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.
276325664
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 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 :
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.
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.
Can you pls check where am i going wrong in my implementation. Thanks!
nvm, 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 longWill 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 in C++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 longin your code so you should know that#define ll long longalso 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 wait at 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.
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
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 276276752
probably 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:
E.
Hint for E:
B.
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.readlineyou always get an \n at the end. When usingint()or.split()this gets dropped, but for strings it stays there. You can see this if you doprint(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 < jmust also be satisfied in theifcondition."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
why Time Limit Exceeded 276190376
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.net/blog/entry/62393 or just use the regular map
thanks,i use unordered_map since i think regular map will sort(log(n)) and i dont need sort.however it TLE.
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
structto define a defaultintvalue: 276398448.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.
I mean a .find() function exists though...In C++20 there is also a .contains() function
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.
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
https://codeforces.net/contest/2000/submission/276220371 he copy code in : https://www.youtube.com/watch?v=hZxQUtFcjTQ
I participated in this contest and solved 1 problem and it was accepted during the contest, but it showing In queue in My submissions
Because system is testing all the submission once again after the completion of hacking period.
https://codeforces.net/contest/2000/submission/276220371 he copy code in : https://www.youtube.com/watch?v=hZxQUtFcjTQ
MY rating is not been updated?
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?
When will ratings get published?
only when the system testing is over
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.
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)
Anyone else getting runtime error on testcase 16 in D problem after system testing
https://codeforces.net/contest/2000/submission/276189043
Can anyone explain why this TLEs?
check out the solution: https://codeforces.net/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.
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?
WTF!!!!
Consider the case where all letters are 'R'. Your code will access an out of bounds array index which is undefined behaviour.
Makes sense, why did it give error in test 15 earlier, but now it passed on that and gave error on 16?
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.
where is editorial??
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.net/contest/2000/submission/276152431
Why are submissions being picked randomly from the queue?
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.
What's wrong with this solution for F?
Will be a memorable 2000th CF Round for me. I finally became a specialist. It really feels great.
Can anyone help me understand why it is throwing TLE?
https://codeforces.net/contest/2000/submission/276439386
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
Thanks! This costed me 2 penalties lol. But the same code in java threw tle as well
Thanks, even I got TLE on using unordered_map :(
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.net/blog/entry/62393
can anyone pls tell why is this code getting runtime error? Problem D
and also any issue with this approach for the question if you find any.
Can anyone tell me why this code giving me TLE in problem H https://codeforces.net/contest/2000/submission/276365420
You don't need to learn Segment Tree to solve H, here's my submission 276496494 that runs in 1200ms :)
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
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!!
out of bounds access. first of all, you should seat[i]--; since your array is 0 indexed and the input is 1 indexed, and then for seat[i]=0 or n-1, make edge case checks. (or make a 1 indexed array with 1 extra space to the right so you dont have to make those ifs).
When can we expect the rating changes to come?
Hello!
I had submitted problem D and it was correct. I didn't copy from anyone. 5 hours ago cf messaged me that a submission significantly matches with my solution. It was a guy whose account was Nikhilj007. Then, I read his submission and found that our codes are different but there is some algorithmic similarity. I don't even know this guy and I don't even know how this similarity happened. I strongly affirm that it is nothing but a coincidence. Please give me back my "AC"s in this contest(which are now showing 'skipped') and don't penalize both of us.
Sincerely, Debanjon Roy
Handle: deanjon_roy
What is the 2.4065th testcase in E problem or whats wrong in this solution? https://codeforces.net/contest/2000/submission/276969819
Hi Codeforces Team,
I recently received a mail about similarity between my submission and those of users codeRahul and Shivamv_99 for the problem 2000D. I want to clarify that I do not know these users and did not copy my code from any source. My solution was independently developed using a simple two-pointer approach. The use of generic variable names further contributed to any incidental similarities. I respectfully request a reconsideration and accept my solutions. Please don't penalise us for what is an unintended coincidence.
Hi Codeforces Team, MikeMirzayanov
I recently received a mail about similarity between my submission and only one single user Ruang_Feng/276252192 relating to problem 2000E - Photoshoot for Gorillas. I want to clarify that I do not know who he is, did not copy my code from any source or wrote code on any platform like ideone.com(As you can see my consistent template which is generated using a bash script). The use of variable names further contributed to any incidental similarities which is copied from problem statement. The 10-line solution is author intended and many many other users have the same ideas. I respectfully request a reconsideration and accept my solutions. Please don't penalise us for what is an unintended coincidence.
why is this contest not showing
The ratings are being calculated again. Don't worry they will come back either today or tomorrow.
Thanks.
Sorry but it was a coincidence .. I published my code on ideone.com that's why the problem has occured. I had no intension to share it to anyone .
Contest 2000 in link and problem and contest tag.
Congrats!!