Привет, Codeforces!
Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов.
В 03.06.2025 17:35 (Московское время) состоится Educational Codeforces Round 179 (Rated for Div. 2).
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Раунд основан на задачах Первенства города Воронежа по спортивному программированию «VrnCode-2025». Если вы участвовали в этом соревновании, то воздержитесь от участия в раунде.
Почти все задачи в раунде придуманы и подготовлены мной. Хочу сказать спасибо Ивану BledDest Андросову за задачу, которая сделала раунд более сбалансированным.
И еще раз хочу сказать большое спасибо координаторам раунда: Ивану BledDest Андросову и Михаилу awoo Пикляеву за улучшение качества задач и помощь с их подготовкой.
И конечно, огромное спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Наши друзья из Neapolis University Pafos также хотят передать вам сообщение:
Продолжается прием на бакалавриат по программе "Компьютерные науки и искусственный интеллект" в Neapolis University Pafos!
JetBrains Foundation поддерживает эту программу бакалавриата и предоставляет 20 полных стипендий для самых талантливых абитуриентов. Стипендия покрывает стоимость обучения, проживание, медицинскую страховку, визовые сборы и карманные деньги (300 евро в месяц).
Отличные новости! Если вы не успели подать заявку в первом потоке — у вас ещё есть возможность присоединиться ко второму! Подайте документы, пройдите вступительное тестирование и собеседование — и вы сможете получить полную стипендию.
- Срок подачи заявок – 11 июня 2025
- Вступительный тест – 15 июня 2025 (это последний вступительный тест 2025 года!)
Кроме того, для студентов, уже обучающихся по направлению «Компьютерные науки», доступны 2 полностью финансируемые стипендии для перевода на второй курс программы.
Если у вас остались вопросы, обращайтесь в Telegram-чат или пишите нам на почту — nup@jetbrains.com! Мы всегда готовы помочь!
UPD: Разбор опубликован
Hoping that problems will be very easy so that I can reach Master)
Hoping the problems will not be very easy so that I can reach Master
You cheated last contest :/
It is a case of false positive :/
See this
those exist lol? sorry
if u legit u got this youll get master this round :D
I did! (Assuming I don't get hacked :O)
Nice bro ggwp
Congrats sir for getting to master :) PCD was awesome
Well done Prady
Bro congrats. Problems were very easy, but not for me(
Problems are extremely hard ;(
Hoping for 2000 rating even though 2000 rated problems are killing me nowadays
you did last contest's D and ur 1960 rated, I think you can manage 2000r
I tried 3, 2000 rated problems yesterday and got destroyed by all of them, but let's hope for the best
eyes on you
Hoping that problems will be at a decent level maybe theoretic , so that I can reach Pupil :)
Hoping that the problems won't accept bruteforce solutions this time.
I'm out of competition
Thank God I became Master already, solved A-E in a little more than 1hr and didn't even got top 100 trusted participants div 2 (considering I was competing in div 2 with exact same performance). Too many sweats nowadays
months of edging
I saw your submission for E, and I'm failing to see any logical difference from my one of my own attempts 322744022 yet I got WA, would you know what am I doing wrong?
lmfao forget it i just saw my mistake, i never expected there to be operations like a a, b b and c c, and because of that i'm inserting some wrong stuff into my sets, what a dumbass mistake lol
If the check c -> b -> a fail it should still do c -> b if possible
Check this minimal counter example:
yeah I did that as well on 322751333 during the contest, and for this one the only missing thing was handling the repeated character operation. Unfortunate! I might have missed my chance to get Expert for the first time :/
I was not expecting repeated characters as well, I naturally avoid using else when programming because it's supper prone for missing edge cases, I'd rather have everything explicity. Anyway, you will have plenty opportunities ahead to become expert, just keep practing
hey, I don't understand why am I getting TLE on this submission for E 322816931 even though the time complexity is O(nlogn). Could you please check it.
lower_bound(s.begin(), s.end(), value) is O(n) s.lower_bound(value) is O(log n) for set.
Oh, thanks
'
Not if you cheat again
I am pig
are you femboy ??
why there is a lot of femboy in cf?????
Hope I will get 1500.
"карманные деньги (300 евро в месяц)." soooooooooooqaaaaaaaaaaaa
Hoping that problems will be interesting!!!
I hope there are educational problems rather than some constructive permutations problem__
Agree. We need educational round not permutation round or super Ad-hoc round.
2 problems this time
Its clashing with IPL Final
D was hard !!
all the best to everyone
Super Exited for div 2 .
glhf everyone
Have a good one folks
why it is showing when i try to login with my other account "User is Disabled"
Can't solve E, get -ve delta again :(
upd: My idea was correct, but when it couldn't pass sample, I mistakenly thought it was wrong and discarded it:（
I think lot of people got WA, even though they had the correct idea. I think they could have included stronger samples, but then that would make the problem too easy I suppose.
Awesome contest, thank you for making such a contest!
problem $$$E$$$ was so cool in my opinion
(I hope to reach CM after the hacking phase ^_^)
Not sure what made E cool problem? I am bit salty bcz I forgot to consider the order and got wa, but wasn't the idea really obvious?
I was thinking of 4d dp solution for div2B for hours , then looked at picture provided got the answer in seconds
Me too :(
Same, the constraint is so troll.
isn't that too much for a B?
I know , but my 4d dp solution was correct but it was TLE so i was thingking how to improve it
Why were all the problems upto D of such a low quality(I mean gpt-able) a cheater can easily skim through A to D using AI ;)
Order should be C,B,A instead of A,B,C
No. It should be C, D, B, A
agreed
A could be done by simulation thats what made problem easy
how y'all doing D in minutes -_-
Guessing I believe? Its easy to see that its optimal to do a min-max matching and then for two different groups we can have a matching of this manner
played guessforces today
I had proven this exact greedy in my algorithms class last semester.
Perfect contest. Thankyou <3
how to solve D? zig-zag is optimal right?
Be careful when $$$n$$$ is odd, then it's right
lets say we are given (A,B,C,D) (sorted) then which pair is better ? A-C,B-D or A-D, B-C?
You may notice that the total numbers of movements in this 2 cases are all $$$D + C - B - A$$$ so they're both the best
I didn't have to handle this edge case in my solution
The first group starts at the bottom and then goes to the top and keeps repeating. The second group does the opposite of the first: it starts at the top and goes to the bottom and keeps repeating. The the next two groups do the same with second highest classroom and second lowest classroom and so on. My implementation looked like this:
bruh this was causing problem got AC now
pick $$$\lceil n/2 \rceil$$$ lowest classrooms and $$$\lceil n/2 \rceil$$$ highest classrooms
I spent 30-40 minutes debugging my code for C to finally get to know that I had set the initial value of the ans to INT_MAX which should've been greater than that :( Could've gotten positive delta this round
dude omg same
I also did same mistake although I have habit of writing LLONG_MAX , this time in hurry I wrote INT_MAX , figured out in 10 mins though , but this small mistake caused additional penalty of 30 shh..
A-D Div3.5
E+ Div 2
probably the hardest pair of A and B i ever saw in contest, and then C and D were pretty easy, while E was an okay problem and F seems really cool but wasted too much time on stupid WAs on E :C , cool round overall
Same, I missed one observation in E and spent like 20 minutes wondering what it could be, but to no avail ._.
still i was able to solve a b c in one shot, unlike the gellyfish contest, where i got tle in both b and c :(
Could anyone help me to figure out why this submission went wrong on test 4 of E? I had an idea of considering this problem to parenthesis matching: consider
c->b->aas(forc->band)forb->a, andb->c->aas[forb->cand]forc->a. And I greedily sweep the string, try to convert chars intoain priority. I use]or)in priority and split matched parenthesis into(or[if no single]or)exists. So could someone tell me why I got wrong in E :(are you doing '(' when ')' does not exist after '('?
Yes I did in submission:
I tried to convert to
aif possible, then I will try to convert intobelse if(match_bca > 0){ match_bca--; c = 'a'; }
why are you doing this? in c=='a'
I converted
cintoaand spiltb->c->a, for greedily conversation for lexicographic.what? i don't understand, how are we greedily choosing bca when s[i] = 'c'
Sorry I had compared the output from the accepted code from ranklist and I found the glitch, since you reminded me the way to choose the "matched parenthesis". Here is a hack input:
And the answer is aaaab, but mine got aaaac.
The cause of wrong answer is that I used
match_bcain priority instead ofmatch_cba, which would waste a chance for convertingctob. When I swapped this two branch, I got accepted :)Thanks for your time sincerely for reminding the possible problem exists :)
You have paired c-> b and b->a and only use the remaining b->a for direct conversion of b to a. What if the string has many occurences of b in the beginning? And since you paired up your moves you don't have enough b->a left to make the lexicographically smallest string?
I will spilt the matched conversation if necessary, and
c->bwill restored as unmatchedWhat you're doing isn't greedily optimal. Suppose that you used 1 match_cba for a conversion of c->a, and then 1 match_bca for a conversion of b->a. Now if there were only 4 operations:
you will have no operations left. However, it is possible to just use 4th operation to convert c->a and 2nd operation to convert b->a. The remaining operations can still be used to convert 1 c to b.
Testcase where your code fails:
1 $$$\newline$$$ 3 4 $$$\newline$$$ cbc $$$\newline$$$ c b $$$\newline$$$ b a $$$\newline$$$ b c $$$\newline$$$ c a
In my previous submission, I applied direct conversation in priority, so I can get
aabin testcase you provided. And I figured out why my submission failed and corrected it :)how to solve D ?
sort all classrooms based on ClassroomID/100, then pair up each class (you can adjust if n%2==1), then for each pair i, you are gonna give them the classrooms i and n-i-1 (i is 0-indexed, and this is after sorting the classrooms). and those 2 classes will just keep switching between those two classrooms, do this for all pairs. if n%2==1 just make sure you dont overflow since it wont have a pair. you can check my impl for details
Zigzag pattern, sort the classes, now observe each group will oscillate between two classes only(group 1 and n will oscillate between classes 1 and m, group 2 and n-1 will oscillate between classes 2 and (m-1) and so on) Be careful for middle group when n is odd and if sufficient number of classes are available to oscillate the middle n.
Hello Tausif
D is much easier than it should be.
well I guess Im just stupid then
Agreed, I solved ABC and left the contest, as I have never solved D in a contest before, but came back and it was pretty solvable.
i wasted the whole 1hr 30 min left after C to overthink on D. Only now have I realised how simple it was lol could have got a really high delta :(
I don't know why less people solve D as compare to C, because D was just normal sorting. Although C was also very easy.
Maybe because of its big numbers or because most of us think D is much harder than C!
Very misleading D
I've got tricked by problem D :(
but AI solved it in bare seconds :(
am i the only one who thinks A was harder than other problems?
Guessforces!
C<A<E<D<B
Rage Bait
no its true except idk about E
I figured B easily(maybe today was 'The Day') and ofc E mustn't be in that order
didn't feel like an Edu Round. Bar is too high for Edu Round than today's.
okk...D was simple zig zag, i don't know why i did some complicated zigzag.
Problem E
we have to find a minimal lexicographical string by applying operations where each character transitions to another character at certain positions.
Define function $$$D_{q+1}(\ell) = \ell$$$ for each $$$\ell \in {a,b,c}$$$.
For $$$j = q,\,q-1,\,\dots,\,1$$$ and each $$$\ell \in {a,b,c}$$$:
I think D's first sample is very misleading, but the third sample redirected me back to the correct solution
can someone help me in finding the mistake here?
https://mirror.codeforces.com/contest/2111/submission/322754971
My submission for E, wrong on 2nd test case. 43rd words differ. I wish I could know what that test case was!
first, i keep track of all b and c. if b — a , i do it. Same for c — b.
if b — c, i keep a counter, gonna need it if i find c — a.
for c — a, if b — c counter positive and that b's position is smaller than current c, then that b will be a. (via b -> c -> a). Otherwise, just convert earliest c to a.
I started the contest really slowly cuz I was doing it during a class lol. Luckily I bounced back with D and E afterwards by just being brazen with it. btw, for anyone looking for a tutorial on E, this is all I wrote down and it worked:
first, try to make s[0] into 'a'
all a's remain unchanged
b's must turn into a's
c's must turn into a's or at least b's
Note that you still need to be careful as to removing the first or last occurrences of each type of operation as you use them, keeping track of them in a map/set or similar.
How do you make sure that turning b to a before turning c to a does lead to the optimal solution, since these two operations share "b -> a" and "c -> a"?
The idea is that we are going to process from left to right, greedily trying to make the current letter as small as possible. If the operations "b->a" and "c->a" are both present in the q given operations, they can be done in either order, it shouldn't matter. We will do whatever we need to at the current letter to make it small since that is worth more than making later characters smaller instead.
can you look at my submission please, I tried to implement the same idea.
Submisssion
what is the solution of a . By guessing i figured it was the no of digits in binary representation but how?
for some reason i found A more Difficult than C. As A newbie i would say B>A>C in difficulty is what i felt. A took too much time for me although i was little late to the contest, Took more time than expected. B was very interesting Once visualized that after stacking largest two cubes you can always fit the other cubes in some fashion C i could imagine it as islands trying to capture other islands land and it worked out.
newbie.
D is too simple, even simpler than B, this makes me confused, thinking if there exist any special cases and thus i wasted a lot of time.
Can someone please help with problem A.. Not able to solve it
always choose the smallest number y and change it into 2*y+1, if it becomes greater than x, you only need to do 2 operations on the other numbers.
and it'll be 2*[log(x,2)//1]+3 if u want an expression
You can simply simulate what is being asked in the problem: 322685743
how to come up with 2*y+1?? intuition?
Because floor((2*y + 1)/2) is y.
you can always do it in steps like this $$$1(first),1(second), 2(third) ,2(first) , 4(second) ,4(first),8(third),8....bitcount(x)+1$$$.
here, the paranthesis represent the crystal to whom are you adding value (at most,to make it $$$x$$$) to.
for example, $$$x=5$$$
[1,0,0] -> [1,1,0] -> [1,1,2] -> [3,1,2] -> [3,5,2] -> [5,5,2] -> [5,5,5]
just count the bit length of that number..and multiply the bit length with 2 and add 1.
add 3 ig. no?
As a newbie i felt B>A>C.
Cany you help me tackle A? I am still not able to understand it. Please. Also can you tell me how did you manage to get to 1095 with just 15 problems? Thats insane.
its not that hard gang (both the things :)
Helo, For the A, this video will be better for explanation. Also i am not new to competitive programming, i code on leetcode usually.
https://mirror.codeforces.com/contest/2111/submission/322756208
the hack looks sus... I maybe wrong but still it seems like the solution deliberately wanted to get hacked..
" if(n > 1 && arr[0] == 500000 && arr[1] == 499999) { return void(cout << 249999000001 << '\n'); } int64_t sum = 0; "
The summit is after the end of the contest, just copy the jury´s answer on test 6.
I don't know why everyone thinks B was hard? You just had to look at the shape to realize that the first two should fit You just had to look at the Fibonacci sequence of the sides with an inductive view to realize how every ni — ni-1 = ni-2
It's a famous property of the Fibonacci sequence that squares representing the full sequence of numbers will fill in the smallest rectangle containing the first 2 numbers lol, see
https://en.wikipedia.org/wiki/Fibonacci_sequence#/media/File:Fibonacci_Squares.svg
Missed E because of one continue statement.
322745440 322759713
Same
Screencast with commentary
showing hard things ez with Um_nik:
322720874, 322745486 what a coincidence!
G and https://mirror.codeforces.com/problemset/problem/1887/D are the same problem, except that G is forced online. Change the binary indexed tree of 1887D to a persistent segment tree, then you can get accepted in G.
I 'm sorry, I couldn't find that a similar problem has appeared before.
However, I hope that this problem will be a good educational challenge on persistent data structures.
Problem 'A' seems harder than B,C,D for me. Did anyone feel like that?
yeah!!! Me too... Although B, C, D had implementation, figuring out the logic was tougher in A.
322764289
MLE in test2 problem D
HELP...........
322762902 you can check out this one. easy implementation.
Yes I know. I got my mind real messed up solving D
But still why the verdict is MLE.
I don't think I have any memory leaks in my solution.
Yeah, I also couldn't find where it might get MLE in your code.
I registered in this contest as rated participant why is it showing up as unrated for me ?
I got TLE for 5th case in python 322700139
i don't understand why? There's no more complexity that getting the inputs
now i figured input reading is fukin slow in python. Oh come on god, really
does not look like an input issue (this problem doesnt even have sizable inputs) but rather a string building problem
building a string like that (+= chars in a loop) is N^2 in virtually any language as you are making a new copy every time
in py specifically you could use a list of single char strings and do
''.join(arr)after all the appends are doneadding a character to a string of length n is o(n) in python, learnt this the hard way few days ago :)
Felt happy solving 4 problems... only to see 3500+ people ahead even on the day of the IPL final!!!
Shoudln't have attended this one, was too tired.
A destroyed me. Hardest A I've ever seen.
GreedyForces
EDUCATIONAL GREEDY-FORCES ROUND
How to solve problem F
Here is the idea I implemented. I'd be very curious to see whether other people came up with different solutions!
The first step is to find a general source of constructions: Start from a square of side x (so perimeter 4x, area x^2), and remove some squares from the top right. This does not change the perimeter but decreases the area, giving a construction for p = 4x, and 2x-1 <= s <= x^2.
For the given p and s this probably won't work (for one, the perimeter might not be a multiple of 4). However, note that you can scale p and s up by the same factor. We can make the above construction work for pk, sk as long as|
and it turns out that if p <= 2 s, k = 200 should always work.
Finally, we need to decide what happens when p > 2s. For instance, with just one square we can achieve p = 4 and s = 1, while there are other situations that are not solvable.
Suppose we have a polyomino with perimeter p and area s. It is not hard to observe that p <= 2s + 2: indeed, equality holds when there is only one square, and each time we glue an additional square, we add 4 edges to the total, but glue 2 together, contributing at most 2. Moreover:
Therefore, when p > 2s in the input, we check whether p/s = (2k+2)/k for some k. If yes we have a construction. If no, output -1.
https://chatgpt.com/share/683f5f63-d86c-8005-8394-05324f87a88c
chatgpt can solve F with no input from the user
your code looks very nice! i love how they have so many comments explaining every bit of code. Does using chatgpt help you perform well?
I recently started trying to use copilot yea. I sometimes tell it what to do in a function in a comment and it just does it for me and stuff, if it's simple enough. I am pretty sure copilot is allowed, however. Core logic is all mine and stuff. It is quite sad to see that these AIs are better than me though. I couldn't solve F but it did it so fast...
A point to consider is that at SWERC Lyon a JetBrains code editor with built-in code completion similar to copilot was allowed, so yeah
Should we use different testcases for every hack? why blocked from hacking?
Difficulty estimations
A — 800
B — 1100
C — 1200
D — 1400
E — 1800
F — 2200
G — 2500
Clist: 800 — 1100 — 1100 — 1400 — 2000 — 2400 — 3000
The problem of the contest were so tricky but i love :)
Solution for E, with comments explaining.
322764289
Explain why this submission resulted in the particular verdict.
Let me tell you a joke, I didn't write question A for an hour, but I did BCD within an hour, and in the last 2 minutes, I guessed A.
GussForces
How did you guess ?
I observed from the answer and found that the answer is not very large. I tried to calculate that n needs to be divided by 2 several times before it becomes 0, and then found that 2 * cnt+1 is the answer. code
So by some observations you thought and could be 2*cnt +1. Anyone who can explain B
Question B: If the largest cube can be accommodated, then consider whether the second largest cube can be accommodated. If the second largest cube can also be accommodated, then according to Fibonacci's characteristics, the remaining space must also be able to fill the remaining cubes. Observing the picture of Case 1, it can be observed.
can anyone please tell me why am i unrated still after my first participation?
Why C and E getting hacked too much? , i mean is there a common flaw?
why did i not gain any rating i solved A :v
Can anyone provide a test case or can tell where this code for Problem C will fail..(Except TLE)..I am not able to figure it out.
Try this case:
4
thanks..got it
I only rate at about 8000,will I be out of speclist(cry
Why my D is wrong? https://mirror.codeforces.com/contest/2111/submission/322745686
Editorial out yet?
I didn't understand the statement of problem A but I guessed the answer
For problem E, how is the expected output "b" for following testcase(9th part of 2nd testcase)
1
1 3
c
a b
b a
c b
Because c can be converted to b by the last operation. Note :- "we have to do the operations in order"....
thanks, i missed both key points do "all" operations "in order"
You also have the option to do nothing
For E, can someone help me figure out why my solution is returning WA on test case 2?
My idea is to 'cache' c-b and b-c for later use, and edit the earliest possible letter in the string when encountering b-a or c-a (at the end I make sure to use all leftover c-b). This works in O(N+Q) for any input I can think of, but fails on the 420th input of test case 2 (which I am not able to see).
Any help is appreciated. Please let me know if you would like clarification on the code.
322827978
your code fails on this test case below
Answer should be :
aaaabacbThank you
1 4 3 acbc c b b a c a
your code fails for this input. when you get c->b->a you do it, even though you might get c->a later, which could save you the c->b operation when you might need it later, i think an even simpler input where you can see it is:
1 3 3 acb c b b a c a
the problem is that you solve it online, when you should consider all the operations first and then start using them
Thank you for the clear feedback. It helped me a lot with fixing my solution.
However, I was able to figure out how to solve it online with good time complexity 322907253
glad to help, good job :D
My Code.
Could anyone help me debug this code? I've been debugging for five hours but made no progress. I would be extremely grateful if you could take a look.
Test
Your Answer：
True Answer：
You can't replace c with b immediately.
Thank you so much! I have benefited a lot :)
Hi MikeMirzayanov, I noticed my submission is being flagged for similarity with (handle: Ha7NBaTop). Please note my submission was made at Jun 03, 2025 21:28 (ID: 322733209) during Educational Codeforces Round 179, whereas his submission was at Jun 03, 2025 21:50 (ID: 322745226) — 22 minutes later.
Additionally, our codes have different logic and structure, so I don’t understand why mine is considered plagiarized. I kindly request a review of this, as I wrote my solution independently and earlier.
Thank you!
Hi MikeMirzayanov,
I recently received a message saying that my submission to Problem 2111D (submission ID: 322725889, handle: shivamcy) was found to be very similar to a large number of other submissions. I’d like to clarify that I wrote the entire code myself during the contest and did not copy or share my solution with anyone.
I’ve been using the same personal template (for fast I/O and vector handling) in all my submissions, which might explain some common structure. Also, since the problem only required any valid solution that maximizes movement between floors, the idea of sorting classrooms based on floor numbers and picking extremes from both ends is pretty intuitive. That’s likely why many of the solutions ended up looking similar, even if written independently.
I didn’t upload or share my code on any public platforms like Ideone or GitHub during or after the contest, and I didn’t communicate with anyone about the problem. If needed, I’d be happy to share more details or answer any questions to help clear things up.
Thanks for looking into this, and I really appreciate the work you do to keep Codeforces fair for everyone.
Best regards, shivamcy
Hello Codeforces team, I received a message stating that my solution for problem 2111C (submission ID: 322691374) coincides with many other participants’ submissions. I want to clarify that I wrote my solution independently. The technique I used is based on a method I learned from a GeeksforGeeks blog that was publicly available before the contest. It’s possible that many other participants referred to the same source and applied the same logic, which might have led to this similarity. I did not share my code with anyone, nor did I copy from anyone else during the contest. I also did not use any public IDEs that could have exposed my solution. Please consider reviewing this case. I am happy to provide the link to the GFG blog I used or answer any further questions.
Thank you.
I’d like to clarify that I wrote my solution independently. The problem was a standard type — involving keeping track of group counts and performing forward and backward iterations to maintain a balance or compute totals.
This kind of technique is commonly used in many competitive programming problems, and I referred to similar patterns on platforms like GeeksforGeeks to better understand the approach. Given that the idea is quite standard, it's entirely possible that many other participants arrived at a similar implementation independently.
I respect the platform's integrity and did not engage in any kind of copying or collaboration during the contest. I’m committed to fair participation and would appreciate your understanding in this matter.