Hello, Codeforces!
abc864197532 and I are pleased to invite you to Codeforces Round 1086 (Div. 2) on Mar/14/2026 17:35 (Moscow time)!
You will be given $$$5$$$ problems to solve in $$$2$$$ hours. Some of these problems are divided into subtasks. The scoring distribution is $$$500-1000-1250-(1250+1250)-3000$$$.
The problems of this round were prepared by tybbs, Mini_PEKKA and me. We would like to thank the following people for making this round possible.
- abc864197532 for his wonderful coordination.
- Alexdat2000 for Russian translation.
- __baozii__, _istil, ETO_leader, Fysty, WiwiHo, amano_hina, baluteshih and max0810 for red testing.
- Friedrich, Halberd_Cease and guagua0407 for orange testing.
- CSQ31, Maskrio, Murinho, Neil_Qian and raresh30 for purple testing.
- daniel071292, lev1106 and the_dragon_emperor for blue testing.
- afoasdfashdoif for black testing.
- MikeMirzayanov and KAN for the brilliant Codeforces and Polygon platform.
- You, for participating.
Good luck & Have fun!
UPD: The editorial has been published. Congratulations to the winners!
Div .1 and Div. 2:
Div. 2 Only:
Auto comment: topic has been updated by Mindeveloped (previous revision, new revision, compare).
I hope to become pupil after this round. Let it be cheater free.
Have you practiced problem solving on other platforms before because from what I see you solved 2200 rated question in your first contest, that's kind of fishy
just look at his submissions during contest, 90% chance he's using AI
Haven't seen a div.2 of 5 problems.
There are sub-tasks as well. And here you go (even if you ignore sub-tasks) :- Codeforces Round 948 (Div. 2). Yes, there may be huge difficulty jumps b/w problems though :(
5 problems in 2 hours, I have bad feeling, but I will participate anyway :) I wish I could do well in this format :pray:
Indeed I perform badly :( 2 hours is really short >,< (My skill issue kicked in)
Same here man, but look at the good side — at least you're gonna be number one on the reversed top contributors list!
😭
YOU GOT THIS BRO!!!
Mindeveloped round ?? the undisputed best shit poster in the business really big fan of you, please reply to me
As an author, I made some of the problems.
Hi brother
I want you to ask kindly about the codeforces problems
I have been doing in codeforces and did 1000+ prblms and you just did ~600 but how are you solving more problems in div2 or div1 like i am curious to know is there anything i didnt know about in the competitive community or something else you have just found because i have came here after seeing your account Mindeveloped .....
Hope you will reply to me as it will helps me alot
thank you
First of all, it's not the quantity it's the quality.
If I solve 10 problems whose rank is 2500+ it's incomparable to even 1000 question of rank 1000.
And another big thing is reading new stuff, you cannot invent nor find everything yourself (at least not in a short time period). using blogs of other people, sites like USACO and reading solutions to problem you couldn't solve is the big thing.
You learn from failing and reading a solution prepared by someone smarter, all in the hopes you can become the smarter one in the end.
thank you ItayKarny i want to know also i am able to solve some 1800 problems but not some 1600 rated. is it knowledge gap or something i am doing wrong ?
Really thank you for your reply to my previous message
Okay that makes sense.
There are different subjects in competitive programming, for instance you might be good in dp but less good in graph, your overall rating is like their average with how often this things occur.
you might be 1800 rated in dp but only 1200 in graphs. plus notice that solving an 1800 problem is today not really means that you are 1800, I think today it's more like if you are rated x you should solve x + 200/300
Mini_PEKKA Pancakes...
As a tester, I think McDonald's new burger in Mainland China is just so-so.
I don't know if it's the same one, but the new one here in America is also really disappointing. It's pretty much a normal burger, nothing really new about it, but it costs $$$12$$$ dollars. $$$12$$$ dollars for a burger. I don't know who they think they are selling to.
I would easily pick Chick-fil-A over McDonald’s in the US. No clue why McDonald’s in China tastes decent and only costs like 4 or 5 dollars, while in the US it tastes way worse and is somehow around 10 dollars if not picking the cheapest meal plan.
In Mainland China, the cheapest McDonald’s burger plus a pineapple pie is sold as a “1+1” combo, and it only costs about 2 USD. The burger is admittedly pretty small, but for people with a smaller appetite, it’s enough. Considering the income gap between ordinary people in China and the US, that price feels like a pretty normal cost for one meal to me—though to be fair, the 1+1 combo isn’t enough to fill me up.
$$$2$$$ dollars for that would actually not be bad here. I would prefer two actual items instead of one of the pies they give out (which are good but small), but I am assuming that the price there is much lower than it would be here since China is poor. All of their prices have just gone up a crazy amount in the past $$$10$$$ years or so, like outpacing inflation by a lot. I remember when they used to have the dollar menu, but now a cheeseburger will run you like $$$3$$$ dollars. And that's just for the cheeseburgers. Bigger items like the chicken sandwiches are approaching $$$6$$$ dollars. Like it shouldn't be normal to go to McDonalds with a group of people and spend $$$50$$$ dollars. It's really a disgrace what has happened.
Because nowadays people in US want to eat only burgers, so they probably put up the price, to remind people that we should not forget about other foods as well, like milk, eggs, fruits and other healthy things there exist. Life don't have to be if only burgers.
Mindeveloped
idk, I don't know who to tag here, but I need to ask a question. As you can see I have not participated in any contests, so I want to ask: based on my profile, should this contest be easy or hard? Also can anyone tell me how to get ratings? Like I'm unrated, and I need a rating, and hope I can solve all the problems fast in this contest.
Why does your username say "cheater"?
To answer your question: Perceived hardness depend on your problem solving ability and knowledge, and familiarity with these types of problems, regardless if you know the basic syntax of atleast one language you should be able to solve the first problem. You gain rating by participating in live contests.
Don't cheat, if you are confused on what is cheating and what is not, here's the rules for AI
why are you larping as dominater
what
He is asking why are you impersonating the user Dominator069. Not sure why he thinks that considering your name in your profile is clearly different. Although, maybe nowadays dom has trademarked the identity of red pandas.
ok, thanks for reply, but what do you think, from my submissions, will I solve all the problems? And about the cheater in my handle: I just think it's funny this way, like SwastikPandey _cheater
Can someone advice me on how to get rid of this newbie i am kinda stuck here in this zone and it's getting frustrating after increasing the efforts in recent weeks.Sometime i am able to solve div 2 A and B and sometime not by making those complex myself.
I think the contest will be difficult,because it only has 5 problems in 2 hours.
Thanks to the authors and testers for the contest! ＞_＜
looking forward for it
Score distribution?
As a tester, I am a fan of
cdqz.I hope I cross 1700 : )
Hope to become expert
Hope to become specialist, gl
Auto comment: topic has been updated by Mindeveloped (previous revision, new revision, compare).
Giving a contest after 3 weeks,hope for the best
As an author, I wish all participants good luck.
Btw today is Pi Day
Happy Pi Day!
Hope I can become Master in this round
Failed :(
It's gonna be a Speedforces contest isn't it :)
i hope to be specialist in this round
Looking forward to being goombah stompped yet again ;-;
Happy Pi Day!
As a tester, wish all participants have fun and good luck!
As a participant, I hope I can solve at least one problem in this contest. Wish me luck, guys!
edit: i'm cooked
Can someone hold other races start at different times?Different time zones have big differences,so I need to take part in this race at midnight.
I hope I will become speacialist this time ❤
Hope to reach 1500 in this round
As a Clash Royale player, I am sure that Bob played hog cycle 2.6 in the 4th test
imo this was a bit shy of a div2. D2 and E were good obv but yea
D2 и E, когда ты на них потратил по 45 минут
How to find for the "real" edges from the tree from the reachability DAG faster than the $$$O(n ^ 3)$$$ Floyd Warshall approach?
I came up with some dp-like ideas of longest paths in a DAG but nothing which works for chains containing nodes with indegree > 1 and outdegree > 1.
I tried to use bitset and it should work in $$$O(\frac{n^3}{\omega})$$$, but I made a mistake and wrote 500 and I got RE, so idk if it would be fast enough
Sort vertices by the number of achievable vertices starting from it in increasing order, let this sorted array be V. Maintain a DSU if added edges were bidirectional. Iterate over vertex v in V from left to right, iterate over vertex u in V from right to left. If u is achievable from v and v and u are in different components in DSU add an edge v->u.
Here's what I did:
Build a DAG which contains edges $$$i \rightarrow j$$$ for all $$$r_{i, j} = 1$$$. Let $$$t$$$ be the topologically sorted list of nodes w.r.t. this DAG.
Then, we do the following:
Now, one might naively expect this to run in cubic time because of the inner loop, but we can show that it only takes quadratic time. Why? Because if there exists a valid tree, then the sum of sizes of
outgoing_nodesacross all $$$u$$$ must equal $$$n - 1$$$.When no valid tree exists, we can simply break out of the outer loop if the size of the edge set ever exceeds $$$n - 1$$$, and we preserve quadratic time complexity.
Really good round. Good, balanced, nice problems. Thanks for the round Mindeveloped abc864197532 and all testers.
I think D2 need a bit of constant optimization. But all in all, it is a great contest.
And it is IO bound if you try to read it char by char
Fun C for me :)
Did you use DP for C or greedy??
My python code
Probably DP
I did this in C++ with doubles and it failed
it passes. see my code
ahhh, maybe it's about setting the precision in the cout, damn
For D2,I got TLE on 18 and mad,but I found master wabca got TLE on 25 before accepted :(
worst c ever
LOL, I just literally OBEY the instruction to do it from left to right, and stuck on it forever. Such backwards thinking rarely appears in my past practice, just can't realize I can do such things :(
nah i got precisionmogged
huh, I see that. It's really a pity
Haha I thought C was easier than A and B
For C this the approach which I thought of : We obv have to take the last element, and if we skip one then we only affect the scores resulting from the choices after that
Initially I take the total points by taking all the choices. Then I iterate from the second last element and check if by not taking the current element the total score afterwards increases or not, considering the score from the earlier choices is not affected at this point.
I am storing the cumulative stamina and pref sum scores initially while taking all choices
I consider the updated score by multiplying the points ahead with the (cur cumulative stamina) / (prev idx cumulative) stamina , as it will be a common factor for all the taken choices ahead. This value should be equal to 1 / (1 — p[i] / 100)
Don't understand where I'm going wrong : https://codeforces.me/contest/2208/submission/366691023
oh it might be a division by 0 issue
I didn't like the contest, expected better from Mindeveloped
The problem D2 is interesting, but the time limit is so tight that even correct O(n²) solutions get TLE due to constant factors. It would be better if the constraints allowed reasonably implemented solutions to pass.
Sorry about the inconvenience caused, but actually the stardard solution is pretty fast and it was difficult to not let O(n^3/w) pass.
anyone else got WA in C due to
std::fixedor is it just me ;_;?me too :( T_T
I tried doing the math in long long's by having the value be the answer * 10^7, but I was still getting WA. How are you supposed to handle the floating point error in C++?
doing all calculations with
doubleworksIt was what I tried the first time, but when I got WA on test case 2 I assumed it was related to the precision...
what was the $$$O(n^3)$$$ solution for problem $$$D1$$$?
I used topological sort and DSU, each time I will add a node for another only if it is reachable and I didn't add a node between them before
I created graph from input matrix, and iterataded in the topological order, then for each node I just naively tried to delete each incoming edge to it
Enumerate $$$a,b,mid$$$, and if $$$a \rightarrow b$$$ is available but $$$b \rightarrow a$$$ isn't, and there doesn't exist any $$$mid$$$ which $$$a \rightarrow mid \rightarrow b$$$ is available, then there is a edge from $$$a$$$ to $$$b$$$. Finally, check whether the graph is a tree.
Commendable approach thanks I submitted D1 modifying it based on your submission thanks for sharing <3
ez ak
where the editorial??
hey guys I submitted my solution for A and it initially showed pretests passed, but later when I checked my submissions the verdict had changed to Skipped. Because of that I had to resubmit the same code after like 20 mins from the first submission..... does anybody know what i should do about it?
Submission ID:https://codeforces.me/contest/2208/submission/366640037
Today my solution for A was stuck in queue for 45 mins. This is happening to me 2nd time in a live contest. Many people who submitted multiple solutions after me got judged, but mine was left out. I request the admins to look into this issue. Also I request people who faced a similar issue to comment below too.
Me too :(
Did anyone solve B without brute force?
I solved it with priority_queue and queue
I did it in o(n log n), just calculated cost for a single round trip, and answer will be (m/cost).
I did, first remove the minimum costs until the win-condition becomes from the first $$$k$$$ cards, then add the win-condition card, and remove these costs from $$$m$$$ (if $$$m$$$ becomes less than 0, then the answer is 0)
then, the game will repeat the same as long as the summation of costs doesn't exceed $$$m$$$, take the minimum costs until win-condition card (now in the back) becomes from the first $$$k$$$ cards, add the cost of the win-condition card to this, the answer will be $$$1 + \lfloor \dfrac{m}{sum} \rfloor$$$ (sum here is the sum of that will be repeated each time)
I solved it by taking $$$(p-k)$$$ and $$$(n-k)$$$ minimum elements which requires just two sorts.
Problem A is way too problematic! I stuck on the wrong threshold of (n-1)^2+1 for 45 minutes!
yeah in n1 , it somehow i got confused
Please Please do a small check on D1, so many cheaters who are reading the problem and coding 200 lines of code with comments in 7 minutes tybbs Mini_PEKKA Mindeveloped
Pi Day spent well
D2 is hard
Serious question: Will this contest be unrated? Today's problem B has already appeared before according to this blog: https://codeforces.me/blog/entry/152061.
unlikely, it wasn't intentional and there's precedent for the rounds not being unrated when something like this happens.
Where is editorial?
This was the most tense contest i had ever taken part in. I submitted D1 with 50s remaining and it passed system testing only after the contest ended.
I think problem D2 is missing some test cases.
My submission (366696596) passed, but it takes $$$\mathcal{O}(n^3)$$$ time on inputs that consist of a small number of layers (at least 3) with a large number of vertices in each layer, such that all vertices on a lower layer are reachable from each higher layer.
An example input can be generated with the following Python script:
It's easy to fix (366730442) but it feels like it should have been caught by the system tests.
Is question C a standard problem?
My seemingly $$$O(n$$$$$$3$$$$$$)$$$ Solution works for D2. Idk why. Can it be hacked?
I don't think the code is $$$O(n^3)$$$.
I'm assuming that you are thinking the code has a cubic complexity in these line of codes:
In the code, we have $$$cc = 1$$$ and $$$cc = cc + indeg[j]$$$ for each loop $$$i$$$. Due to that, after each $$$i$$$ runs successfully, we have $$$indeg[i] = 1 + indeg[j]$$$ for every $$$j$$$ that was chosen by the order. We also have the number of elements in $$$ing[j]$$$ equal to $$$indeg[j]$$$. Since $$$indeg[i] \le n - 1$$$, that makes the complexity of each loop $$$i$$$ linear. To sum up, the complexity is just $$$O(n^2)$$$.
That makes sense. Thanks!!
I almost didnt submit this code thinking there is no way it’ll pass. Thank god I did xD
Well, congrats, it paid off :)
I didn't solve D1((((((((((((((((((
nice round
Mindeveloped Editorial link is not present in the post.
My friend qwq_Lsy found his solution for D1 and D2 Wa on protest 2. I have communicated with him for a long time and have no idea on why he was wrong. Can somebody help me? Thanks.
Take a look at Ticket 17527 from CF Stress for a counter example.
Thanks!
For the first time in my life I see that div.2 has 5 problems
I think I need more practice....
I received the plagiarism warning. I unintentionally shared my code with a friend during the contest. Now, I realize, I violate the contest rules. This mistake i made during my contest, and it won’t happen again.
I apologies for this and will make sure to follow the contest rules strictly in the future.
I unintentionally used a code of my friend and it was too late for me to undo it. Which I understand is a big mistake of mine. And I am gonna make sure that I don’t do something like that in the future.
Dear Codeforces team, for the contest 1086(div 2) I got flagged for matching solutions to D and E with a single person I'd like to clarify that the other account is me with a different gmail.. I am sorry for this major overlook on my side
[deleted]
deleted
why my solution to D2 with O(n^2) got TLE on test 23? https://codeforces.me/contest/2208/submission/371466729
Oh, I realized that the solution is O(n^2\alpha(n))