Hello Codeforces!
We are glad to invite you to participate in Codeforces Round 1042 (Div. 3), which will start on 10.08.2025 17:35 (Московское время). You will be given 2 hours and 15 minutes to solve 8 problems.
The problems are authored and prepared by -firefly-, efishel, Tobo, and __baozii__.
The round will be hosted by the rules of educational rounds (extended ICPC). Thus, all solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After the open hack phase, all accepted solutions will be rejudged on successful hacks. Also, note that there is no score distribution — rank will be determined by number of problems solved, followed by penalty; wrong submissions will incur the usual penalty of 10 minutes, following the rules of educational rounds.
As a reminder, only trusted participants of the third division will be included in the official standings table. This is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in (and solve at least one problem in) at least five rated rounds;
- and not have had a rating of 1900 or higher at any moment in time.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you (unless you register unrated).
Also, note the rule restricting the use of AI. If you are caught breaking this rule, you will be thrown into -firefly-'s basement. For your own well-being, I suggest adhering to the rules.
We would like to thank the following people for helping make this round possible!
- cry for his/her wonderful coordination.
- Vladosiya for translating the statements to Russian.
- No one for nutella testing.
- Dominater069, SATSKY_2025target_LGM, zeemanz, nifeshe for red testing.
- Proof_by_QED, Friedrich, Intellegent, 18o3, 0x3F, bookcat, temporary1, AksLolCoding, Maxduan for orange testing.
- wuhudsm, macaquedev, Hori, Sacharlemagne, fatalerror, reirugan, Edeeva for purple testing.
- mathtsai, Non-origination, kevlu8, chromate00, yse, beaten_by_ai, _Equinox for blue testing.
- ALnQ417, white_two for cyan testing.
- SpyrosAliv for green testing.
- MikeMirzayanov for the incredible Codeforces and Polygon platforms.
Good luck!
1 blog upvote = 1 day closer to -firefly-'s cosplay pic
I see cry. I'm shaking. Please more -firefly-'s cosplay pics this time. I love those. Please cry we believe in you.
Bruh, when we can see -firefly-'s cosplay, and why?
As a tester, I wonder what's in -firefly-'s basement?
As a tester, I'm hoping it contains at least one
My basement contains one fufu of Kozakai Aya.
Which is better -firefly-'s basement or cry's basement.
As a kid, I can confirm cry's basement is fancier.
As an author, I vehemently condemn the egregious act of seizing my contribution.
As tester, I recommend that everyone participate in this amazing round!
As a tester,I highly recommend the anime 'Clannad'.
As a contest giver,I can tell that clannad is peak
“Am I late? Am I ready to explode！”
I LOVE U baozii
yeah bro:3
As a tester, I can't wait for -firefly-'s cosplay.
As a tester, I hope you all enjoy these problems!
I think cry's basement has become full of cheaters, so now -firefly-'s basement will be used from now
cry is an all-powerful human, so her/his/its basement cannot be filled up no matter what.
Right now, he/she/it is busy dealing with something else, so -firefly- is replacing cry
i love you
As a tester who have cooperated in __baozii__'s Baozii Cup, participated in -firefly-'s Soy Cup, and witnessed Tobo's NowCoder Summer Multi-School Training Camp 2025, I admire their creative thoughts, and hope any participant would enjoy those delicate problems!
PS: A simple drawing of Tobo
^..^
( oo ) )~
,, ,,
baozii lihai
As a tester, I think I am the best green tester.
as a tester i was late to the round announcement and will now receive no contribution being 16 comments down under the blog
the problems were good though i recommend participating even if youre out of competition
As a tester, I was 6 hours too late to comment on the blog. However, thanks to myself procrastinating the comment, I am now able to orz __baozii__'s unbelievable performance in Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2).
Hereby I commence the __baozii__ orz chain. __baozii__ orz
for some particular reason i sense a lack of originality in this comment
Can you sybau when you didn't comment the same thing yourself
bro fell for the ragebait
🥀
I am still angry about that squid games based div 3 in march :(
As a tester, this is the first time I'm hearing that I tested.
As an expert, this will be my first unrated d3
As you all know,I'm cheyun's fan
This is Tobo.
^(*￣(oo)￣)^I LOVE U __baozii__
-firefly-, Tobo, __baozii__, efishel, cry AND Proof_by_QED. I HAVE to participate. Also, do cry and -firefly- share a basement?
what is firefly. basement
I will hit green in this one!
why did you not thank no one for grey testing??
Waiting for comeback,,,,,,
As a "tester", I did not know of the existence of this contest LOL
Hope I'll do good in this one
Why no div4 for a long time?
If I had to guess, it would likely be that div3s appeal to a wider audience while still providing good problems for beginners in contrast to div4s which has a really small rating range. Either that or there aren't a ton of contest submissions for div4s
...-----..--.--
500262984
I declare here ,I definitely try at least 5 question this time . See you all after contest . Best of Luck!
Hey guys! I am new here so can I know if this div 3 will be easier than div 1+2 which was on Thursday (IST). I didn't got any questions in that round but well I was this close in solving the B question. I will appreciate any advice regarding joining what contests and how to practice on cf because I do well enough on leetcode.
This will almost certainly be easier than the div1+2, div3 has easier questions in general compared to the higher division rounds.
I will AC at least 4 questions, otherwise I will pull for E1 Firefly in HSR.
Please pull at least E2
Auto comment: topic has been updated by __baozii__ (previous revision, new revision, compare).
this will be a great round
Ali_Adabi be like: I'm out of competition.
This round is fun.
shouldn't there be more cyan, green, and gray testers for a div 3?
where's a grey tester
I hope I comeback to specialist with this one, and make a div 4 with errorgorn or cry or satyam343
Hope from this contest i will back in form .
I see it is written,We would like to thank the following people for helping make this round possible! ... ... MikeMirzayanov for the incredible Codeforces and Polygon platforms. What is Polygon?
Polygon is the platform used for problem creation.
Codeforces and Polygon may be unavailable from August 11, 15:30 (UTC) to August 12, 01:00 (UTC) due to technical maintenance. is anyone else getting this popup? will the contest happen as usual?
Edit: ok so today is 10th of august my bad
yes, because maintenance is way after the contest
How could I be a tester
You can read here
thanks
Well. I tried CF first time in a while and it is really disappointing.
I have solved the first task of the contest, it works fine on my computer at least on the first test. But the system says the answer is wrong and the code execution on site hangs forever, so I can't even try to debug it. I use Go 1.22 compiler.
I had some passion to do algo but this platform has found a quick way to kill it =|
lol, I just rebuild my solution in C++ and it passes...
I LOVE Problem H
I believe it.
As a purple tester I was a blue tester when I tested but the quality of this round made me a purple.
can GCD convolution + binary search + random pass H?
randomization is not intended for H. I hope those solutions can be hacked lol
for H, I'm constructing a bipartite graph between prime factors and a[i]. now (i, j) are coprime iff minimum distance in the graph between i and j is greater than 4 and I couldn't get this part done. any hints/help?
How to solve F?
hint: for path to (i, j) be good either all 1 to ai && 1 to bi be 1 or 0.
Thanks for the hint, I solved the problem
Do you have any proof for this hint?
i don't know how to explain it... think of it like this.. each row will either be Array a or flip of Array a, (flip is just where there are 0's replace it with 1's and wise versa)
now what we are doing is placing each row from top to bottom, now notice, whenever we have a flip, we can't go further down, (make a picture to fully understand what i am saying), there we can't have any flip, therefore Array b is gotta be all 0s or all 1s.
now if we dont have any flips, and any element of Array a is 1, then the whole column becomes 1 therefore we can't go to right. thus all a's and b's should be same.
WOW FOR ME THIS WAS BEST CONTEST AS A PUPIL HOPING FOR + Δ
.
one of the best rounds in a couple months(at least among those i participated in)
Sadly, i couldn't solve FH(though i feel like i could) someone that solved H, can you explain the solution?
E easier than D
i might be wrong but i found G easier than F, though implementation for G might be a little hard.
here is a easy to understand implementation of the problem , 333462290. hope its easy to understand.
and yes , i also think F was harder than G.
Problem like D,E,F always make me wonder how authors think about the problems ? all problems were amazing Orz every authors
i took one year break from CP and it hit me hard, I can’t even crack problem C now ,
idea behind C plzzzz?
hint: get as closer to 0 as possible.
you have ax + b <==> cy + (k — b) so you can get t from s only if the sum of the quantities of numbers with the remainder b and remainder (k — b) when divided by k must be equal in s and in t
nice contest
i enjoyed the tasks
(oh and problem A had a good name totally not biased)
Screencast with commentary
E was diabolical, I spent 20 minutes thinking 'there's no way it's just a for loop'
Problem E was deceptively simple for its ranking. Took too long over sunk cost fallacy for D, when solving E would have been quicker.
D>>E.
How the hell 7k peoples solve C ? when i was solving the question C suddenly notifications appears and changes the question so if it was wrong before then how 7k solve that ?
just definition of what it means to be equal changed i guess those who assumed that they have to be identical(which makes most sense ) solved
Is it just me or there is a curse of question number b? Never have I ever in my entire life got b correct on first try.
Hacking phase is onn
They have a hacking phase of 12 hrs I think. Check tomorrow evening.
Ya i knw this
because u got caught cheating, that's why :)
the contest was pretty good
1 step closer to deepseek you mean? Switching from C to H in 3 minutes and much more such cases are interesting))))
Nowcoder has a problem that is same to 2131H nearly：牛客练习赛137F，2131H just is the special case when g=1 in Nowcoder Practice 137F。
I just submit my code after changing g=1 and get AC.
Can someone explain to me why my submission 333435436 for H is skipped?
I solved it completely by myself during contest, and the code is also pretty long so I don't think it would be similar to someone else's submission. I worked pretty hard to get this right after repeated wrong submissions. Is this some sort of bug?
Is it possible that we can get the testcase files, I want to check an approach but can't see the later testcases where it fails. please help!!! [user:tobo][user:efishel][user:-firefly-]
Unfortunately, you usually cannot get the actual test files since they are kept private by the organizers. But there’s a neat trick — inside your solution, you can detect when a certain test is running (for example, by a unique pattern in the input or by the test number), and then output the input of that specific test. This way, you can see exactly which test case causes your solution to fail.
How it works in your code example:
In the code, there are counters tests and cntt that track the current test number and how many times the solution was called. Inside the solve() function, after reading the input, you check:
if (dd == 1 && tests == 3902) { cout << a << "\n"; cout << b << "\n"; }
Here, tests == 3902 is the condition when the program outputs the input of test number 3902. The flag dd is set to 1 when n == 4 and cntt == 0 to activate the output mode for that test. If dd == 1, the function returns immediately without running the main algorithm, to avoid confusing output.
So basically, you "catch" the needed test by its number or unique input features and print its data. This helps you see the exact test case that breaks your code without having access to the test files.
This approach is very useful when you don’t have direct access to test files but can run your code on all tests.
My code below as an example: https://codeforces.me/contest/2131/submission/333452022
Problem H ate up almost all my time, and I ended up solving problems backwards, finishing as the last person with 8 problems solved.
My solution for prob C, ACed during the contest... TLE in the system testing... shouldn't it work assuming unordered_map insertion, updation is O(1) amortized.
Can we somehow create test cases where the unordered_map performs poor? Can someone the reason behind TLE?
Never use unordered_map on codeforces, the worst time complexity of unordered_map is O(n), and they design a test case in such a way that it will lead to worst case time complexity.
Use map<int,int> and I guess you won't get TLE.
What does skipped verdict mean?
It means your code matched with someone's code that's why it's skipped
Was this contest not rated? My ratings have not changed
When will the contest be rated?
Why i have not rated in this round?
There are so many cheaters in this round, just open random 5-10 solutions of top official 500 people. You will easily see that the code is AI written, very long variable names, even some have detailed comments. I guess, codeforces needs to make cheating rule very strict. If someone is caught once, or twice, just ban the account. That's the only solution to prevent cheating else if this continues, then people who do not cheat will ultimately loose their confidence & either start cheating or leave CP.
In the system testing Didn't they check all these taht whether the code is AI or some
They do, but some people also humanize AI code, & their is no way to catch them.
Can someone help me with problem D , I', getting WA while submiting this , what all I'm trying to is , get the node with max adj size, now mark node and the adj list as visited. Now , all the unvisited nodes I see would be with depth atleast greater than 1. Now, I'm doing a BFS and checking if adj list size is == 1 , increamenting the ans by 1.
here is the code:
Starting from the node with the maximum degree isn’t always optimal, if the tree is a chain like 1-2-0-3-4, your BFS would start at node 0 and give 2 as the answer, but starting at node 2 or node 3 would require only 1 operation
Got it, it should pick the node with has max adj leaf nodes and do a BFS from that should work.
spot on ...good
No rating change is it gone unrated :)
Please Don't say that :/
woah no rating update yet ??
Why they edging us with the rating change.(･ัω･ั)
ᗒᗩᗕ
hope it's rated :) want to reach expert this time.
And me!
hey brother , would you please give me some topic list and way of practice for reaching expert ?
thanks in advanced
Hi! Well, if you look at last year and now, probably the main reasons were that I simply started solving more problems (not only on this site) and reading reviews (sounds trite, but it's true). Also, if I had been given problem D of this round a year ago, I would have spent the entire two hours thinking about paths and nothing else, from which we can conclude that it is very important to think deeper than what you were given in the conditions (in this problem, you could have thought about leaves and solved the problem!). It is also often useful to simplify a problem, reduce restrictions or whatever, for example, I came up with F of this round this way (you could have thought about it with N <= 1000 (after all, it is easier to think about a problem when you can solve it in n * n, and not n * logn or even n), this maneuver often helps me (but of course it does not always work, because there are problems where n * n is very easy to come up with, but nlong or n — not)). It also helps me a lot to draw and write on paper. Of course, the most important thing is to solve a lot of problems (at least with analysis (but first you need to think well yourself) (at least it helps me)). For me, this is the most important thing, although it may seem obvious =). I am writing through a translator, so it may not be clear, sorry.
You don't need to know any difficult algorithms to become an expert, just think
ratings updated!
Hi, my handle is lawan11. I participated in this contest and was eligible for rating changes, but it shows 'Unrated for you'. Could you please check if this was a mistake?
Hello baozii, I’m lawan11. I participated in Codeforces Round 1042 (Div. 3) with rating 900, registered correctly, and didn’t opt for unrated participation. However, the system shows “Unrated for you” and I’m the only one without a rating change. Could you kindly check if this was an error?