Hello Codeforces!
I have the pleasure of inviting you to participate in Codeforces Round 960 (Div. 2), which will start on Jul/20/2024 17:35 (Moscow time).
The problems were prepared and authored by wuhudsm.
You will be given 6 problems and 2 hours to solve, one of the problems is divided into two subtasks.
One of the problems may be interactive. So, please refer to the guide on interactive problems if you are unfamiliar with them.
I would like to thank:
- Akulyat for coordinating the round;
- BurnedChicken for the only LGM testing;
- physics0523, liympanda, culver0412, Dominater069, TheScrasse, Andreasyan,satyam343 for GM and IGM testing;
- Error_Yuan, IanISam, Little_Sheep_Yawn, NemanjaSo2005, aufannn, IceKnight1093, and pavlekn for M and IM testing;
- Muhammad-Saram, vikram108, Proelectro444, htetgm, n0sk1ll, and AkibAzmain for CM testing;
- kHarsh3715, beyondpluto, larush, SolCollider, Banis,Abhishek_Srivastava, Think_Only_Once, chromate00, and astilate for Expert testing;
- md_nihal, HexShift, and dazlersan1 for Specialist testing;
- yash_04, and ishaandas1 for the Pupil testing;
- DARKPAST, and Binary_Thinker for the Newbie testing;
- tibinyte2006 for the Illegal newbie lying face testing;
- MikeMirzayanov for the great Codeforces and Polygon platforms;
- CHATGPT for solving $$$0$$$ problems : ) ;
- And at last but not least, You for participating in the round!
Fun fact
Good luck and have fun!
Score distribution: $$$500 - 1000 - 1500 - 1750 - (2000+750) - 3000$$$
UPD:
Congrats for the winners!
Div 2:
Div 1+Div 2:
As a blue tester, my color changed two times while testing the round :)
Can't wait for it!!
HOW DID I MISS THE MOST ORZ vikram108 in the testers!!!!!
As a tester, wuhudsm orz
As a participant, wuhudsm orz
As a participant, Abhishek_Srivastava orz
Orz Abhishek_Srivastava sir
As a tester ,I believe you should definitely give this contest. All the best!!
thank you for letting know CHATGPT solved 0 problem!
As a tester, I will be missing the chance to give this contest :(
Btw, this is my first round as a tester. Hope everyone enjoy the problem set.
will be gr8 if can solve 3 to 4 problems this time, will try to get under 3k rank
In the last contest, I lost 160, and I hope to recover it.
last contest was hard
you can recover this round!
did he?
NO:(
As a tester, I almost accidentally registered for this round. Hope you have fun :)
I just unregistered. XD
As a participant, very excited to give this round tested by larush
CHATGPT for solving 0 problems : )Lol, it would be nice if every contest is also tested on GPT to reduce the chances of cheaters using such tools
Using chatgpt is not cheating
Yeah that's true for debugging and stuff, but sometimes, rarely, the whole question gets solved by GPT, I've seen people in my college just copy paste the question and get an answer, still it's more common on LeetCode.
its still not cheating (on cf atleast), just bad problem setting
True, makes sense
Tbh, I was not able to understand 136A - Presents question language and its test cases literally!! And i ask gpt to explain it to me in simple term with example without code...
My question is- Is this a bad practice??paramveer5404
Using GPT still feels like a grey area to me. I also use it to sometimes understand the question properly or debug stupid errors like initialising an array before taking input or something like that. I have asked my seniors who are Experts and CMs,they also say that it's okay to use GPT for the above purposes but they suggest to avoid spending too much time on GPT in hopes of getting an answer.
But one of my friend who uses a lot of GPT once got skipped in a contest(I'm certain he did not use telegram etc.), maybe coz a lot of people would use the same GPT solution leading to a Skipped.
So I feel it's okay to get things debugged or to understand the question but copy pasting code from GPT feels risky.
But I feel that I am not that experienced enough to conclude something.
What are other people's thoughts on this? Anyone wants to weigh in, in the comments.
I'm tired of wishing too much
Bro is not the man who never quits
No bro this is a trap to get upvotes xD
I hope for you to reach 1750 this round <3
Thanks <3 i hope for you to reach expert this round
As a tester, I failed to solve any problems.
As a tester, I found that GCD(score distribution)=250k for k>=1.
As a tester, I disappeared from the scoreboard :(
i would happy if codeforces avoid the contests on saturdays which actually clash with lc biweekly contest
the question becomes: does it matter if you are happy?
biweekly contest is clashing with codeforces
who tf cares about lc
Cf>>>lc
im really hoping for 1434 rating this time...
As a tester, I did disappear from the standings.
As a tester, I also disappeared from the scoreboard :(
(Even hadn't finished all the problems until yesterday lol.
I love some of the problems so much and hope you enjoy!)
As a tester, I wasn't removed from the standings during testing.
As a tester, 111001110000101100011100100000011011.
you mean 62,020,241,435?
6/20/2024 14:35
BTW shouldn't it be 7 for July.
Proof tester can be wrong.
Oh yeah, sorry.
Testers are humans too, anyway.
Wrong encryption results in wrong decryptions.
Testers, please test it as well.
As a tester I want to give a hint for this round
participate in this round
Definetly. Without fail, I will participate
Thanks for your hint.
As a tester, I highly recommend you to participate in the contest. Problems are interesting!
First time tester in an official round, testing is fun.
SURELY... i wont spend an entire hour on C
or come up with a wrong proof on D
OR get trolled by E's problem statement
As a tester, wuhudsm has put a lot of effort to make sure that the problemset is balanced.
Agree. wuhudsm orz.
As a participant, I think a space is missing in the title.
Upd: fixed :)
This contest timing(8 — 10) is clashing with leetcode biweekly(8 — 9:30). I am Indian (GMT + 5:30)
just ditch Cheatcode man they always unrate the Contest rather than catching Cheaters
True I just started LeetCode only to see 2 out of 3 contests unrated!! They don't value our time,this site much better
CF starts at 8:05 and Leetcode ends at 8:03
so solving 3 in 3 minutes?
Solving 4 in 3 minutes.
Oh sorry, it's again unrated
What about participate in both contest:)
As a tester, I almost disappeared from the scoreboard since all the problem I solved when testing were replaced, and only the problems I got WA are left, anyways don't miss it since lots of efforts were put, and hope you will enjoy the contest ^_^ !
As a tester, I don't know the problemset because it's different from ones I solved in testing.
.
orz Little_Sheep_Yawn
As a fan of wuhudsm, I am a tester who doesn't remember when I was on scoreboard.
Yet another great wuhudsm round, I'm sure this round will be so cool.
Is there a chance of an interactive problem in A->D ?
Yes, 2/3.
As a tester, I should test the round again.
as a tester, i almost forgot that the testing exists :skull:
"CHATGPT for solving 0 problems : ) ;"
Thank you for telling me this. =)
hopefully I'll solve the first Problem (500)
hope for +delta
I like wuhu dasima,He likes to eat red-skinned ducks.
omg md_nihal orz is a tester
woww i didnt notice sirrr
" CHATGPT for solving 0 problems : ) " It's good to increase our rating <3
You is clickable. Cool!
Damn,how did you do this.
I think I'll become a pupil today.
I'm sorry, but I guess I have to unregister this contest. How should I unregister?
x-shaped icon to the right of your handle — click it to unregister.What are (rank) testing? (like newbie testing, pupil testing...)
it means a (that rank) person has tested it
I just lost hope in today's contest. I gave up after 4 wrong submissions in A.
Bye to green garden and hi to gray concrete again.
Same. harD A and eAsy D
Why did my E test take so long?
Today's contest was the most difficult among the contests of the last month.
WAForces
I will never forget this A bait.
infinite queue
ABCD SpeedForces.
Apparently the contest is easy for everyone but me. Expert and I only solved A...
Contest is indeed easy, but I was stupid and wasted submisssions on C and D, and didn't solve E1, E2 becauze wasted much time on C, D. D is probably easier than C, but they both are easy.
Problem D feels like some random constructive problem from USACO bronze division, I would argue that it's even easier than C.
Rows that have first $$$1$$$ or $$$2$$$ cells painted black are virtually the same, so you can replace all of one kind with the other. Also rows that have first $$$3$$$ or $$$4$$$ cells painted black can be treated the same way.
Also I think something happened to the balance of the round past problem D :gasp:
And this is why problem A is called "Submission Bait". Next time I will consider reading problem name
It's on me to blame (for not debugging quickly and then submitting late tbh), but what's with the queue in the last 10 minutes? Something going wrong server-side?
I feel your pain, I have WA on pretest 33 in E1 that I could have fixed if my previous submit at 01:57 had been evaluated within ~2 mins T_T.
Me is a bit subtle, my code was wrong local-side and I looked at the wrong piece of code to debug for 20 minutes straight T.T Rush-submitting at 1hr57min helped nothing.
can you please help
i have an idea that if somehow we can find a path from root to some leaf in which mole lies than we can apply bs to find answer but i can't find and any way to find the correct path within the query limit.
is my idea correct.
if yes, some hint regarding how to find correct path
if no, ignore
Problem A bait is golden
AdhocForces.
Moreover, the differences in accepted solution in E1 and E2 is quite low, which means the different in constraint between two versions is really hard to come up with the solution separately.
What's your approach on D??
Try to iterate on every row from $$$1$$$ to $$$n$$$. Then, just greedily use the first operation if the number of black cells in the current row is less than or equal to $$$2$$$, otherwise we use the second operation.
lol, I definitely overkilled the problem then by doing bitmask dp for $$$a_i \leq 4$$$
271621595 I tried DP on D, failed on pretest 3, can anyone tell me if the DP is entirely wrong , or is there some minor error? Or if anyone has any tricky test case , that may also help. Thanks
Yeah i had the same bug but managed to fix it, here is the test case:
I fixed this one, and then started failing on 2nd test case ( results were given after contest was finished, due to long queue, didn't get chance to debug/ find error in 2nd test case ) .
n = 6 ,
2 4 4 4 4 2.expected = 5 .
The answer should be 5.
The "special case" is not a special case at all, you have to consider at every row, painting the whole thing white, but also every combination of previous $$$2\times 2$$$ grid placement with your own grid placement, making your state $$$(i, d)$$$, where $$$d$$$ represents which columns the grid from the previous row covered (I personally used $$$d = 0$$$ for "no grid", and $$$0 \lt d \lt = 3$$$ for "the grid covers $$$d$$$, $$$d+1$$$")
ohhhhhhhhhhhhhhhhhhhhhhhhhh, damn thats cool . Thanks :)
C is really easy problem once simulate and see the change.
I wish I could solve early
Who else got bamboozled by A??
got WA twice, but enjoyed it :)
can anyone tell me why my greedy logic is giving wrong or which case i am missing
submission link -https://mirror.codeforces.com/contest/1990/submission/271584567
Your solution fell into WA here:
7 3 2.With your outputted array
-1 1 1 -1 -1 -1 -1, $$$x = 3$$$ obviously, but $$$y = 7$$$.ok got it thanks
I had the same solution as you for over an hour before finding out what was wrong, it's definitely very tempting to think that this is the correct solution. The problem is when the initial -1's is more than the '1's in between. Ex: Input:
9 6 5Your output:-1 -1 -1 -1 1 1 -1 -1 -1However, the maximum prefix is actually at
i=1. So the output is unfortunately incorrect.Hardest Div. 2 A I know
May anyone tell me why for the problem B, I place a[x,y] to be 1, and place -1 otherwise, is wrong?
It seems to me obvious that for this case, x and y meets the constraint.
Counter test: 6 2 1
from y-1 to 1,puts -1,1,-1,1,... from x+1 to n,puts -1,1,-1,1,... from y to x,puts 1,1,1,1,...
Cause y < x. I missed this part of the statement at first as well.
How to solve E? Is it related to centroid?
is it even possible to do it deterministically, like if the tree is a star with n nodes, then one can't uniquely locate the mole in <n-1 queries
is it even possible to do it deterministically? Like if the tree is a star with n nodes, then one can't uniquely locate the mole in <n-1 queries
Yes, because the mole moves up when it isn't in your subtree
For E1
You can partition the tree such that each partition has fixed depth d (for some parameter d), except possibly the root partition. This can be accomplished via dfs.
Then, you ask whether each partition contains the mole or not. If you have found one, you can basically ask queries in such a way that the mole reaches past the root of the partition (for example, one dummy query to make mole go up, and another to check if the partition still contains the mole).
Now if you choose the parameter d appropriately, you can ask the queries < 300 times.
Was D really that easy ? 1.7k solves ?
Very easy. It's sort of like greedy from top to bottom, and you somehow discuss a few different cases and you're done.
ig i overcomplicated it then
Don't know, but it seems similar to CSES Counting Towers don't know for sure
Seems fair,i couldn't solve that,and couldn't solve this.
Very hard E, although considering the score distribution that seems fair.
C is one hell of a problem, i was like first 10 min:Oh hell no,i wont be able to
next 20 min:Maybe I can
next 30:No i can't
next 20:oh wait ,it is an increasing sequence
next 10:WA on pt2
next 9 min:Formula corrected, got AC
How'd you do it ? My approach was simulate for the first 2 iterations & all the following ones get simply right shifted by 1. But that didn't work.
I did the same, made two simulations,then i was sure that frequency for each element will be atleast two,then i used some math.
that works 271588535
I thought the same but i cant explain. Why does running it twice work?
there are 2 things that you can GUARANTEE after running it twice.
- 1. The new array will be increasing. (This can be guaranteed after the first run but you cant guarantee the 2nd point after the first run)`` Now when you can guarantee these 2 points then you if run on such an array for the third time you will clearly see that the elements just shift a single place and that continues. Hope this was clear
These are the observations that leads the solution but doesn't explain why does this solution work. Maybe I'm stupid.
well this is a constructive problem (acc to me), so your observations are sort of your proof , and if you can agree with the above 2 points , then clearly we guarantee to reach a pattern for every input after 2 runs , so we just find a way to calculate the answer for that pattern, like thats what i thought before coding
https://mirror.codeforces.com/contest/1990/submission/271632355
Hey can you please help with an edge case for my code. Read the comments, but couldn't figure it out.
Thanks.
For test case
t=1 n = 4 a = 1,1,2,2
your code gives 11, expected is 13. That's because
1,1,2,2 gets converted to 0,1,1,2
till here you code works perfectly but after the 0,1,1,2 will get converted to 0,0,1,1 and then 0,0,0,1 and then 0,0,0,0 . Your code just does not take these further steps into account
Looking at your code, your solution probably overflows when you do
sum += i * cntter;Notice thatiandcntterare both int, so whilesummay be a long long, the multiplication is not aware of this and therefore overflows. To prevent this, you can simply cast one of the varibales to a long long, sosum += (ulli)i * cntter;Maybe it's your implementation, or check if any variables were overflowing, I had the same idea and it was AC. https://mirror.codeforces.com/contest/1990/submission/271592090
why is my logic for C failing anyone?? 271626656 I also tried this 271597372
You cannot brute force,This will be of help
Worst contest ever
maybe a skill issue? cuz the contest was nice
WHO PUT 100 PRETESTS
The team was having fun while preparing the contest
carrot extension working for anyone?
For some reason, it always falls during the contests xd
For C, I simulated the operations for 2 iterations, then got the sum by prefix sums My hypothesis was after 2 operations, I would have more than 2 occurrences of each element, except maybe the last one and the array is in sorted order. Then, with each operation, just the last element gets dropped off, so I can get the sum using the prefix sum.
But apparently, this is wrong. Can someone point out what mistake I might have made?
Maybe you have errors in calculation, otherwise your deduction is same as mine.
How do I approach problem C?
Try to apply the operation for about $$$3$$$ or $$$4$$$ times to an arbitrarily varied array, and you'll get a pattern that you could collapse neatly with a bit of maths.
i think only 2 is enough right?
Coding-wise, yeah. But to observe the pattern, I think applying with pen and paper for one or two more doesn't harm.
thats true :)
print a table
Although I solved it, did not like $$$D$$$. It is just about a corner case that you get from the sample tests and then generalize it.
Problem B can any one help me figure out what is going wrong in my submission
271616161
thanks for the help resolved now was calculating y wrongly
try 10 5 4
Fucking mole
why this approach is wrong for question B let the array be full of 1 then after x the remaining portion must have 1 extra (-1) as to (1) so put these negatives from x to x+countofnegatives and before y the remaining portion must have 1 extra (-1) as to (1) put these negatives from y-1 to y-1-countofnegatives
try the test 10 5 4 and calculate the prefix/suffix sum. The trick of B is if you put too many -1, the max pos of suf/prefix wont be at x or y
Worst problems, it was purely ad-hoc and case-based problems. How are such authors even allowed to write problems?
Yeah, nice problems start from E1, but i had no time to get there, as i was getting wa2 all the time on ABCD xd
Idk, why... I read E2 20 minutes before the end of the contest and realised how to solve in no time, but had not enough time to implement... To me E2 <<< D, C, B
how to solve F
Please somebody ban this guy... inappropriate name for the website.
Akulyat
it's none of your business
Keeping CF clean and sacred is everyone's duty. I am just fulfilling mine.
Either get ban, or don't comment on public form with such an inappropriate user-names.
As simple as that.
it's none of your business
chill, bro just wanna solve F.
It seems everyone got at least 1
Wrong answer on pretest 2on problem AI didn't, but I solved C with 10 wa instead lol A and B went pretty smooth for me, although I saw why they could be tricky.
now im feeling happy i didn't even if i spent 8 mins on A
Could someone share solution of problem F?
Here's my solution with proven correctness (& proof of good running time by AC):
First of all, the segment is polygonal $$$\iff$$$ the maximum element is strictly less than half of the sum. One direction of the proof is obvious; for the other one consider the following construction: first the maximum goes to the right, and then all the other segments go to the left. This construction can be transformed into a polygon by dragging the intermediate points to the top & right until the end of the curve coincides with the left end of the maximum.
Now consider a subsegment of the array. We’ll denote the sum $$$S$$$ and the maximum element $$$mx$$$. If $$$2 \cdot mx \lt s$$$, the whole subsegment is polygonal. Otherwise, notice that any subsegment that contains the maximum cannont be polygonal, since the sum can only become smaller. This immediately gives a recursive algorithm: if the condition is fulfilled, stop, otherwise split and take the maximum. We can maintain the sum & maximum in a segment tree.
However, this is not enough by itself, since on the following test this works in $$$O(n \log n)$$$ even for very large array sizes:
Here’s one thing we can do: maintain a cache of answers for segments, and stop the recursion when we see the answer in the cache. Now we need to somehow invalidate the segments after something has been updated in them. Doing it naively is very tricky (and probably involves something like dynamic merge-sort-trees), but we can do it lazily: maintain the last time of update using the same segment tree. Now when a segment is queried, compare the time when the answer was put in the cache with the time of last update, and either return, or invalidate the cache record & recurse.
The total number of cache invalidations is $$$O(\log A)$$$ per update, since every time a new segment appears that cover the same point, at least a half of the previous sum was cut, and the first sum is $$$\leq 2A$$$. Therefore, the total deletion time is $$$O(q \log A)$$$.
The total number of recursive calls (and considered segments) across all queries should be $$$O(n + q \log A)$$$, which gives the total time of $$$O((n + q \log A) \log N)$$$, but I see no easy way of formally proving this. If anyone has the proof, please share it!
Thank you!
What is B????
Set indices from $$$y$$$ to $$$x$$$ equal to 1 and to left and right from it alternate -1 and 1, like:
what if fill y to x with 1 and to left and right of it fill only -1
doesn't work. For example,
Cuz best prefix is $$$2$$$
very nice problemset, thanks!
Can someone tell why is this solution wrong for Problem B 3rd test case : 6 5 1
Solution : 1 1 1 1 -1 1
best prefix is $$$4$$$ not $$$5$$$
max prefix is at position 4 or 6, not 5
the best prefix of your solution is 4, but the prefix at index 5 is 3
this will work: 1 1 1 1 1 -1
I got cooked, but I liked the problems!
I haven't solved E yet, but the problem is inherently interesting, and I will have a fun time thinking about it tomorrow
why my approach for problem $$$D$$$ didn't work ?
I did this solution but got WA on pretest 2 :(
There are three ways to dye a $$$2 * 2$$$ subgrid. So u can't just minus $$$a_i$$$
now I got it and realized that this case:
3 2 4 2
should have output 3, but my solution output 2
I don't know how I came up with that idea !^_^
Your idea isn’t totally wrong though, more dp states might help :).
thanks for the great round
what would be the difficulty rating of C?
1500 maybe
Unclear Instructions in Problem E
It seems like mole will move to its parent in each query, but
It will only move when subtree does not contains mole.
?
Technically its correct , But it could be bolded or written separately in new paragraph
I tried to use triangular numbers for C but I got WA from Test Case 2. Thoughts? 271632012
Solved ABC in 21 minutes,then my brain just gave up.
I might reach green for the first time in my life after giving contests for 11 months!!! Ngl problems were really scary Edit: Guys I did it!!!!!!!
brace yourself, the true grinds have only began
Thanks :D Never gonna stop
nice. I will reach gray after +6 on B
Thanks for the round, the challenges were enjoyable!
thank you for the great problemset! :]
I guess my skipped solution for problem D is hackable but it passed as I missed a small edgecase
271631440
May be the testcases are not too strong
can someone explain problem b to me ? if i understood the problem correctlr why i don't make array all by one?
I don't really get your saying — if the array is $$$1$$$-only then $$$x = n$$$ and $$$y = 1$$$. Can you clarify your concern?
I meant that I didn't understand what "maxmj=1(b1+…+bj)" and "maxmj=1(bj+…+bm)" meant in the statement.
Take an array like this $$$[-1, 1, 1, -1, -1, -1, -1]$$$ ($$$n = 7$$$).
We see that:
$$$max_{j=1}^m (b_1 + \ldots + b_j) = max(b_1, b_1 + b_2, \ldots + (b_1 + b_2 + \ldots + b_j)) = max(-1, 0, 1, 0, -1, -2, -3, -4) = 1$$$
Here $$$1 = -1 + 1 + 1$$$, hence the maximum prefix position of $$$b$$$ is $$$x = 3$$$.
Similarly:
$$$max_{j=1}^m (b_1 + \ldots + b_j) = max((b_j + \ldots + b_m), (b_{j+1} + \ldots + b_m), \ldots + b_m) = max(-3, -2, -3, -4, -3, -2, -1) = -1$$$
With this, the maximum suffix position of $$$b$$$ is $$$y = 7$$$ ($$$b_7 = 1$$$).
Got it. I was thinking something similar during the contest but didn't want to write a solution in case my interpretation was wrong. Thank you for your explanation!
I used to get it wrong but now I understand the issue thank you
can someone tell me where this code is going wrong for Question C 271621163
I think the first loop should be execute once again. The array will be incresing after the first time, and every element except for the last one will occur at least twice after the second time. Then the prefix works. I hope you find it useful.
Hi can someone explain why the answer is 3 for problem D
Input 3 1 3 1
--- Understood
My uncle <3 skahl15
Thanks! ;)
After staying at a level for a long time in this game,i cleared it and more than satisfaction i feel fired up to reach the next one too.Lets goo
Thanks for the round, the problems are awesome!
I'm curious about if the definition of a[i] in D turned into column instead of row, is the problem solvable?
I misread it in the contest ╥﹏╥
0101byc is Fake I'd of NeverLand — you can check that into his submission 271575788.
so you should declare Psychotic_D as winner (#1) of official Codeforces Round 960 (Div. 2).
not concerned with just rating, but it will be a great Achievement for Psychotic_D.
:)
Hey wuhudsm I also think that users 0101byc and NeverLand have some explaining to do. Additionally, please consider adopting the "trusted participants" policy from Div3 and Div4 rounds in Div2 and Edu.
buddy thats not proof that the code is by them
Looks like it's not the first smurf account for him. The same happened in another div.2 contest. At least those two accounts are owned by the same person. After checking the code styles and templates it looks extremely similar to NeverLand. But this account itself looks like a smurf account, to be honest.
Also, Psychotic_D is also a cheater and should be permanently banned along with his friend wuhudsm and other people from their group (e.g. EndlessDreams).
I wonder if Codeforces administration will take any action against people who cheat so much so they take top-3 in the recent rounds.
Wild fact: initially Problem D was placed in B and I thought it was best suitable for that position because of my greedy solution
seems good to be a winner XD
Thank you a lot,I got my best rank 170!