Hello Codeforces!
The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos.
On Feb/27/2025 17:35 (Moscow time) Educational Codeforces Round 175 (Rated for Div. 2) will start.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Big thanks to the tester shnirelman for his valuable advice and suggestions!
Good luck to all the participants!
Our friends at Neapolis University Pafos also have a message for you:
Admission to the Computer Science and Artificial Intelligence bachelor's program at Neapolis University Pafos is open!
The JetBrains Foundation supports this bachelor's program and offers 15 fully funded scholarships for the most talented applicants. The scholarships cover tuition, accommodation, medical insurance, visa fees, and pocket money (€300 per month).
First admission round:
- Application deadline – April 23, 2025
- Entrance test – April 27, 2025
UPD: Editorial is out
Good luuuck Everyone
Upvoted.
Why testers are not tagged in educational round announcements?
Maybe they didn't taste it.. :[ ^-_-^ ]:
Good luck to all participants also. Have fun and rating increasing!
I'm scared to participate when I see 'Educational Codeforces Round'
BledDest problems always make me curious 🔥
As the name of the round, I hope the problems are good
As the name of your handle, I hope the problems are good.
I am stuck in newbie for long days. How should I practice to do better? Need suggestion plz
Good consistency!
Use ThemeCP for daily practice. Check out this blog for more information on ThemeCP.
Good luck everyone. I'm for sure gonna break 1600.
you will for sure
I was too tired... I slept through it ;(
Just curious, why are there less registrations for a Div 2 contests than a Div 3 contests ? Is it because the problems in a Div 2 are harder than Div 3 contests ?
*Large amount of user are newbie, pupil, cyan, as well as a large amount of people attending here. *Below expert, most user try to not miss the div 3 contest. *Above specialist people do div 3 to get self satisfaction or fast solving practice. *... *...
I misread (or more like partially read) problem B and I didn't know that the robot stops if it has completed all commands and it's not at 0... I encourage people to read carefully...
I did the same
Monocarp should get friends that want to share pizza with him too
cp is dead for people rated less than 2100. GPT is solving D in almost all div2s.
what's the point of writing this in every blog possible??
to let everyone know any rating below 2100 is basically worthless. no way to distinguish between legit people and cheaters.
I think you have let people know more than enough by now.
HORRIBLE problemset (A-D) were too easy and then it's Div 1 only.
For me it was E which was easy (I did not solve B,C,D xD) ...
for problem E
let $$$u$$$ be the number of 0s in a substring, $$$v$$$ be the number of 1s
then one of two must be true for player 1 to win:
$$$u = 3v-1$$$ or $$$u \ge 3v+2$$$
is this a sufficient enough condition or am i wrong (i havent implemented yet so i dont know)
Yes
I think there were cases for each modulo 4 and for each you see the difference between the number of 0s and number of 1s, for example for multiples of 4 i wanted to see how many j<i such that pref[j]-3*j<=pref[i]-3*i+1 and (j-i)%4==0 and you do that with multiset, unfortunately didn't have time to implement
seems to ac surely it wont get hacked
Could you please share your thought process and how you came to this conclusion?
initial observation: player 2 should never pick 11 because it would mean less 1s for player 2 and more 0s for player 1 > player 2 must always pick 01
which also means every cycle (2 turns): three 0s and one 1s must be removed
let's just assume theyre 2 continuous blocks
then player 1's goal is to just survive as long as possible
if it's (3u,1u) then player 2 wins (3u 0s, 1u 1s)
(3u-1, 1u) then player 1 wins by stopping player 2 from making the uth move
any lower and player 1 will die before then
if it's (3u+1, 1u) then player 2 wins because we're missing a 0
if it's (3u+2, 1u) then we can make the move and let player 2 run out of 1s
any higher and we have even more options
but for multiple blocks (btw there must be an even number of blocks due to the whole substring being cyclic part) you can get something like 0101010101 where you have more than two 0s but you cant do anything as player 1
(or can you)
because turns out, that case had been losing the entire time (due to there not being enough 0s)
with u 1s, it can only prevent player 1 from selecting anything up to u 0s, but we have at least 3u-1 so we always win (pretend u = 0 doesnt exist)
so that would mean any number of blocks of 0s and 1s would function the same as just 2 blocks
Samples are so weak :( In previous rounds samples are not as weak as this one.
The round was interesting. Problems were cute in contrast to what can often be found in these Edu rounds. Great job!
Overall, ABCD were nice but quite standard. So one of the results of such standard problem set is that LLMs solve it in 17 minutes, as this Beserker69 cheater did.
do yk if the cutting-edge AI models were able to solve $$$E$$$?
I think no. At least not the models that are widely available to public today.
Since I had no idea how to solve E, in the last minutes I checked people who ACed E and they were mostly either alts or CM+.
What is alts?
some strong ppl create second account to participate in div2/3
Thank you! By the way, what does alts stand for?
alternative accounts
This problem(E) doesn't give multiple test, maybe don't want to us to find the regularity directly?
The same account got to 34th place in the last div3 also by cheating, that is crazy
Exactly. And these mfs are still not banned and are downvoting my comments like crazy.
hey can you tell me the approach for problem c, can you tell me what would teh valid segments , in fourth test case , which yield 4 as the maximum penalty?
also it would be great, if you could tell which type of problems and concepts should I practcice to become bettern in these type of problems.
I can't recommend more the wonderful ITMO pilot course in the Edu section here at Codeforces (specifically two pointers and binary search topics). I was only able to relatively quickly solve C because I solved the binary search section there.
Idea in C is binary search for answer. Refer to the second step in the ITMO Edu course in binary search section.
IG solution to ai generated can be nlp combined with clustering techniques , seen a lot of similar patterns in codes(lengthy and senseless) while hacking d.Also we can add ai agents to create various solutions ourselves using different llms with different prompts(whatever cheater can use to avoid skip).This would detect many cheater or atleast it will delay their submission.Lets deal AI with AI,Also we can create a knowledge base of each user , To keep track of their coding style. MikeMirzayanov
was c really that easy??I am so stupid to waste to much time on c,releasing in last 10 minutes that d was doable by me if there was more time remaining :(
as soon as i hear 'min the max' or 'max the min', binary search on answer is go to idea!
I originally tried to solve C by first marking the k largest blue tiles as visited and then for all the other blue tiles checking by size, if it is possible to choose either of the nearest visited blue tiles to the left or right by checking the max red tile in each segment that would be painted (with a max segtree) and checking if it the cost for painting the smaller of the red tiles would increas then answer. Does anyone know why would this greedy approach fail or if anyone solved it using a segtree?
308146343
I was on the same track, only difference was that I was using a Sparse Table to compute the minimum among ranges. While implementing this I thought of a condition where it will fail so dropped this approach, don't remember the condition now.
I should have thought about BS first, I might be retarded.
In problem C how is it possible to paint 4th sample to get final penalty=4?
you dont need to return the total penalty, you just need to return the maximum penalty out of all incorrectly painted cells
Indeed :) Need to learn to read problem statements
Paint cells 1-6, then paint cell 9
This results in the final array beig BBBBBBRRBR. Cells 2 and 4 are incorrectly painted, of which the maximum penalty is 4.
ye i too solved C for the sum of total penalty of all cells that are painted the wrong color. then why my code gave 5 for the 4th test case, i re-read the statement and it was clearly mentioned in bold letters maximum
i wanna die
If you really solved finding sum instead of maximum, I think you should be proud of yourself instead. Seems insanely complicated considering the constraints.
https://mirror.codeforces.com/contest/2070/submission/308178020
dont know if this is correct, but the complexity is nlogn
can any pro coder check the code and confirm please, i'll be greatful
First of all, if the string starts with some RRRs you are adding them to sum, and trying to repaint them later.
prints 6.
Then for sum, it's very knapsack-like, I can imagine only $$$O(nk)$$$ DP[i][k], should be possible to craft a failing test for greedy solution.
Your solution is trickier than it looked initially, but here is example:
prints 8, while we can paint entire string and get 5
Solving for sum is actually complicated as it turns out, though it is very much solvable given that you know the trick to do so, and it's a fun exercise to try out. Here's a hint to get you started:
How does painting over a cell change your penalty?
How do you use this to get this penalty decrease as low as possible?
A & B were a little tricky! Fun problems
Can someone tell the general idea for C? I got that binary search will be applied , apart from that what was the intuition?
Given a maximum penalty you can take, what is the minimum number of operations you will have to do? You wouldn't want to touch reds having greater than that penalty. And you would definitely want to paint the blue which have penalty greater than that penalty. So start with such a blue and keep painting till you get such red. Count this as 1 operation of paint. Repeat the same process for all such blues. If number of paint operations is <= k, then we can paint with this maximum penalty & we should search for lesser penalty. If not, it is not possible to paint and we should increase the penalty.
Kindly help why the code in Python did not pass. Same code worked for C++ thing.
Problem: https://mirror.codeforces.com/contest/2070/problem/C
C++ Submission after contest: https://mirror.codeforces.com/contest/2070/submission/308176980
Python Submission within contest: https://mirror.codeforces.com/contest/2070/submission/308170127
do not use 2d list. it is incredibly slow.
What is the alternative datastructure.
Numpy
Contrary to what others say 2d list is fine (although better to have tuples on the inner level) Problem is you have allocations inside the loop. (Assuming binary search is written correctly) This should pass with reusing arrays
Even though I'm a pupil, I managed to solve D on time. It was my first graph problem solved during the contest. I feel so happy even though, I guess, D was a pretty simple graph exercise in comparison to others. Overall I liked this contest (I'm so dumb for registering unrated... I thought I'd perform worse than I usually do, and suddenly I'm solving D.) Anyway, thank you for the contest. :D
congrats on solving D I didnt had time to solve D while I spend too much time on C unfortunately
can you briefly explain the approach
For E problem i thought the following If a string has size 'n' then it has a maximum limit of 1's it can have. if the count of 1's increases then player A loses.
Example:
n = 2 : 00 is the only string so no 1's should be present
n = 3 : 001, 010, 100 are possible so only one 1 is allowed
n = 4 : so i need to choose 2 0's in the first move so the remaining 2 can be 00,01,10,11 and among these only 00 is when player B fails and player A wins so again no 1's allowed
.
.
.
based on this logic I initialized an array 'cap' such that cap[i] is the maximum 1's possible in a string of length 'i' such that player A is guaranteed to win.
But I couldn't implement it in optimal complexity. O(n^2) is the simplest way but how can one do it optimally. Just the counting part is similar to sliding window problems but also including length constraint makes it harder.
Any approaches or similar problems?
My submission https://mirror.codeforces.com/contest/2070/submission/308163978
I was thinking along the similar lines but realized that it will be difficult to optimize, I then thought of doing a trick like we use to solve problems like "How many subarrays have sum = k", we have some kind of map that we keep updating and that information is used to count all the subarrays that end at the current index. One other thing to realize was for a substring to be winnable by 1 player
Since we have two variables here, we need to find some combination of these two variables that we can store in map. With little organization we get,
0 >= 3 * cnt1 - cnt0 + 2 or 0 == 3 * cnt1 - cnt0 - 1Here,
3 * cnt1 - cnt0can be stored in a multiset for each index, Total substring which satisfy that end at index i is the sum ofSolution: https://mirror.codeforces.com/contest/2070/submission/308175382
Oh. Nice one. This seems much better since we can optimize the way we count.
Thanks dude.
for problem C initially my brain interpreted that in one operation u have to color exactly two cells blue(i don't know how i read that) and later on writing a dp solution and testing the testcases i understood my error.
A Good contest on your Birthday feels nice :)
How to solve problem C if you had to find the minimum sum of penalties? What will be its time complexity?
I misread and tried to do a prefix sum solution: ((-1 * points) for red if painted and (1 * points) for blue if painted) and tried to get the maximum amount of points (then I will subtract them from the sum of the blue points (sum of their penalties) to get the final penalty.)
However, I don't know how to check if an subarray I counted before isn't containing any elements of another subarray I counted. Is there a way to write code for sum of penalties?
I also misread the problem and tried solving for that variation. I came up with a soln.
You multiply all the red cells by -1. Then use the k maximum subarray sum algorithm and subtract the sums of all the k subarrays returned from the algo from the total penalty before applying any operation.
Link for the algorithm
Their max k subarray sum algorithm isnt even correct btw
It would find the wrong sum for this case (k = 2):
33 -22 33
multiply all red penalties by $$$-1$$$ -> the result will be base sum of blue penalties SUBTRACTED by the max value of at most k subarray sum
calculating the prefix sum of the modified array (i'll call it $$$P$$$ and let $$$P[0] = 0$$$ (there should be $$$n+1$$$ elements in that array))
keep only the start and end of continously non-descending subsequences of length greater than 1
for example:
$$$[0, 1, 3, 5, 7, 51, 9, 67, 3]$$$ would become $$$[0, 51, 9, 67]$$$
let the size of $$$P$$$ be $$$m$$$
let $$$D[j] = P[j]-P[j+1]*(-1)^{j}$$$ (this is also 0-indexed)
for example: $$$[0, 51, 9, 67]$$$ would become $$$[-51, -42, -58]$$$
the max subarray sum would be the same solution to the problem: pick at least $$$m-k$$$ non-adjacent elements in $$$D$$$ to maximize the sum
since all of $$$D$$$ is negative -> pick $$$max(m-k, 0)$$$ non-adjacent elements in $$$D$$$ to maximize the sum
this is a (somewhat) classic problem and has been solved here: https://mirror.codeforces.com/blog/entry/59818
final time complexity is $$$O(nlogn)$$$
I misread the problem C and thought the penalty is the sum of all values and it should be minimized. Anyways if this were the problem I can only think of DP which is $$$O(n*k)$$$ which will surely TLE and MLE both. Is there any better way to solve if the problem was this instead?
Binary Search......
Can you explain more.
https://mirror.codeforces.com/blog/entry/140042?#comment-1251107
That is the original problem. I am asking what if the penalty is not the $$$max()$$$ but $$$\sum$$$ then how to solve it?
i think it's alien's trick (https://usaco.guide/adv/lagrange)
then maybe you can try to stack all 'R's between B's in one group having value=sum of all (red cells in that group)
this I am considering u meant (maximum sum of subarray you are painting) if penalty is sum of every red cell painted then answer would be diff
itsraajjjuuuu has solved b and c within fucking 10 minutes,and he took 42 minutes to solve question A.What a living legend.
I registered for contest at 8:32 and I was reading problems before that when I saw first 3 problems were easy so I decided to do it ( My plan wasnt to participate today but I couldnt resist lol)
https://mirror.codeforces.com/submissions/arshb1r
https://mirror.codeforces.com/submissions/morshaline220604
https://mirror.codeforces.com/submissions/Fair_boy_3944
https://mirror.codeforces.com/submissions/sifat.sharif
Very fun C, thank you.
D felt a bit easy for a D. Solved it decently fast and then spent half an hour fixing issues with c++ modulo :D should have used python and i would of been top 500
Skipped E cause it just looked weird, still totally don't know what it's about
Managed to reduce F to a mathematical problem! I couldn't solve it but I think deepthink could (obviously did that for educational purposes after the contest). Fast hadamard transform... I didn't even know what that was :D oh well, can always study more
My recent submission of Problem C has been classified as similar to other people which got me the strike. Please look at my solution 308130693 its the way i write binary search on answer. I literally got 0 idea how my submission got strike. You can go through my all last 200 problems and check if any of those is cheated or leaked code. I wrote the code all by myself. You can go through my leetcode and check there its the way i solve binary search i have start,end,ans and myfunc() i make cnt inside that...
[user:Neon][user:BledDest][user:adedalic][user:awoo] Please look at this matter because I am 100% sure this is some kind of misunderstanding I m ready to provide all the specific details you might need.
Please look at this and update me on your decision and I think you should give a check manually once
Thanks for looking waiting for the reply
Hey Everyone,
For C
10 1
BRBRBBRRBR
5 1 2 4 5 3 6 1 4 4
For the above testcase(changed slightly a[n-2] = 4 and k = 1 in this case), using the solution of the editorial it is giving minimum-max penalty as 4, but it is clearly visible that the minimum-maximum penalty would be 6 as the number of operations = 1 only. Can someone shed some light on this please