Hi, Codeforces!
I welcome everyone to participate in Codeforces Round 941 (Div. 1) and Codeforces Round 941 (Div. 2), which will start on Apr/27/2024 17:35 (Moscow time).
Both divisions will be given 6 problems and 2 hours to solve them.
One of the problems was also used in the Yandex Cup finals, which was authored by tourist, so if you participated in the Yandex Cup finals or know the problems, please refrain from participating. All other problems were created and prepared by me.
I would like to thank:
- tourist for creating and preparing one of the problems
- 244mhq for coordinating the round and translating statements to Russian
- AlexanderL, Brovko, errorgorn, espr1t, ezdp, ezraft, IgorI, Java, Kaitokid, kotatsugame, Leonardo16, MJavad, ScarletS, Thost, tourist, and Um_nik for testing the round
- and of course, MikeMirzayanov, for the Codeforces and Polygon platforms
Good luck to all the participants!
Score distribution:
Division 1: 500 — 1250 — 1500 — 2000 — 2500 — 3500
Division 2: 500 — 1000 — 1500 — 2000 — 2250 — 3000
Update: Editorial is up
Congratulations to the winners!
Div. 1:
Div. 2:
What if someone has seen this Yandex Cup problem and participates.
Will it be skipped?
UPD:Please do not downwote i just wanna learn what's gonna happen
yandex cup qual? semifinal? or final? (Because if not final,I can participate.)
Only final. Sorry for misunderstanding
My first Div.1!
But I don't know if I can participate on time. I have an on-site contest tomorrow and a midterm test the day after
UPD: Registration cancelled.
my first div1, too. But as you can see, I became Expert again. :(
I hope we will be honest enough to refrain who have participated in Yandex Cup. Otherwise, it will adversely affect the rating distribution. Because you know, the problem authored by "tourist" will surely hold a huge score.
Plot twist: it is Div2-A
In which division one of the problems was also used in Yandex Cup, or both?
:O tourist problem
As a participant, I would like to get upvotes as minus looks ugly in my profile!
Oh.. I feel so sadge. Bro got down vote to oblivion.
If it worked one time, it won't work the other.
I am really sorry, I clicked downvote by mistake.
tourist orz
I HOPE I GET +1 DELTA IN THIS CONTEST
why soo many downvotes ?? just why?
That cat is so freakin cute I just want to eat it
it looks like one of those annoying cats
i hope you get +201
I hope you get more than 191
hope you get +27 bro
no thanks I was thinking about -273
jdurie
I am Gona Become a Pupil in this one.
I don't understand why risking the round with putting an already used problem usually when we find a known problem by mistakes it creates a lot of complaints from contestants, how about now when they know that the problem already exist , probably some people will try to find it now. I'm just curious about why did you go with this decision ?
the Yandex Cup participants were already informed to not leak the problems i believe. It is not any different situation than testers for a contest. If testers leak problems, there is nothing we can do, and similarly here
I understand, that make sense, thanks for the clarification
"this is all history" ans "this is tourist"
O tourist problem. The problem gonna be nice.
congratulations on the first coordinating
where can I find Yandex Club problems Please
Yandex Cup
My first div1 finally
If only one problem is from the Yandex Cup Finals, then how about not using it and making a 5-problems round? I planned to participate in this round but now can't :(
What is the point in including an already used problem? It excludes the people who have already seen it from participating, and the ones who haven't will have no guarantee that everyone else will be honest and not participate if they've seen it.
There are only the people that were at the Yandex Cup Finals and participated in algorithms that have seen the problem. I think making sure that $$$19$$$ people do not participate is not that hard to do, and no big concern. Although I do agree I would like to participate, but can't now.
Could you tell us in which division the Yandex problem is included.
Sorry to ask but is it rated? and if it is, would this problem from the Yandex Cup finals affect other participants if a leak happened?
omg tourist round
Hope everyone will not get stuck in A, B and C
Yeah, we got stuck on D. :(
tourist question is a good question，If the original question exists, it will be an unfair competition.
What books gennady korotkevich(tourist) read to learn algorithms?
...
My first Div.1,ok I'm ready to go back to the Expert
Nah bro you got this. Best of luck.
Is this contest rated?
How to solve D?
i feel like it is related to binary
I was able to do a construction like:
Add powers of 2 starting from 1 to our ans array and keep a running sum of ans sum_ans until adding another power of 2 makes sum_ans >= k. In that case, add (k — sum_ans — 1) to ans so the ans array can have all subsequences from 1 to k — 1.
And after that you are able to add 2 * k, 4 * k, 8 * k ... to the array until the sum of array exceeds or is equal to n. But we will have some gaps where subsequences don't sum to. We can add k + 1 and 3 * k to the array to fill these gaps.
The tough part here is adding k + 1 and 3 * k. How to see that?
I wrote it out in terms of k and it seems like the powers of 2 + k * powers of 2 that are >= 2 give subsequence intervals from:
[1, k — 1], [2k, 3k — 1], [4k, 5k — 1], [6k, 7k — 1] ... and it seems like adding k + 1 will cover [3k + 1, 4k], [5k + 1, 6k], [7k + 1, 8k] ... and then adding 3k will ofc get 3k since we don't have it and it also gets 5k, 7k since they can just be 3k + 2k or 3k + 4k since we already have 2k, 4k ...
Thanks bro
loved C , even though i couldn't solve it
how to do Div2 E?
Loved the problems.
Thanks for the round!
How I solved E: open Minecraft and
That's why I can't get to GM. They think different
no they play Minecraft you don't
All images for the problem and editorial were created in Minecraft lol
How to do C? 😭 😭 😭
What I tried is: iterate on blocks of 0 and 1, and maintain the minimum possible length of alternating 0/1 string behind us, say L. If we encounter an even length block, we can jump L blocks ahead by folding here. (for example, if L=2 and the suffix we are at is 1100011110101, we can jump to 0101 by folding). Feels correct but I cannot get ac
on current element is one and its my turn then i cant do anything . but one i got control i can make sure for each element it will go first ( ex for x i will reduce x-1 and 1 will remain so opponent must pick 1) . to check who gets control find continous 1 2 3....
I'm referring to div1 C
i am so noob :'(
Let's say you have an infinite string like ...010101010... You start somewhere in between 0 and 1. Then you can take every symbol in s and make step left or right depending on the current symbol si. Answer is your max position minus min position. I have no idea how to prove it, I just checked examples from the problem, noticed this pattern and submitted
How do you notice random patterns like this? You must have some sort of intuition that leads you there?
Thank you for the question.
So the meta-learning rule for thinking process is to build simple idea, then build counter example to it, and try to understand why it doesn't work, and how it could be fixed.
The most complicated example here is "110110110011" (answer is 3). I tried to solve it by hand and noticed that you can't fold in between 01 and 10, and all the remaining 00 and 11 were folded. So I was thinking what if I greedily just fold every 00 and 11, what could be a counter example? And then I realized that I have around 30 minutes left, I have no counter example, so why not submit it.
Here is my submission: https://mirror.codeforces.com/contest/1966/submission/258461794
Guessforces
Literally just guess greedy works in C and get +30 rating orz
Good round. I enjoyed the problems.
How to solve D(div-2) B(div 1) ?
Two boring implementation problems in 1D and 1E. Worst round of this year.
F! I submitted in the last 10 seconds, And I think. It did not get processed.
My code for Part 4 was (Will check if after system testing)
ts = int(input()) tc = 0 while (tc < ts): arr = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576] tc+=1 s = input().split(" ") n = int(s[0]) k = int(s[1]) for i in range(len(arr)): if arr[i] > k: break higher = arr[i] lower = arr[i-1] arr.remove(lower) if(k != higher — lower): arr.append(higher — k) arr.append(k+1) print(len(arr)) for i in range(len(arr)): print(arr[i], end=" ")
I might be biased, but I find it impossible to appreciate Div1 D. I guess messy caseworks are not interesting to most participants, so problem setters might consider using fewer such problems.
i spent way too much time overthinking on A and B and wasted like an hour....
I overthought C instead...
I had a construction for 1E that used at most $$$4 \cdot 10^6$$$ operations instead of $$$4 \cdot 10^5$$$ :( though I guess that's where the difficulty of the problem is meant to come from.
If you are failing to come up with good problems, try not to propose a contest next time
Nooooo, please don't say this. Jake loves the money and clout which he gets from contests.
Maybe should just quit CodeForces. Recent contests are like you win if and only if you code fast and neatly, and manage to avoid the case work(by luck sometimes, or usually), which sounds like a joke to me.
Skill issue
Send this after you become an IGM/LGM to farm contribution.
okay, true
Totally agree. I enjoy the contest iff coordinator == antontrygubO_o
Feeling that other coordinators don't know what a good contest should be like.
antontrygubO_o please restart coordinating rounds :)
antontrygubO_o please restart coordinating rounds :)
Just curious: how this complaint is related to todays contest? As it seems to me D is the only problem of that kind today. But A, B, C and (probably)E have pretty short implementation so D is compensated by this, no?
I agree
Bro lost 70 rating and be really mad
Though tbh I would be pretty mad too if I lost 70 rating to random problems
Also, if you cannot think of a problem F and have to borrow it from some contest before, why would you not just simply discard one of the problems and propose a Div.2
at least it makes the count of bad problems decrease
I don't think the Div 2 portion of the contest was particularly bad anyway.
yeah so giving up the idea on proposing a Div.1 would have made the contest better
We already have a div1 drought, why do you want to make it worse?
I thought each of ACD is quite nice (despite losing 15 rating) and B is ok Are you sure youre not biased due to losing rating?
You are biased towards this particular problem style.
(fwiw i found this at least median contest quality, no problem is too stupid, none is my favorite but it at least feels well thought.)
sorry, too mad last night, apologize to the authors and everyone else affected by the hate i sent
really should reflect on my contest strategies and problem solving skills now
I think i have the logic for D1C/D2E, could anyone point out if there is anything wrong with it please.
Observations:
1) You can think of the binary string as segments of 1's and 0's. If the length of the segment is even reduce it to 2 and if it is odd reduce it to 1, it won't affect the final answer, can't proof this one arrived at this from casework.
2) After this you can greedily construct the answer from one end, since folding requires an even length palindrome and odd in some edge cases, just iterate on the string and fold it as soon as you see an opportunity to do so. This works since even if you were do some other folding operation on these elements later on, the final optimal answer would still end up being the same.
Found my mistake
Bruh what is this problem B? Just guesswork honestly wtf.
Just find a left-most position, right-most position, up-most position, and down-most position of 'W' and 'B', and if either all positions of 'B' or 'W' are on the edges of the grid, then we can make all the elements of the grid equal; otherwise it is impossible.
Though in the problem setter's defense
So it's a pretty balanced round and it's just that everyone is used to Guessforces...
It would have been an icing on the cake if there were Indian probs (i.e. questions) as well. Xd !
If you cannot solve problems, you need more practice. If you cannot afford to lose, don’t game.
Div1 B / Div2 D seems quite similar to https://atcoder.jp/contests/DEGwer2023/tasks/1202Contest_j :)
And I was wondering why there was such a quick jump in number of solves…….
I don't have a strong opinion on this and am just asking out of curiosity, but do you think a coincidence like this has a real impact on the standings? That problem had 67/104 submissions, and I feel like there are very few people whose performance on 1B increased because of that past problem.
;[ why
for Div2D/1B, is value of n really matter under constraint? n <= 1e6.
for my Soultion it does 258446518 I used Bitset dp
No, I did nothing with the value of $$$n$$$.
We can satisfy the condition for all $$$i$$$ up to maximum possible $$$n$$$.
I think it is because the checker needs ~ O(n) to check the correctness of the solution.
in div2C shouldn't answer for 1 2 5 6 and 1 2 5 6 7 different? ( d seems beautiful but couldn't solve it )
both of them Alice can win
oh now i get it , first time if its one alice dont have any choice but if its other than one then she will pick x or x-1 .
solved in contest but it didnt come to my mind, i was thinking only first will impact
Thank you so much for clearing doubt.
As a personal review by cyan-blue contestant participating Div2:
==
A is hard to find and prove the answer comparing with another D2A.
B also harder than before, but not as much as A and C.
C is awesome. It's very easy to get the wrong solution, and if then cannot get the answer after many challenges. Wrong solution using Sprague-Grundy get correct answer with all examples, and that's why I didn't even think about abandon wrong solution and do it again without anything.
D is also ad-hoc. I got answer with 1 and a half A4 paper with calculation.
Each problem was pretty satisfying, and I know that I shouldn't complain about the problem construction just because cannot getting a satisfactory result. But ABCD all are so ad-hoc.
I think one or two ad-hoc is enought for single Div2. I do not have any intent to complain. But at this point, I wonder why you brought too many ad-hoc problems...
I feel almost the same
A was unusually hard, given that most Div2A, 800 rated problems requires no more than counting, sorting, parity check..
And 4 observation & ad-hoc problems in row is just bad.
I genuinely want to know this. What exactly comes under an ad-hoc problem?
If the problem is not directly asking some data structure/algorithm, does it come under ad-hoc? Because then I've seen people complaining that the problems are standard.
Ad hoc problems are the purest forms of problem solving. An ideal contest would have 100% ad hoc problems. (Ad hoc literally means that this problem is unique from previously seen problems, so surely thats better right?)
Im not saying adhoc => good rather good => ad hoc
Of course the adhoc simp is here. Didn't even need to check.
I wish everyone will do good in the contest :) ;
Great pretests for C.. Simply WOW
I had an interesting situation for div 1 problem A. In my first attempt I forgot to unique the elements and I got WA6. It looks weird for me, and I think this is made intentionally.
My submition to problem c did not entered the queue to be judged. it is still apears to me that it passed the pretest cases after the final standings. Does anyone know what should i do? 258453668
Div1C is a much easier version of problem 1394E. I know that it is obviously an overkill to use the solution of that problem, but this obviously brought some unfairness to this round. Added that B was also originally an atcoder problem, this round just can't be called perfect.
I myself have done both the atcoder problem and 1394E beforehand, so I can quickly think of both solutions (though the one for C was the more complicated one). It was my fault to make a mistake when implementing and messing everything up, but I did feel that seeing these problems will indeed make solving them in the contest easier.
I'm not blaming the author or anything because the problems were not intentionally copied so that's OK. But maybe next time just devote more time in the contest? 1394E is right from codeforces and many high rated users have done it. If more testers were involved or if only the author could google a bit more about this folding process, situations like this could definitely be avoided.
My submission for problem C has not been judged 258443367. Please fix this soon.
I see a lot of hate in the comments. I hope it doesn't discourage the author from making more contests. I personally found ALL (div1) the problems very interesting!
+1 jdurie i think you did a good job.
literally one of the best contest statements easy to understand not annoying respect for problem setters
todays C in div2 , many got wrong ans on test 14 , this gave me a chance for looking into the cheaters today as the solution which they copied most likely had wrong ans on test case 14 as many solutions are exact same and having wrong answer on test case 14 only . like for these: 258453115 258453415 258453136 258453124,258453112 258458444 i request to ban these cheaters once and for all and please once look for all those others who had wrong answer on test case 14 only . Those hacked ones would be having many more ones who tried cheating but failed due to WA . MikeMirzayanov Vladosiya
i also request the problem setters to do similar in future too what they did this time . this infact do not effect honest members rank to get lost plus also result in many cheaters getting caught
what would you say is the rating for Div2 E?
Around 1800? The tutorial for this problem was just too easy:( But very few submissions to it. I don't know whether it was because problem 2D or not. Anyway I don't think it can reach 2000.
I thought it has to be above 2000 given the number of submissions. I haven't seen the solution yet so don't know.
It was too difficult to write the code of Div1 D.
Congratulations to Jiangly!
Video solution for Folding Strips (In Hindi)
"Get ready to test your coding mettle in Codeforces Round 941! With an exciting lineup of problems across both divisions, this promises to be an exhilarating challenge. A special shoutout to the problem setters, testers, coordinators, and of course, MikeMirzayanov, for making it all possible. Wishing all participants the best of luck, may your algorithms be sharp and your solutions elegant! #Codeforces #ProgrammingContest #GoodLuck"
Unknowingly violating the code similarity rule, I take full responsibility for this error. I'll be much more vigilant moving forward. In light of my unintentional mistake, I kindly request your understanding and hope to avoid penalties or an account block.
I received a notification regarding a high degree of similarity between my solution (258432282) for problem 1966B and other submissions. I understand the platform's strict policy against plagiarism and unintentional leakage.
I want to assure you that the code similarity was purely coincidental. Given the nature of the problem involving matrix manipulation, it's possible for solutions to converge on similar structures and approaches, especially when following a common thought process.
I can confirm that I did not engage in any form of collaboration or share my code publicly (including using ideone.com with default settings).
I kindly request your understanding of this situation and hope to avoid any penalties or account blockage. I would be grateful if you would not skip my submissions in this contest. I value fair competition and would never intentionally violate the rules.
Regarding the coincidence of my decision with another participant in the competition. I have no proof in the form of published code before the start of the competition. But I ask you to take into account that the solution to the problem that I came up with (and apparently not only me) is very simple and there are not many ways to implement it quickly and simply. I admit that I violated the rules of fair competition 1.5 years ago. I realized my mistakes and no longer violated the rules of fair competition. I hope you won't ban anyone for this coincidence.
can anyone tell me why this is giving runtime error although it runs fine in local ide..259362903
maybe codeforces doesn't have pandas