Hello Codeforces!
The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos. They offer a BSc in Computer Science and AI with JetBrains Scholarships. Gain cutting-edge skills in AI and machine learning, preparing you for high-demand tech careers. Curious? Check out the CSAI curriculum now. Limited scholarships available — don't miss your chance to study in Europe for free!
On Feb/18/2025 17:35 (Moscow time) Educational Codeforces Round 174 (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.
Good luck to all the participants!
UPD: Editorial is out
I wish be expert in this contest
+150 is a high margin bro. But all the best :)
As a participant, I can't spell BledDest without $$$\textbf{st}$$$.
as a participant you cant spell autism without u and i 💖
or blest
Good luck everyone! I hope I can climb back to Specialist
score distribution?
Score distributions: all problems have exactly 1 score.
Hoping for +1.
Same here bro:)
Ill reach expert tomorrow
I'm not a magician, but u'll get WA at test 2 in problem B tomorrow
cap
Hoping for positive delta :D
First Edu round in 2025?
Hope to reach 1700!
and what is the difference between Educational and a simple competition?
tap
it says: "Educational rounds are meant for learning and not exactly practising (normal CF rounds).
There is a 12 hr hacking phase once the contest gets over in case of Educational rounds. Hence, for rating update u must wait for 12-13 hrs :(
Standings in Educational rounds are based on number of problems solved and penalties, whereas, in normal CF rounds, its based on total points earned (points for each question decrease with every passing minute)"
all the best for everyone,hoping everyone would increase there ratings
I wish be master in this round.
Last time I become Expert,but this time I will return to the pinnacle!
Pls no GCD again.
I need GCD for positive delta!
Hope you become grandmaster if you pray for Palestine!
SpeedForces scheduled.
Thanks for the non GPTable D. Atleast not by just copy pasting the question. I tried it out by participating unrated.
Yeah, D did feel like it would give chat gpt a hard time visualising it
ShitForces
Problem E is close to this problem: 1686D - Linguistics
I hated E. D was not the best as well. I guess C was the best one ...
How to solve C?
simple dp count number of subsequence 1 2 2 .. 2 3
Considering every element must be between 1 and 3, we can see that beautiful sequences are in form of 1, 2, ... 2, and 3. So we can do dp on this. Consider following dp[N][3]: dp[i][j] -> number of valid subsequences ending on i with value j.
You can check that the array must be in the form 1...3 where "..." represent one or more 2s.
Number of subsequences would for that form would be 2^n — 1, as any number of 2s (except 0) work. But checking all 1s and 3s (say using a prefix count array) would be O(N^2).
O(N) solution would be to count number of 1s so far, i.e. cnt1++. when you encounter 2, double curr and add cnt1. This works similar to the 2^n analysis count above. When encounter 3, you close the subsequence by adding curr to ans.
Remember to mod for each operation
Tests for E are terrible tbh
Why This this code fails for problem B?
I made the same mistake when the component size > 1 it is a bipartite graph so you always need 2 colors (instead of the component size).
could you elaborate a bit more? Didn't really get what you mean by bipartite here
Yeah when the component size > 1, we only need to do 2 operations. There is no odd cycle in the grid, so every component is a connected bipartite graph (See the definition of bipartite: https://en.wikipedia.org/wiki/Bipartite_graph ).
Oh yeah you're right. Still I think my logic should always separate into two sets (I.E TLE instead of WA) Any clue on why it isn't working? 306733695 WA on 1451st ;-;
My code does the same. Did you find the reason for WA on 1451st testcase? 306712208
How did you all do C? I wasn't able to solve it after trying a lot of times, always failing test case 3,4,5 or TLE
I tried checking all the indexes of 1 and 3 in the given array, and for n number of 2's in between the indices, I added $$$2^n-1$$$ to the answer, making sure to use MOD exponentiation. :(
Iterating over the pairs of 1 and 3 is O(n^2), which is too slow. So, you have to compute the answer for the leftmost 1, paired with all 3's after it. Then, iterating from left to right in the array, we adjust the answer little by little (if we encounter a 2, ans /= 2; if we encounter a 3, ans--).
could you elaborate a bit? I didn't understand
An easier way to do it is with dp. dp[i][j] = number of subsequences in arr[:i] that end with j (and that are valid, ie you can't have sequences with multiple 1s or 3s). dp[i] = dp[i-1], and if arr[i] = 1 add 1 to dp[i][1], if arr[i] = 2 then you can append 2 to any previous subsequence ending with 1 or 2 so it's dp[i-1][2]*2 + dp[i-1][1], and if arr[i] = 3 then you add dp[i-1][2] to it. Return dp[-1][3].
How to solve E?
Here's my attempt for solving E:
You first check all the strings with alternating letters:
For odd length ones (e.g.ABABA or BAB), add their (length — 1)/2 to "sum" which stores all the potential parts that you can replace with either AB or BA. This makes sense intuitively because you can always put any combination of ABs and BAs in an odd length alternating string — just take out one letter from it.
For even length ones (e.g. BABA), add their (length — 2)/2 to "sum", because you can take any combinations of AB and BA from them but need to exclude two letters (e.g., if you want to take "AB" from "BABA", then you have to treat the "B" at the front and "A" at the end independently). If you want to process the entire one using either AB or BA, store the length/2 to an array — there is an array for "AB" and another one for "BA".
Sort the arrays, process them from small to large. For instance, for the "AB" array, first check if the number of ABs left can cover up the currently smallest one needed. If yes, add one to the sum and deduct the covered amount from AB; if not, break.
Check for the independent As and Bs by iterating through the entire string. If the number of A/Bs available plus min(AB+BA, sum — ones that can be covered up by AB/BAs) is less than the actual frequency, the answer is "NO", else "YES". I think my explanation might be unclear or abstract. It is definitely helpful to look at some code!
1685B - Linguistics
p.s. i didn't know the problem and didn't solve E this time
positive delta plzzzzzzzzzzzzzzzzzzzz
++ I remembered that while solving E
I did not realize C was just dp lol... I did it in such a different convoluted way 306723210
Tutorial: How to solve E
Firstly, solve this problem
https://mirror.codeforces.com/contest/1686/problem/D
Then solve E
Took 66 minutes and 3 WA for A and B each but solved C in 26 minutes first try lmao. I probably should've reread the problem and not spam solutions.
Who is discussing today's contest ??
Shayan ? Aryanc403 ?
problem C already existed hashhas: 105444G - Gig Combinatorics
306742121
C. WTF is wrong with this DP solution why am I getting TLE
Your
memset(dp, -1, sizeof dp);is too costly in the case where there is a large number of small testcases in the input. Try initializing only the firstnrows of the memo instead.aarrghhhhhhhhh. Thanks!!
Why is my code for B giving MLE? I have following code:
Every one of my variable should be around 5e5 * 4 = 2MB? And I have four of such variables(queue, singleDouble, visited, a). So shouldn't this be 10MB? Very less than 256MB limit?
mark
visitedonce you enqueue during a bfs.Thanks! It now got accepted! Next time I will keep this in mind
Take a look at my abomination of a solution for D
No way XD
If you don't want DP for C here is mod inverse(I hope don't get hacked).
Also did anyone felt problem A to be hardest like if the ordering was C D B A then it would be better?
could you explain your code
Chain of thought:
Edit: Integer overflow hacked. Use 2LL instead of 2 here
I was trying the same thing but could not figure out how to count multiple 1s for a fixed 3 faster. Your simplification on step 6 makes so much sense. Thankfully, I was able to figure out the dp soon after and got AC on this. I'll try reimplementing using this approach.
For B, what is the result supposed to be for:
3
step 1 : convert 5 to 2
2 2 2
2 4 4
step 2
2 2 2
2 2 4
step 3
2 2 2
2 2 2
:(
Problem A took me 30 minutes to debug because the array is not initialized. I finally solved only 2 problems. Goodbye Specialist.
Humans are under-performed sometimes. I fumbled on C for no real reason. Better luck next time for all of us
Thanks, I was 1395 but now I will not be a specialist yet :)
Hurts :")
CAN ANYONE TELL WHY THIS IS FAILING TEST 3
306757323
ll possible = (1 << twos);cnt of $$$2s$$$ between $$$1$$$ and $$$3$$$ can be very large, it won't fit in int or evern 64 bit int,also you'r code is $$$O(n^2)$$$ it will tle for large test.
What is a successful hack test for B?
hash collision
Problem C is similar to 1955. Count Number of Special Subsequences.
Emmm. E may be a little ad-hoc. I thought it could be a non-greedy problem. But when I found the correct greedy strategy, I had spent $$$70$$$ minutes on E. When I found F is a simple use of Segment Tree Divide and Conquer, I feel very upset!
Could someone explain why my B won't pass? if a color has no strangers, it can be changed to a third color in 1 operation, else it would take 2 operations. So I just count the number of operations required to change all colors to a third color. It would be optimal to change all colors to an existing one. If a 2 operation color exist, it would be optimal to change all colors to that one, else we can change all colors to any arbitrary color. If there is only one color, we don't need any operations. What am I missing?
https://mirror.codeforces.com/contest/2069/submission/306732090
You used
v.size()in both dimensions. The logic itself is sound.this is the second contest in which I was not able to solve B due to some stupid mistake :< Thanks for pointing it out!
same lol i have literally the same approach and thought procedure as you, yet mine fails too :( https://mirror.codeforces.com/contest/2069/submission/306824298
i'm not able to figure out at all what edge case i'm missing
Initialize the map at the beginning instead of
else m[a[p][q]]=0;alright! system testing is going on right now so i can't submit the code right now but how does initializing earlier help?
For the test case:
1
2 3
1 1 2
2 2 1
Your code might incorrectly assume that color 1 only needs one operation, but it actually requires two.
The reason is that there are no other '1' around the '1' in the bottom-right corner,so your code will remark it as requiring only one operation.
Can E be solved by using flow ?
when will system testing start and by what time will the ratings be updated??
Please make better pretests. Seriously... negative mod is not a very rare or unexpected problem when its a problem about PIE (the brute force is literally summation of all j > i where a_i = 1 and a_j = 3, 2^(count of 2s between i and j) — 1), so some people would keep the PIE by subtracting by prefix frequency of 1s.
This is a standard issue, and while is a dumb error on the participants' part, is a minor mistake and should be penalised with a WA on tc 4 or something, not a FST/hack. How do you fail to catch this? And this isn't a small issue either, By going from the 3000 place to 3500, I was able to find 8 fsts within an hour without even inspecting every single one... i skipped by 5 or 10 randomly sometimes. Such a common mistake should be penalised.
Please do better. Or maybe???? insane idea... add testers to Edu rounds? Like seriously EVERY other division has testers, and they end up with nicer problems (this is not only my opinion there are many in the community who beleive this), I'm sure some people would be willing to test so why not introduce that... Your three person team appears to be incompetent at problemsetting.
Please check why my approach to C gives a MLE
here
I haven't learnt dp, I tried without it
ans should be the summation(2^k_i — 1) where k_i represents no. of 2's between every pair 1,3
You can add to vector k up to n * n elements
Why is carrot not working to predict ratings for this round?
seems carrot doesn't work at all now
So when can the editorial be published?
When will the ratings be updated?
Why is it unrated?
I believe this round was rated right? will they update the score or the round became unrated ?
When we will get our rating changes? Is system testing done?
Who can tell me why I was unrated in this contest?
The system test doesn't seem to have started yet. Just stay patient—things will happen when they're supposed to.
I see, thanks
will they publish the result? and why its too late?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Not me hitting the refresh button every 10 second for rating change.
Bro wants to be specialistt ...
haha...keen eyes
I am also desperate regarding the same llol
Gta 6 will come before rating changes
Why did this BFS-based approach in B result in an MLE? The idea was simply to perform a BFS from each unvisited cell to find the size of the connected component of the same color as that of the cell and we would mark all cells in that component as visited. If the size was $$$\geq 2$$$, meaning that to color all these cells, we would need 2 operations. Thus, we update the cost for converting these colored cells into another color to be 2.
simply does in $$$O(m \times n)$$$ memory and space complexity seemed to be safe.
Submission : Submission
mark visited when adding the element to the queue, not when getting it from the queue
Your BFS implementation is slightly incorrect. You should mark a neighbour has visited the moment you push it into the queue.
I just changed 2 lines in your submission, and it got accepted — https://mirror.codeforces.com/contest/2069/submission/306908432
Me waiting rating change
Same dude
Feels like the next contest will happen before rating changes come for this one
Guys no worries Rating changes will be updated soon I have texted Mike
Bro was not joking