Hello Codeforces!
I am glad to invite you to Codeforces Round 986 (Div. 2), which will start on Nov/10/2024 18:35 (Moscow time). Note the slightly unusual start time.
The contest will run for 2 hours and have 6 tasks. The contest will only be rated for those with a rating not higher than 2099, but we welcome higher rated users to participate out of competition.
Holding the contest would have been impossible without:
- flamestorm for insanely excellent coordination, without whom this round would certainly not happen.
- Vince729 and swagchicken for lots of discussions about the problems and proposing other problem ideas :)
- conqueror_of_tourist, BucketPotato, Dominater069, sstrong, triple__a, xiaowuc1, lucasxia01, n0sk1ll, nikilrselvam, thanhchauns2, AkiLotus, bibimoni, CSQ31, mp1309, Non-origination, Qualified, redpanda, dazlersan1, fatant for testing and giving a ton of useful feedback!
- MikeMirzayanov for the wonderful Codeforces and Polygon platforms.
and of course a special thank you to all of you for participating!
Score Distribution: $$$500-1000-1500-1750-2000-2500$$$.'
UPD: The Editorial is now published.
UPD2: Congratulations to the winners!
Div 1:
Div 2:
First solves:
- A: podyapolskiy.yaroslav in 00:01:14
- B: potato167 in 00:07:38
- C: thembululquaUwU in 00:09:18
- D: jiangly in 00:17:37
- E: golions in 00:17:54
- F: MAKMED1337 in 00:10:29
As a tester, this is indeed a Codeforces round.
As a participant, i hope that problems are good)
Thanks for telling, I thought it was an Atcoder beginner.
As a tester, I almost planned to register until getting tagged.
As a tester, i couldn't solve all the problems.
WOW! ok, it'll be a bit hard◉_◉
You don't need to solve all the problems to get a really big rating boost.
yes, I know 2 problems are enough for me
As a participant, I wish we can learn something from the contest
OMG , Trump
Congratulations on your election :-|
as a participant, I will start from Problem F, or die trying.
As a fellow participant, we must go all or nothing
Rainboy would be proud.
I won
As a tester, I want to know why you're not doing Universal Cup.
xiaowuc1 orz
I hope the people who are genuinely solving tasks(by themselves) get a positive delta.
As a participant Hope to solve 3 problem
I hope i can reach pupil , its nearly impossible ig but ill try my best .
As a participant, I wish I can solve at least one problem
I hope I will reach M in this round.
Hoping for some positive delta.
the time start is so good 22:35 utc+7, also it time to go pupil! :-D
hope to solve 4 problems :)
yeah i reached the goal
As a participant, I believe I will learn something new.
I wish every CF round started at 9, so that I could have time to eat my disgusting mess food in peace.
I'll try to make my day with this Round. Good luck to everyone!
As a participant, I wish I won't get wa on test 2
As a Codeforces user, I don't understand all these ass comments everywhere, what is the story behind them? why are they considered cool?
hope to solve 4 problems -_-
Who else came here and the contest haven't started?
I wont breath until someone rep this
As a tester, goodluck.
As a participant, this is my first unrated Div.2 :D
Can't register after contest starts? I registered and still couldn't submit
jiangly OP!
it's dev1 in disguise
My points have gone up though. <<___>>
Rays of hatred for changing D
As a participant, i am ded †.
i'm cooked
Same, these problems really humble me after doing good for a while.
good, 'cause i am roasted.
This is the one of the CF rounds of all time
as a participant i can say the solution was out on telegram. Please take strict action on cheaters a request. I am fedup of this cheating can't you block their account permanently and ask everyone on the platform to link their account with their phone numbers so that if one cheats he will need to create a new account with a phone number and a person can have limited phone number not like gmail account so he or she might not do the same with other phone number account. The problems where good indeed
What were you doing on Telegram ?
Downloading movie for the night
which one ?
jav
Phone number verification is a good idea. Dont know why they dont implement it. It will make it harder to cheat again and again.
phone number verification is a must.
great b and c. Makes you really think.
C is much easier than B
D is much easier than B
how to solve C?
two pointers
something like sliding window?
What i know that thery are the same, anyway yes u can use sliding window,
But before that pre-calculate prefix & suffix to know max good groups u can made in ranges [1, l] or [r, n] in O(1).
Finally the range [l, r] is optional answer, if (pre[l — 1] + suff[r + 1]) is greater than or equal to m.
Div 1.33
how to solve F?
Why
q 2 j 4is invalid in problem D for the second test case? where: Q: 2 3 1 4 K: 1 2 3 4 J: 1 4 2 3q 2 is invalid because q_1 < q_2
my bad. mistaken as position. thanks!
sorry, I don't get it, which rule does that violate? q values 1 more than 2 according to their list, so it should be okay to swap?
Realized my mistakes at the end of the contest...
B burned me to charcoal, C reduced me to ashes and buried me in the mantle
B took all my time, then after solving B, I realised that C was way simpler
Still have no idea how many rounds of simulation to run for pA... was guessing 100 * 10 would be enough?
10 should obviously be enough, i think. Since max destination coord can be (10, 10), and if we ever reach there, we would have to make some progress at each iteration of sequence. The bare minimum progress if (1, 1) (since each iteration is identical and we cant move (0, 1) one time and (1, 0) the other). Since max x/y is 10 and each time we get closer to it by atleast 1, 10 rounds would be enough.
10 is not enough, surprisingly...
yup, right. luckily i iterated it 20 times during contest, lol. nice problem.
$$$10$$$ is not enough. Consider a path where Alice goes $$$3$$$ down, $$$1$$$ right, $$$1$$$ left, and $$$4$$$ up. The point $$$(1, 10)$$$ is eventually reached,but it is only reached in the $$$14$$$-th repetition. I'm pretty sure $$$14$$$ is enough, but I can't prove that.
aaaahhh i see, that's cool. Luckily i iterated it 20 times instead of 10 during contest for some good measure, or i would have been cooked even worse than I already am :(
I iterated it 1000 times after WA :)
C<B
pls dont make these shits again.
thank you.
what?
I liked B and C, but the problem statement for D made me lose braincells
In the second test case for Div2D, can you please help me understand ? I am able to reach from type-1 to type-4 card in this manner.
1) Give the type-1 card to queen, and get type-3 card from queen
2) Give type-3 card to king , and get type-2 card from king
3) Give type-2 card to Jack, and get type-4 card from Jack
What is the problem ?
I couldn't solve B, or C or D. Implemented all 3 questions, but kept on getting WA on pretests. Quite imbalanced contest IMO.
Alice can't exchange card a for card b if b < a. Haha it's funny how we all wrote at the same time
The problem is you are disrespecting Alice's trading preferences. Alice would never trade card 3 for card 2 as she prefers 3 over 2.
We can only go up in types, we cannot go from type-3 from type-2, it is Alice preference.
Also spent like 20 minutes on it
Alice won't exchange type-3 card to type-2 card because Alice values type-3 card more than type-2 card
I didn't consider Alice's preferences. I simply ignored it in problem statement. :( .
Step 2 is wrong , Alice won't trade for a lower card as given in the question.
You can't trade with the queen in the second test case,
both Alice and Queen wants to trade to a higher number.
Alice (meaning you) isn't willing to trade a higher card for a smaller card, so your trade of giving $$$3$$$ to receive $$$2$$$ can't happen.
You can't give to king type-3 and get type-2, because 2 is smaller than 3. Alice can change cards only in increasing order according to her preferences
"Alice's preferences are straightforward: she values card a more than card b if a>b, and she will also only trade according to these preferences."
B was harder than C.
Problem C is GARBAGE.
nice C and D, retarded A and B.
shittiest div2 ever applepi216 please do better next time
Solved A in 4 minutes just to stare at 5 wrong submissions on B....
for B, if b == 0 and c == 0 => if(n <= 2) ans = n — 1 else ans = -1;
if(c >= n) ans = n;
otherwise ans = n — (n — 1 — c)/b — 1;
what is wrong with the approach?
It's also solvable for n-2.
for example
3 3 3 3 3
0 3 3 3 3
0 1 3 3 3
0 1 2 3 3
0 1 2 4 3
more case when b = 0
what if b=0 and c<>0?
Terrible weekend. Got humbled twice I don't belong here.
Corner Cases
Lol, :)
It was so close for AC :(
The feeling when you skip B and can solve D & E is indescribable, feels good.
I felt like A < C = D < E < B by difficulty
B is so easy, if you carefully analyzed each case, it's more annoying than difficult in my opinion.
can you share your approach
goal is [0,1,2, .., n-1] in any order
if there is a number x > n-1 in a, then there is some number in [0,n-1] missing from a. And if we repeat the operation enough, then x is inevitably will be replaced with a number in [0,n-1]
so the key is, if a big number exists then a good one "[0,n-1]" does not
I analyzed cases in the following order:
1. handle case when n = 1
now 1 < n
2. handle cases when b = 0, a [c, c, ...,c]
now 1 < b
3. from given test cases, I realized it may be better to also handle case when b = 1 and c = 0, basically a = [0, 1, .., n-1], so we need not to do anything
now b*(i-1) + c is always greater than i-1
4. using the hint, it's possible to see that for each big number (> n-1), when we apply the operation, if there is still big numbers, then max is one of such integers and it's replaced by a good number (in [0,n-1]), which means that for each big number, we will need a single distinct operation to delete it, after removing all big numbers there will be no evil.
So, now the task is to count how many big numbers in array a.
Notice that a[i] = b * (i — 1) + c, bigger i, bigger a[i]
find min i such that a[i] > n-1 "big number"
so b*(i-1) + c > n-1
this can be solved with binary search.. but also probably just by moving things in this inequality.
Wow, I think I solved D in the last 2 minutes of contest, hoping it passes system testing!
I spent maybe 10 minutes rereading the problem statement for D until I figured out that the Queen/King/Jack of Hearts are supposed to be the players and are not cards of the game. Other than that, great contest :)
what the hell was be
can someone help me by telling what case i missed
https://mirror.codeforces.com/contest/2028/submission/290946207
I made a small change in your code and it got accepted. Here is the accepted solution. You missed the case when n == 2 in the if condition where a==0 && b==0.
Implementation skill issues wasted so much time Left contest in frustration Will work on myself
I submitted my solution for problem C in the last 30 seconds without even testing it!
I am really happy!
I'm so close to submit but It's 2 minute late...
Now I'm waiting for the practice mode
B ruined everything
Is problem D a graph problem ? In the entire contest, I try to build the graph and reduced the edges so that the graph size is O(n) instead of O(n^2). I try the mono stack or segment_tree but failed very badly.
I did solve it using bfs but there might be other non-graph methods
It can be interpretted as a graph problem. To reduce the number edges you can keep track of which nodes are already visited and only consider edges ending in unvisited ones (using a set or something).
I was trying the same idea using mono stack for around 40 minutes, but understood that prefix max and position of maxn on the prefix is enough.
I did use mono stacks to reduce edges, but I don't know if it is a $$$\Theta(n)$$$ solution: 290933314.
first time solving a problem which has less than 500 submissions. (problem E)
C is actually good problem, sadly I lose all my time for A/B because I'm bad at edge cases.
Just sad.
Wasted almost an hour on C by somehow concluding that Alice's segment can be non-contiguous and now I'm actually curious how to solve the modified problem
Ex: For $$$m=2,v=2$$$ and $$$a=[100,2,100,1,1,100]$$$ answer would be 300 where we give segment $$$[1,1]$$$ and $$$[3,4]$$$ to the creatures and rest to Alice.
$$$O(n.m)$$$ is obvious but can we do better ?
I am actually curious what the $$$O(n.m)$$$ solutions is!?
All I can think of is complete search on the set of pieces allocated for Alice, and for each check whether we can make monsters happy using the rest. It's $$$O(2^n.n)$$$
Let $$$dp[i][j]$$$ denote the minimum sum of the j pieces to satisfy j creatures among the first i elements.
$$$dp[i][j] = min(dp[i-1][j],dp[k-1][j-1] + sum[k,i])$$$ where k is the maximum index less than i such that $$$sum[k,i] >= v$$$
Answer would be $$$sum[1,n]-dp[n][m]$$$
We would need to do binary search to find k so the TC would actually be $$$O(n.logn+n.m)$$$
I wasn't able to spend much time on C in the contest (got cooked by B like many others), but the approach I had was quite straightforward. I did end up upsolving it after contest ended, with an
O(n + m)solution, which is this case is justO(n).Key Observation: Alice's section can only be at the beginning, end or somewhere in the middle (since she can only take a single contiguous section) — part of the question, but easy to miss.
Approach: 1. Create modified prefix arrays of potential sections in both forwards and backwards directions (adding to array whenever the sum crosses
v— creating sections greedily in both directions). 2. If length of above arrays isn't overm, then a solution is not possible (as we couldn't createmsections even using greedy). 3. Now it's just a matter of maximizing Alice's section (m+1th) while consideringmsections from a combination of forwards and backwards arrays — we can iterateiin0..mand consider max of(total - forwards[i] - backwards[m-i])as the final answer.AC submission without using 2 pointers or binary search: 290960412
Sorry I should have been clearer. I meant how to solve the modified problem that I misunderstood not the original problem.
Why this solution to problem B is giving TLE on pretest 4?
Scanner in Java is incredibly slow.
Thanks, just submitted the same logic with bufferedreader and it got accepted.
D is extremely hard for me to understand the statement.
same
Thanks for the contest! Feels good getting pB in 1 try!
I have a simple question Was not there other names in the WORLD except King, Queen ans Jack ?
The names imo are justified in literary context, as they are directly linked with Alice's Adventures in Wonderland.
I like how the descriptions naturally reflect this concept, although the
q k jorder on D got me a few times because I'm just so used to thek q jorj q korder due to all the playing card games I've played so far.What can I learn from problem A? If constraints are really small, just run the simulation enough number of times which is very large than the constraints?
can someone explain why in D, in the the second test case.
Alice exchanges to card 3 with queen and then to card 4 from jack. Why isnt this a valid workaround
In other words,
why isnt the soln
3 q
4 j
correct?
She cannot exchange card 4 with jack because p[4] = 3, and p[3] = 2 therefore p[3] > p[4] doesn't hold.
yea, my bad I was debugging it wrongly
I think that problem B needs too many steps as the second problem in Div2,but after minutes of thinking,I solve it.I use very easy to use and convenient translator today which I didn't know in former.But my parents asked me not to use the translator on some competitions that are not important or do not increase the rating value.
To be fair, I don't believe the submissions from podyapolskiy.yaroslav are works done by a single person without using AI tools. If you look at their submission history, the person switched to a new random question every 3-5 minutes, and was able to produce a fully written solution that passes the sample but failed at some later pretests (except A). Even worse (and that's why we could discover this) -- they don't even bother hiding it with spacing out the submissions by a few more minutes, or at least trying them in order.
The final judgement obviously needs to be made by the admins, but it's fairer to award the first solve to the genuine first solver if the admins found this case guilty.
can anyone tell why my approach fails 290961099 ? can we solve it by binary search ?
problem c.
Nice Contest!
What was the point of even having D, it was just simple greedy and implementation
B had a bit hard concept. C and D were excellent, I enjoyed implementing it. They really teach us to visualize the problems and to handle indices carefully. All in all, a great round.
As a participant and a beginner, I can't even solve B.
first time getting a first solve :D
As another Lions fan, go Lions!
Cool! What a game tonight
Congratulation :D
We can see that the first person to solve problem A, podyapolskiy.yaroslav, used AI on all of the questions.
Wait really?
You can check out his submissions.
How can I check it? I'm new to Codeforces :D.
Oh may bad , I got WA on A , because of limit of repeating the process , if I got it correct , then I'll top 3k now
Putting $$$10^{18}$$$ as limit works xD
Just not in python
orz
"Amazing problem! It really tested my understanding of edge cases and forced me to think creatively. Loved how every observation brought me a step closer to the solution. Looking forward to more challenges like this!"
"Finally solved it after hours of debugging! The problem was tricky but super rewarding once I figured out the approach. Thanks, Codeforces!"
"Great problem! Loved the unique constraints – they made me rethink my entire approach. Big shoutout to everyone who shared tips on handling tricky edge cases!"
"One of the best problems I’ve solved recently. It perfectly balanced complexity with elegance. It felt satisfying to apply different techniques to reach the solution. Kudos to the author!"
"Spent half my day on this but learned so much! From wrong attempts to the right approach, the journey was worth it. Excited for more problems like this!"
Each of these comments is around 60 words or less, focusing on appreciation, learning experience, and excitement for future challenges.
ChatGPT :)
POV : B is close to This
I've just noticed while upsolving AC problems
what is wrong with the rating system man???
https://mirror.codeforces.com/contest/2028/problem/B - может я что-то не так понял, но может кто нибудь обьяснить мне как решить эту задачу бинпоиском? Я написал решение на c# с использованием biginteger(на decimal и long там переполнение) и оно не зашло по времени
I will try to solve more than 3 problems
it’s a great idea to highlight the name of the first solver for each problem!
MikeVazovsky is the strongest competetive programmer ever