Xin Chào, Codeforces! (☆^ー^☆)
We are thrilled to invite you to participate in Codeforces Round 1014 (Div. 2), which will be held on Mar/29/2025 17:35 (Moscow time).
This round will be rated for all participants with rating below 2100. Participants with higher ratings are encouraged to participate out of the competition.
You will be offered 6 problems and 2 hours to solve them. The tasks were authored and written by k1sara and sergeev.PRO. We hope you enjoy the challenge!
A heartfelt thank you to everyone who made this round a reality:
244mhq and Um_nik for expertly coordinating the contest and offering invaluable guidance throughout the process,
makrav, zltzlt, IzhitskiyTimofey, sadness, Noinoiio, max0000561, Vash_nick, yunetive29, ItsNotMeItsYou, DimonKrutoi, dope, Fu2o, Mikhango, re-wa-tl-ok, VictorKleymenov for testing our round and providing impactful feedback,
danya111 for coming up with some exceptionally riveting excuses as to why he’s too busy to test our round,
sergeev.PRO for being an amazing co-author, for putting up with my endless complaints, and for generously letting me copy every math homework over the past five years,
MikeMirzayanov for the fantastic Codeforces and Polygon platforms.
You for participating in the round.
[UPD 1] The score distribution (now changed) will be as follows:
[UPD 2] EDITORIAL
[UPD 3] Congratulations to the winners!
All participants:
Rated only:
Excited!!
sigma
Wow, handsome authors! I believe this contest will bring us a perfect experience!
Hope to reach M.
hope to reach next level good luck!
Are you half Viet?
i am full Viet
Hello full Viet, I'm darkkcyan)
cam on bay h no la cua e
the authors be looking like a couple
istg this is the 3rd engage kiss fan i've ever seen in my life
Score distribution looks really nice ngl
"GL HF" is something I only see in the beginning of lose LOL game.
As a tester, I think that this round is very nice
orz, vietnamese's contest ._.
orz finally
Xin chao !!! Very excited to do the contest
Very excited. Wish I can reached the next level!
Bro...
Tu noi dong xanh
They did danya111 bad xD
let's see how this one goes
why all submissions are getting "queued" after the maintenance period?
Same is happening with me.
Really love the "you" word colored in legendary grandmaster's colors. Feels really great to see this way.
Expecting Increase
based
yeah... good one. I totally deserve it tho.
Sorry guys, and good luck with the round!
how is that a bad thing
It wasn’t sarcasm — your advice was actually pretty helpful(
Hope for positive delta
As a tester, I am not sure how to kindly ask for contribution.
hope to reach expert
contest sigmaboy <(")
As a tester, good luck!
target to reach pupil
4th problem is 1500
so SPEEDforcessss...
[EDIT] — now we have different score distribution
WOW!!Nice~~~~~~
GOOD LUCK TO EVERYONE！！！
whoever knows this is a legend
:))) supachok no phe pờ nhây :)))
look at my name
orz chiến thật
Excited!! I hope it will be a great and enjoyable contest and I can improve my rating.
Ông Từ Mentioned!!!!
this is a true Việt moment
Authors are busy in making the contest since 2019. xd
Hope to reach expert with the boys.
hoping for positive delta !!!
Hoping this time to get over the mark !!!
Score distribution seems nice
orz contest vn là phải chơi
juan
Hoping to reach expert again : )
Glhf kids! I'm winning these
Nice try Pippy
lol imagine if we changed P to D and D to P in question E
plz hint for F im so lost
The editorial with hints will appear soon
lovely
It's out
appreciate the quick editorial release
I enjoyed all the problems from B to E. Thank you for the contest.
why didn't you enjoy A
800+ on E? Any hint?
++
if a cell has even neighbours , it doesn't matters what you color it. If has odd then parity changes.
nice questions and contest,ruined by cheaters :(
C,D > E
:3
dislike
I am cry...
dont plz im joking like
Idk why but I cannot load standings... so I happened to not checking standings table at all.
After contest it's normal again.
But maybe thanks to this I focus more on coding and comeback at D (at least for pretest — praying).
same happed with me
Really enjoyed B and C. But the high submissions is clear indication of mass cheating!
Fr nowadays too much cheating
Today B and C was enough easy, so I am not thinking that it can prove cheaters existence
Maybe after testing my solutions will be wrong, but you can solve very very shortly and easy.
Big problem with D. Good task but there is so many test cases :(
Just brute force for D
https://mirror.codeforces.com/contest/2092/submission/313025446
can someone help why this failing on pretest 2
can you explain your approach? not able to understand
i am updating max possible even and odd number after each index like if the present a[i] is even then we can add it with max possible odd possible and then update odd with its sum and also update even as it may be possible to not add 1 in the end and as a result get an even sum and do the same if the present a[i] is odd
Try this test case. The right answer should be 25, you output 19.
27
Why I am getting WA in D https://mirror.codeforces.com/contest/2092/submission/313025035
test case 3
you might want to tried this test case.
5 LLTIImy code is giving -1
answer is 4 3 4 2 2
oh thanks Now I understand we can also make pair of character highest and second highest count even if it is not there.
check my history, I WA 2 and WA 3 to actually arrived this test case and speed coding. Actually insane luck to made it at 1:54
very nice test case. How did we handle such case? that we have to consider adding the largest element also? eg. i have sorted all 3 based on their frequencies i.e. L,I,T. But my code is also giving -1 on your test case. I haven't considered the case that we can/should add the character with the largest frequency also.
Don't overthink it, brute force it. O(n^3) is acceptable since n <= 100.
You can checkout my submission.
can you explain your approach? not able to understand. What are you bruteforcing? I am not good at Python
Sorted the frequencies of "L" "I" "T", I greedily pick the smallest one to try increasing it. But not the only smallest one, I tried them all by the order of frequencies. (brute force + greedy).
The overall loop is 2*n since the problemset said we cannot do more than 2*n operations.
Standings not loading for me, is it a problem with my internet or everyone facing it?
me too, I cannot load the standings.
D is rubbish.
No, you probably just didn't find a simple way to think about it.
Suppose you have different characters LI with the L at position i.
Then with operations at i and i, you get LITI --> decrease relative frequency of L by 1
With operations at i, i+1, you get LTLI --> decrease relative frequency of I by 1.
Then, you just look for indices where the relative frequency of some character is larger that it should be and apply these operations.
D isn't garbage because it doesn't have a good solution, it's garbage because it has tons of bad solutions which pass. Most submissions are clearly GPT written heuristics which somehow AC. Even if you assume the testing is strong enough not to let incorrect solutions pass, the fact remains that a majority of contestants who've written these solutions will be unable to prove their approaches provided a proof for their implementation even exists. There are many masters who didn't AC but tons of newbies, specialists and experts who apparently did.
I think it was easily foreseeable that this would happen given recent contest trends, and it's a failure on the part of authors to not deal with it preemptively.
Out of curiosity, what kinds of other heuristics did people use?
I wonder if the problem would be "fixed" by making the complexity requirements more strict to force the simple solution.
I didn't really find any solutions with GPT heuristics. I found some super verbose solutions like: https://mirror.codeforces.com/contest/2092/submission/313017676 and https://mirror.codeforces.com/contest/2092/submission/313014345
These are "bad" solutions in terms of being needlessly complicated, but if someone writes and debugs them correctly, then fine. They also lost a bunch of time to solve E. I'm not aware of anyone with who wrote a bad solution quickly, as you'd expect from GPT.
I think the contest was easier than typical (2C, 2D, 2E all are easier than normal), and that's a good thing considering that few legitimate Div 2 constants typically solve E and F. Unfortunately many people are worried about GPT cheating, so they interpret the increase in solve count as evidence of increased cheating.
The question is just implementation. The naive brute forces passes, my implementation is O(tn^3), but passes in < 80ms. The solution is also just uninteresting, there are no observations, optimizations, or clever ideas involved. It's just straightforward simulation of adding characters to the string.
Take a look at my submission for example. It's not particularly hard to write, but slightly tedious and boring.
My submission
Very smart.
What is the motivation for thinking in terms of decreasing relative frequency rather than increasing it? Is it that the max operations is 2n acts as some sort of hint?
Well yes, but my thinking in the contest was messier.
At first I was also thinking about some greedy solution. In fact, I think I sort of proved that a greedy solution is possible (i.e. if the frequencies are a > b > c, you can solve it in $$$(a-c) + (b-c)$$$ operations). But the implementation details were messy, and I was wondering "is this really the intended solution?" The answer is obviously not, otherwise then there would be no reason to have the 2*n constraint.
Then I wondered "what if I apply the operation twice at the same index?" and since I already had the idea of relative frequency from my idea about the greedy solution, I was able to make the jump.
Also this sort of construction is common (max of $$$kn$$$ queries ---> do a $$$n$$$ step solution with $$$k$$$ operations per step). For example: https://mirror.codeforces.com/contest/1762/problem/D
I really think CodeForces needs stronger samples. Good problems with weak samples such as D can also bring bad feeling to those who got the correct algorithm but failed on corner cases.
Disagree--if you come up with a complicated algorithm/implementation (for example compare yours to https://mirror.codeforces.com/contest/2092/submission/312973230) bugs are normal and as a consequence you have to go through the debugging process.
It shouldn't be the responsibility of the writers to make that easier.
Most submissions for D and E seem GPTd, both were casework heavy problems with even many of the seemingly non AI solutions seeming guesses at best
Also idk why the pretests were this lazy especially for these two problems
Bad contest
Can anyone give me a quick explanation to C's solution ?
One observation is if a is odd and b is even, you can always make a = a + b and b = 0
If you start out with only odd or only even towers you can't do anything and the answer is just the maximum.
Otherwise, if you start out with odd and even towers, you can almost combine them perfectly, except you may have to leave behind a tower with height 1.
Example: Towers of length 5, 4, 3. Combine (5,4) ---> (8,1), and then (8,3)--->(11,0).
Notice that the total number of towers with odd height is invariant over all operations. So if there are initially x towers with odd height, the tallest tower can have odd height, and then there will be x-1 towers with height 1.
So the answer is [sum of tower heights] — (x — 1).
soluion for
a: https://www.youtube.com/watch?v=7B6Izk5Dkng b: https://www.youtube.com/watch?v=TvuS12-pZyM others will be uploaded soon too
D is just lame implementation. right?
D is just lame
Indeed implementation, but lame or not is based on taste
I was excited to see my D work but also disappointed that it was just brute force greedy
My worst performance, back to 1850- again :(
i honestly could not figure out A and just guessed it
if problem A simply hide test case
It could easily be a B problem, tough for me too.
I would like to know where my code fails for problem C, IMO its not an elegant solution but should still work. https://mirror.codeforces.com/contest/2092/submission/313011156
Your approach is correct, but it is not necessary that the answer fits into a 32 bit integer. Use
long longinsteadI messed up D
why I cannot load the standings even tho every other page loads normally.
Just missing this single line on problem 'C' has ruined my night:
Now, could any of you show a little sympathy for me, pleeease...
I got
Wrong answer on pretest 2twice because of this.Wow! Coder FeiWuLiuZiao competed in Codeforces Round 1014 (Div. 2) and gained +112 rating points taking place 184
it's funny how d.pippy is allowed to host parties at his home again now
one of the best div2 contests i joined. if i don't mind -19 rating change :D
Why is problem F's time limit so tight?
The intended solution has a time complexity of $$$O(n \log n)$$$ and a memory complexity of $$$O(n)$$$. My solution runs in $$$\approx 300 \ \text{ms}$$$, so setting the time limit to $$$6 \times$$$ of that seemed sufficient. Also, the testers' solutions ran in under $$$400 \ \text{ms}$$$.
I got a system warning in this contest saying my code coincides with someone elses. I just wanted to say that that user got access to my account and he most likely used that to cheat. If you check he had submitted after I had