Hola Codeforces!
We are really excited to invite you to participate in Codeforces Round #1093 (Div. 1) and Codeforces Round #1093 (Div. 2), which will be held on Apr/13/2026 17:35 (Moscow time).
For division 1, you will be given 2 hours to solve 5 problems, for division 2, you will be given 2 hours to solve 6 problems. Note that at least one of the problems will be divided into subtasks. Furthermore, at least one problem may be interactive, so please read the guide for interactive problems if you are not familiar with them.
The scoring distribution will be announced later.
The problems were authored and prepared by misteg168, danx, rlidon2006, and Misuki.
We would really like to thank the following people for making this round possible:
244mhq for his orz coordination and support throughout the round, and also for the Russian translation.
A_G, dinohaur, zltzlt, omeganot, IceKnight1093, fishy15, ub33, awang11, Justinshao, Pablo-No, FelixMP, madlogic, pandaa73, chromate00, IceSerpent, Lucia_Aparicio, aniervs, and Kalufas for testing the round and providing priceless feedback.
MikeMirzayanov and KAN for the great platforms Codeforces and Polygon.
And finally, You, for participating!
We wish you all an exciting experience. Good luck and have fun!
UPD1 Scoring distribution:
div2 500-1000-1500-(1000+1000)+2500+3000
div1 500-(750+500)-1750-2250-3000
UPD2 Spain's Olympiad in Informatics:
This round was based on the Spanish Olympiad in Informatics, which took place last weekend. Thanks to all contributors!
UPD3 Editorial is out
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
Hope this round will not unrated
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
Auto comment: topic has been updated by Misuki (previous revision, new revision, compare).
As a cute Pig,Hope everyone can enjoy the contest.
As a muslim participant u are haram
Hello dear muslim guy! This is haram: "give up on your dreams and die"
it's reference to AOT bro
I don't know.
hope ts dont get unrated lol
As a tester, I'm still dyslexic
As a yiren, wish to become specialist in this round.
As a future paticipant, I'm a big fan of Misuki
Hoping this round should not be unrated.
Hope it will not be unrated again......
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
Please don't get unrated this time........
please dont be unrated please dont be unrated please dont be unrated
Why there are 8 "auto comments" ?
It's me updating testers list and noticing that the round will be at 16:35 only in CET but there is a whole world apart from central Europe.
looking forward to the contest
Hope the problems dont get leaked this time
Hope this will go well. Excited to attend.
I wish this a best alternative for THUPC.
Just show what a fantastic rated div1/div2 contest should be like
show not leaking contest problems is a very easy thing
Will it be unrated?
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
From the scoring distribution perspective, why does it feel easier to get into div1 than div2?
I think the interactive problem will be divided into subtasks.
Div2C & Div1A can also be the interactive problem.
Maybe, I don't think so.
Ahhh!! How could I overlook the aspect of no. of queries to know the stuff :(( You were right.
Finally a rated contest ! ^_^
My first official participation in a D1 contest. Boooooi Im scared
best of luck
tks
I don't know why, but I think this round will be more fun..
Why this contest has such a slow judge? :/ I had to waited for like 10+ minutes just to see the verdict of my submission :<
queueforces.
Oh Well...
Queueforces again.
inf queue time
Seeing 66 Queries for easy version — Thank you for your generosity, kind sir
Seeing 33 Queries for Hard version — Dammn you that is basically the same thing!!!
I don't want to classify anything to a bucket or standardise, but whenever you see such things in interactive problems, 99% times it is the Binary Search & DAC (Divide & Conquer) coming to the play.
I loved problem D in div 2 and then i saw standings of div 1,so MANYYYYY cheaters
Because the problem itself has so many layers with each being a tough nut to crack. The mathematical interpretation of query response was the soul of the problem. Then even if you have figured out, you need to go phase-wise and write a clean solution to isolate the indices. I am still flabbergasted by the fact that 1100+ contestants in total have figured this out.
Just try to deduce the relation between the parity of response and actual size of query set when different no. of elements which are part of triplet are present. You would see a beautiful relation then.
what might be the rating of div2 D ?
Around 1750.
div1 is cooked, so many cheaters in top 100
I guess authors give Div1 problems to Div2 users
It's really a big problem not being able to see why div.2 D is WA on test 1. But it doesn't matter, I don't need it.
so we had, guessforces, unratedforces, queue forces, this week has been crazy.
what sol'n to div2d1 takes up 66 queries?For most soln to div2d1 itself was 33 queries
Yeah. It was a jebait. You can make a solution that looks at pairs of answers to complementary sets, but it actually incorporates the whole idea from the full solution (look at parity of size-answer) so it's kinda pointless. It allows people to do random shit more if they don't know the 3log solution, but the full problem would be easier without the subtask.
Yeah, the first subtask had completely distracted me from the $$$3 log(n)$$$ solution ;(
If you query a subarray and its complement (all indices except the ones in our subarray), we can check the difference to their answers to infer that if the special number occurring thrice is somehow split up between these two. Therefore you require 2logn to find one of the special numbers. I still don't get the solution to D2, I guess I have to try a bit more...
Div2C is certified "guessforces" classic
I don't know when did solving a Diophantine Equation become part of guessing? You can't blame a problem to be ad-hoc or guesswork if you don't know the formal proof of it.
yeah i did bring it to (2n + 1)(2m + 1) = 2a + 4b + 1 and then find pair of (n, m) but afterwards to check if (n, m) satisfied, i just think about the very weak condition and surprisingly pass all the test (yes i don't know how to proof it then)
It's not a weak condition. It is very evident that one of the segments is L-shaped as well and it won't give us 2q unit segments directly since, they can only be rotated and not broken into pieces.
They share one horizontal and one vertical segment. So, it becomes pretty obvious that max. no. of such segments should be <= both H and V. We can compensate the buffer using p segments, and if it doesn't satisfy, we would never be able to fit all the pieces into our N * M grid. I hope this helps you.
can you give some hint
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
When I first read Div2B, I only need 3 minutes to implement it, then spent more than an hour debugging it. Still pass pretests tho. "I'm sure it'll pass system tests".
Wasted 45 min on $$$B$$$, finally guessed something and it passed. Tried some math factorization on $$$C$$$, WA on test 1. Lot of cheaters on $$$C$$$?
Pure torture for 2 hours.
I wasted an hour on B because of an one character bug.
Why mostly cheater are Indian? I don't want to be racist but it's fact. Specially I saw.Irisqwq, div1, obviously like a cheater.
its cause there exists a culture of academic dishonesty among students. When a parent forces their child to do something they don't actually want they try to find any way out. Then the dishonesty spreads like a virus. If you know someone else cheated and got ahead of you, you become envious and do it too.
Did anyone try solving Div. 2 D1 with
binary searches
?
I did
3 binary searches: one to find the rightmost position of the target element, one to find the leftmost position and the last one to find the remaining position
. Unfortunately, my solution gives TLE on the second test. I would be grateful for any advice on the matter.
Printing
numbers from 1 to 2001 66 times
shouldn't take that long, right?
UPD. The bug has been found. Thanks no_oneplb. There was an issue with my
binary search implementation
.
Can I have a look at your code please?
i did the same thing ,this is the intended solution,it will take atmost 33 queries,must be a implementation issue.
have you flushed it? (Please assume that this comment has been deleted.)
I did. It wasn't mentioned that my code passes the first test case and gets TLE on the second one. My apologies, I have edited the comment to clarify.
//-\\ wish get +15 min to duration
I got MLE on Div.1 D, although my solution costs $$$O(n \log n)$$$ in both time and memory.
After some time i ended up directly with the 33 queries solution with 3 binary searches. What was the intended 66 queries solution?
You don't query for the complement, right?
No, why would I? My approach was looking for parity switch. If you write down K as the size of a prefix to be queried and x as the response, you see that they have the same parity up until the 3rd repetition from the answer (z). You can bs this.
Eg
a = 1 2 3 1 2 3 1 4 4 5 5
k = 1 2 3 4 5 6 7 8 9 10 11
x = 1 2 3 2 1 0 0 1 0 1 0
Remember x(i) = query(1..i)
Damn I messed up something then I think ==))
There is a solution with 44 queries where to find the last one you check (l,mid) < (l+1,mid).
I just figured out C, 1 min after the contest ended, feels sooo bad.
Same :(
D2 is very cute. After you figure out how to find the rightmost index with triple frequency in O(log), you can "shift" it to position 0 and find the middle one and leftmost one with the same binary search.
i understood that i can find the edges, could not understand how to get the middle one
query doesn't need to be a contiguous range, keep that in mind
Imagine you teleported the right one to position 0 of array. That's equivalent to having this index in every prefix query you make, so you can find the middle position like that. My implementation does exactly that: https://codeforces.me/contest/2220/submission/371035405
bro the code for Div1D is too long for 2h CF.
I coded for more than 50mins and passed the sample 5mins after the contest
How you submit immediately after contest? Now I can't go to "Submit Code" tab, because: "Contest is over".
yeah ur right, so I just tested the sample in the statement.
Submit Code could be enabled after systesting.
thank you to reply!)
The user above passed the sample testcases not all testcases. He might have tested the code locally on an IDE.
Ooh, really, my translator failed on phrase: "passed the sample"
Hardest B I saw till now.
For me, it's kinda easy. You just need to check if there are any subarrays with length more than $$$m$$$ so that every index of the subarrays is the same. If there is one, print No, or else, print Yes.
Can you explain why it works?
Actually you need to check if there are any subarrays with length greater than or equal to m. If yes, you cannot move past that segment at all. consider m = 2 and we have subarray 1 1 1. so you wait in x=1. subarray turns 0 0 0. now you go to pos 1, subarray again becomes 1 1 1. The next time you try to move, it will again become all zeroes hence not possible to cross this segment. Even if the segment was 1 1, you would not have been able to cross the segment.
I agree, but I found this div a bit complicated.
Any Tips for Problems like B.
Where they given clocks and you can reset the times
every second you have choices.
I could not solve earlier problems as well for example — https://codeforces.me/problemset/problem/2062/B.
Any help is appreciated how to approach these kind of problems.
You can think of it as, its always better to enter position i when its value is 1 as it give you maximum time to stay on that position without moving.
thank you next time i will consider thinking about this.
I think you want to think in terms of "invariants" or insights that you can discover.
These 2 are really helpful:
^ given the knowledge from (1) now we know we only need to worry about positions with the same starting times. Then you can play around and discover:
Thus just check if there are any sequences of same start >= m length
gotcha thank you. i initially thought about if two elements are different, but it was taking time hence i moved to c.
Div.1 A is too hard.
Feel like an Ad-hoc forces.
I feel AB are more on the adhoc side, CD were more standardish? And E I feel it is insane that some people solved what took us a lot of time in 2h.
Sorry for my feedback being all negative:
Overall: Please use $$$1$$$ instead of 1 when it makes sense.
Div1A: The statement is really informal. It does not mention what is grid or anything about overlapping.
Div1B: Please do not silently change the constraints. / I got trouble at WA1 with no information (my bad...)
Div1D: The statement is really informal: the variables actually change in an input and they depend on each other complicatedly. / The problem itself is boring, observation <<< implementation.
I cannot anticipate more from an author who don't know how to use markdown.
Hope this round will not rated
From hoping that this round will not be unrated, we came to this within 36 hours :((
I mean, D1 is unnecessary. I also feel like the same idea is repeated in a lot of interactives.
I mean you can find a handful of interactive problems not using Binary Search in any form. I remember a couple of number theory based or brute force interactive problems other than problems involving Binary Search.
It is sad that I opened the complete problemset too early, and saw that n=2000 in B(in hacks) , and try hard to optimize my solution from 36 queries to 33, and there weren't clarifications. After a while I noticed that n=1000 in statement, and after I refresh the statement they all become n=1000. It wastes me about ~20min time.
Sorry for it. I didn't do clarification, because it was changed in the beginning of the contest and was only in hacks section (input had n <= 1000 constraint from the beginning). Next time I will do clarification for all changes in the statement, that might affect participants.
Why greedy fails in div1-C/div2-E? 371027291
Not entirely sure, but I feel like its because you can force a node to become red and it would, improve the expected operations for a lot of other nodes. Tried the greedy with a pq and failed (WA 5) For those that solved it, was it some kind of rerooting tree dp?
I solved it by just repeatedly picking the one with the lowest value of $$$\frac{degree[node]}{(ct[node]*(ct[node] + 1))}$$$ where $$$ct[node]$$$ is the count of red neighbors but I think most people used dp
why is it correct?
how on earth does that work?
Given 2 black nodes connected by an edge you should first pick the one with the lowest value of the mentioned formula. After that I guessed the solution but got screwed on custom comparator logic.
ok but how does one come up with a formula like that?
If you are constantly attacking a node the Expected turn to turn red is total_neighbors/red_neighbors = tn/rn. If one of the neighbors of node u is colored black then expected value changes from tn/rn to tn/(rn+1). Whose difference is 1/(rn*(rn+1)).
It is more optimized to choose
1first(60%) than2(66.67%).Can any one give me a hint or something about Div2 B ? I couldn' solve in during contest
Think what happen if you have a segment with same values.
You can always go to v[i+1] if v[i+1]>v[i] or v[i+1]<v[i] (think why?)
The remaining case is when v[i+1]==v[i]. That's it
Div1 C was such a greedy bait.
Can you give me a hint or something about Div2 B ? I couldn' solve in during contest. How should I approach this? I solved a good number of problems but still not able solve B generally. What should I do???
I will take this as a compliment.
.
Why is task B split in 2 subtasks? The only solution which I found that uses 66 queries and can't be quickly optimised to 33 queries is much more complex than the full solution of B2.
To bait people to start implementing the first solution. I got baited.
I did first 2 in 25 minutes then cannot solve any. can anyone give me hint for problem C (div2). I was thinking of converting the unit lengths to L shaped as well and then making a valid n*n just from the L shaped total available lengths (2-> 1*1,6-> 2*2,12-> 3*3 and so on) the I just need to arrange the leftovers in a valid manner.
the total number of segments in an $$$n \times m$$$ grid is $$$n(m + 1) + (n + 1)m = p + 2q$$$.
$$$2nm + n + m = p + 2q$$$
$$$4nm + 2n + 2m + 1 = 2p + 4q + 1$$$
$$$(n + 1)(m + 1) = 2p + 4q + 1$$$
So there are a few possible pairs $$$(n, m)$$$ to try. To verify if a pair passes, simply count the number of horizontal and vertical segments, L shape uses one of both, so $$$\min(hor, ver) \ge q$$$ is neccessary. You can also guess that it's sufficient (during the contest I couldn't find the proof fast, but the pictures in samples made me believe this fact).
Maybe one of my dumbest moments yet, but I realize now I could've literally just submitted my D1 solution for D2. I thought n <= 1e4 instead of 1e3, so I thought my 3logn sol would've used too many queries.
Do you confirm that the problemset has not leaked since the onsite contest?
There was a live stream on YouTube, where they commented the problems of the Spanish Olympiad in informatics, during the actual time of SOI.
User @ChatGPT4.0 is illegal, I can't understand why he is still not banned.
Now that Div 1 has been invaded, will be interesting to see how codeforces attempts to combat cheaters. Just need one smart person to build an algorithm, then do a sweep through the past two years, and recalculate all results imo. The algorithm at a minimum should be able to exist in the future to catch people today. :)
Auto comment: topic has been updated by misteg168 (previous revision, new revision, compare).
☠️☠️☠️
It's easy to solve after contest, because everybody can cheat or copy paste other's solutions.
There’s no need to risk being criticized by showing off how you cheated on a problem that few people have solved, because it’s very easy to verify. But it seems some people prefer making irresponsible and cynical remarks rather than offering well-founded skepticism. I hope you can apply that same evasive wisdom to every competition you take part in from now on.
Believe it or not I solved it legitimately,
(that's April 13rd, 16:58 UTC)
I posted this just to show how silly I am instead of showing off.
what's silly in this?
Did not manage to solve B, C, D1, and D2 in 40 minutes and spent the rest time on F. Discovered I forgot to remove my debug code that modified answers after contest.
It's easier to accuse others of cheating than to verify it yourself.
Worst Contest ever for ksun48, tourist, ecnerwala, Petr :(
How can I report a user for cheating?
I've found that for Div1B (i.e. Div2D), if your program exited abnormally before answer all testcases, you will get a verdict WA instead of RE(See 371038871 and 371039177), which makes it nearly impossible to get a RE verdict, is this a correct feature of an interactor?
As it happens, most interactive problems on codeforces work like that (well, at least in my experience). I remember there was a div 1 where I wasted 5 submissions because none of my asserts seemed to raise RTE, until I made the hypothesis that RTEs are not guaranteed and got AC.
So its safer to assume that RTEs just won't get logged...
Dude the rank 1 for this contest directly jumped from expert to Master, completely skipped CM. How XO
Hello Codeforces, I have attempted to write a formal-ish proof for Div 2B, I am not 100% sure if it makes sense, but I hope someone can take a look and see if they understand it, thanks!
Submission with proof in comments
so tuff
why ~~~~~ p+2q=m(n+1)+n(m+1) ~~~~~ in 2219/A?
You are given $$$p$$$ unit length segments and $$$q$$$ two length segments (L shaped). Each of the $$$q$$$ L shaped segment contribute $$$2$$$ segments to the grid and each of the $$$p$$$ unit length segments contribute only $$$1$$$ to the grid. Hence we get $$$p+2\cdot q$$$.
Now consider $$$m=2,n=2$$$. How many string are there? $$$3\cdot 2\cdot 2=12$$$. Hence it is easy to see total segments in a grid is $$$m(n+1)+n(m+1)$$$ and this cna be solved using SFFT to factorize and we have solved the diophantine equation
Hadrik120710, Thank you
Welcome!
great
yay expert!
congrats!
editorial?
sus ahh div 2 B 370985385
Can you help me solve problem C? I feel like my approach is wrong, but I don’t understand why.
My idea is that we can always think of the grid as a 1 * n grid. Based on that, I came up with the following process:
If (one % 2 == 1 && l % 2 == 1), then both are odd. So I reduce 3 from l and 1 from one, which makes both values even. After doing this, we effectively form a 1 * 2 grid. From there, I assume the remaining part can always be handled, since the leftover l contributes l / 2.
Then, I think that if one % 4 == 0, it will contribute one / 4; otherwise, it is not possible. This is because, as far as I can visualize, this seems like the only way to construct it. There might be other ways, but ultimately I feel everything reduces to this logic.
Also, if l % 2 == 1, we can reduce l by 1 and one by 2, and then everything aligns similarly. We can repeat the same process again. Basically, each time l is odd, we apply similar steps.
I don’t have a formal proof for this—I just tested a few cases and arrived at this idea. If anyone can point out where this approach is wrong or provide a correct way to think about it, it would really help.
Since when have Hector and Gustavo been friends?
Maybe this is before the Max Arciniega incident.
I mean Gus did all he could to keep Hector alive after Nacho swapped his pills, right?
hahaha! funny
Hope this round will not unrated.
misteg168 MikeMirzayanov , Dear Codeforces i am writing regarding my submissions in Codeforces Round 1093 (Div. 2), specifically for Problem A. Due to some confusion with different compiler settings at the time of submission, I ended up submitting the same solution twice for the problem A-Blocked. Both submissions contain same code, but unfortunately, one of them was marked as Skipped.
I sincerely request you to kindly review the situation and, if possible, remove the skipped submission from my record. This was an unintentional mistake, and I would be very grateful for your consideration.
Submissions:
370969636 -> compiler:C++23 (GCC 14-64, msys2)
370966387 -> compiler:C++17 (GCC 7-32)
Hi MikeMirzayanov misteg168,
My account lcb9021 was suspended due to similarity on submission 370979771 (2220D2). I already emailed an appeal on Apr 17 but cannot log in to check site messages.
Could you please preserve and verify PM logs between my account and the matched account [OTHER_HANDLE], and advise on the status of my appeal? I can provide local timestamps and other evidence upon request.
Thank you for your help. — lcb9021, contact: [email protected]