Hello, Codeforces!
We, the RiOI team, are proud to invite you to participate in Codeforces Round 1046 (Div. 1) and Codeforces Round 1046 (Div. 2) which will be held on Aug/28/2025 17:35 (Moscow time).
The round will be rated for everyone. You will be given 6 problems in both divisions, where some problems will be divided into subtasks, and 3 hours to solve them. For both divisions, the number of interactive problems will not be equal to 1, so you may need to read the guide for interactive problems before the contest.
The problems are authored and prepared by Register, STUDENT0, Error_Yuan, _istil, and Alan_dong.
We would like to thank:
- Error_Yuan for his great coordination.
- Alexdat2000 for Russian translation.
- Um_nik, errorgorn, SSerxhs, dorijanlendvaj and conqueror_of_tourist for red-black testing.
- _l_l_, E_fireworks, rui_er, Markadiusz, __baozii__, lethan3, SomethingNew, YuukiS, tfg, Sana, maomao90, A_G and FairyWinx for red testing.
- NobodyThere, wangmarui, ikrpprppp, Kolychestiy, cry, hocln, Makcum888 and beaaaan for orange testing.
- madlogic, Wf_yjqd, pacha2880, Edeeva, windreaper and denk for purple testing.
- chromate00, SunsetVoice_ and Non-origination for blue testing.
- Mohamed_Saad62 for cyan testing.
- houran for green testing.
- MikeMirzayanov and KAN for the great platforms.
- You for participating!
Special thanks to __baozii__ for his help during the preparation!
The scoring distribution is below.
- Div. 2: 500 — 1000 — 1500 — 2000 — 2750 — (2250 + 1750).
- Div. 1: 500 — 1000 — 1750 — (1250 + 1250) — (3000 + 2000) — 4000.
Good luck & Have fun! (∠・ω < )⌒☆
UPD 1: Editorial was published.
UPD 2: Congratulations to the winners!
Div. 1:
Div. 2:
As a tester, I tested almost all recent rounds.
As an author, you are following me.
ok
Too bad testers can't Register to participate
As a student,I participated in almost all recent rounds……
what __baozii__ thinks:
RiOI Past Rounds
Why I failed to register the round by clicking the Register button?
Why you click me qaq
As
As a tester, I think the whole problemset is awesome! orz to author for making so much interesting problems!
except the problems that need you to know the mind of the creator of the problem
As a participant, I need to Register the round.
The Register button is not working, it directs to a profile.
As a tester, I'm a big fan of RiOI team!
As a participant, I wanna say, ru1_er (not rui_er at all!) is a very lovely girl!!!
Div. 2 scores look balanced
Number of interactive Not equal to 1
Either way I think interactive is the solution for ai cheating
HUGE Thanks to the authors and testers for preparing the problems
A great week Spent with more Contests and Practice
As a tester,there is a fun problem in div2 and just Register to see it:)
As a tester, you cannot view these wonderful problems without Register the contest.
As a tester, I hope everyone enjoys the round and gets +rating, unless you’re higher rated than me
How dare you call yourself a "tester" and CURSE others like that?
he's courting death
I hope to become a candidate master soon.
I hope you become candidate master in this contest
good luck! I wanna finally rich cyan
I did not click Register at the end of post to register for contest
Error_Yuan single handedly solving the sparse div 1 problem, orz.
As a NON-tester, i want to say, i'm dead(2 interactive in 6 tasks)
can be 0 also or 3 also
Phew... I thinked i will get 2 interactive problems
or 6
Some people just want to see the world burn
im planning to make my contribution negative for fun
i hope to get a negative delta so can participate in the next div3
because i love Div3
Well, if you don't care about the rating, you can always participate in div3
I hope you get -7
The only goal i achieved in my life:
As a tester, I just wanna say: Ciallo～ (∠・ω< )⌒★
Ciallo～ (∠・ω< )⌒★
Appreciate the effort, can’t wait for the contest!
Hoping to Solve A and B, in last contest I was only able to solve A and I solved C after contest coz got stuck at B
Hoping to get to Candidate master this time... Tho the chances are low hahah
I just don't want this round to be yet another
Congratulations maga!
Congrats on cheating your way to CM. I hope you will be banned at some point.
hellod hfhjdfghfjgfudjhdgsufyj
As a Newbie, I need to think twice before registering in div2.
Believe in yourself; you can do it.
felt good after hearing this... thank u
please register and do your best in the contest ...
and then don't look at scoreboard LOL. but I hope it goes well for you.
u r right, and thank u
lezzzGOOO!! all the best to u and to me and to everyone
I have a question
when I try to submit solution to first problem I am greeted with
verify you are a human screenwhere I have to click that buttonis there something I can do before the contest so that I don't get that screen during submission
Wait,it only says number of interactive problems will not be equal to 1,could it be 0?
I don’t think so, since if there were an interactive problem, they would have told us to read the guide for interactive problems before the contest.
I hope everyone can enjoy the fun of this match :)
"For both divisions, the number of interactive problems will not be equal to 1". I am not getting this point... (how many it will be: 0,2,3...?)
anyway it will not be 1.
Daddy!!
Ciallo (∠・ω <)⌒☆
All the best guys
As a participant, I need to stay at least at pupil so i Register at this contest
As a participant, I guess the d2D/d1B and d2E/d1C are interactive.
If not, it means I leave the luck in the contest tonight.
Best of luck to everyone!
As a yuzusoft-gamer, I say senbai Ciallo(∠・ω < )⌒☆
As a tester, I'm sure it's an excellent round.
Amazing problems, thanks for the round Register STUDENT0 Error_Yuan _istil Alan_dong and all testers.
very hard problems (.-.)
speedforces
Bricked A so hard, found it harder than B and C
I found both A and B more puzzling than C as I was able to see the DP for C quite quickly somehow
How to solve C ?
so imagine you are looking at number X currently
so if there is subsequence of size
XcontainingXending here right ?? so you just store indices of each value and look in the dp table at that positionlike if
arr[i] = xthendp[i] = x + dp[before where block of size X can begin]elsedp[i] = 0now if I have indices of X in a
list... previous index to look at is at positionlist.size - Xalso your username LOL!!!
spent all my time on D2 after ABD1, but should have solved C instead.. how to solve 1C?
The idea is: If you have a cycle with even length, all vertices have to have the same value, if you have a cycle with odd length, all vertices have to have value 0. Now you can just calculate all 2-edge connected components (calculate all bridges) and check if each component is bipartite or not.
Why a cycle that is even but not divided by 4 (size 6 for example) cannot be coloured in 2 values (so that adjacent vertexes are different values)?
Oh damn I understood, I'm stupid :( could solve it if it weren't for this mistake
Look at any cycle. For any two vertices $$$U$$$ and $$$V$$$ on it, by checking paths from $$$U$$$ to $$$V$$$, you get that XOR of all vertices on the cycle except for $$$U$$$ and $$$V$$$ is $$$0$$$, which implies that the XOR of $$$U$$$ and $$$V$$$ is the XOR of the whole cycle, which further implies that all vertices on the same cycle have to have the same value. Additionaly, if the cycle is odd, that value has to be $$$0$$$ (there is a path containing all cycle vertices). It can be verified that these conditions are sufficient.
Now, note that the fact that cycles have all values equal implies that every connected bridgeless subgraph has all values equal. Therefore, you can just find all bridges in the graph, see how it decomposes, and make sure that every component like this has all values equal, and if it contains an odd cycle, that value is $$$0$$$. Now, either you have no condition on the value itself ($$$V$$$ options), exactly one condition (one distinct weight or an odd cycle), so one option, or two contradictory conditions and it's impossible.
Is there anybody who can help debugging my code :(
https://mirror.codeforces.com/contest/2136/submission/336043898
I can explain my approach if you want
When $$$W = 99999$$$ your second query may not function as your wish. $$$49999, 1, 49999$$$ will be displayed in one line.
Probably the most interactive round I've ever seen. Just wow. That was cool.
So hard. I spent 1h solving E but falied. Can anyone tell me the solution
Look into Bi-connected components, once u observe that bipartite bccs have to have the same value, and non-bipartite bccs should have 0, you have to condense the graph into a tree like structure and then multiply (You also have to merge the bccs which have the same node, as all of the bccs will have to obey the 0 or same value property). Probably the longest solution i've written.
I have a simpler solution. Find a dfs tree, then an edge not on the tree makes the values of corresponding tree vertices to be same. You can use DSU to maintain which vertices should be same.
bombed c two wrong submissions :(
gimme give a hint for E plz
Bridge, though I was not able to solve it during contest.
º~º 336036032
saw div2C is a simple DP.. made a wrong submission ... darn it !!!!
and how come >650 people solved div2E.. today we don't even have div1 count included in it, was it some approachable problem ?
div2c is not a simple dp as n = 10^5, it is classic fenwick tree . like it was asked before if I am not wrong in cf
oh I am sorry,
I meant I was able to figure out the dp so quickly and while trying to be fast I made a silly mistake.
It was a DP problem.
1D DP basically.
may I know how? I used dp + fenwick trees and found it really really complex
so you just keep track of best subsequence ending at i and best subsequence within 1 to i,
dp[i] = maximum length of neat subsequence considering only the first elements if vec[i] == 1, dp[i] = dp[i-1] + 1, else, dp[i] = max(dp[i-1],dp[pos-1]+vec[i]); where pos is starting index of that block.
No need of fenwick tree, you can store the indexes of each element of array as a[i] <= n.
Now when at a[i], we will either choose this or not, if we choose it, then we can use binary search to find whether for a[i], does their exist enough values of a[i] after i index. If it exist, then we can take it.
I wrote my idea here
https://mirror.codeforces.com/blog/entry/145815?#comment-1304972
I really feels that D>E but more people passed D...
debugging E is like torturing myself (dead)
Is the limit of D2 intended to be super strict? I tried to rush a solution at the end but could only optimize to around 2.6e4.
Use n=12900 and a[1]=110.
I tried to solve problem F1 using a query of size $$$10^5$$$ that has only 3s, and finding the length in each line using some math and bruteforce, finally, finding $$$W$$$ with another query to check the number mod 3
I got wrong answer on test 4 with this idea
does the main idea use 4 instead of 3?
The main idea use $$$1$$$ in the first query.
TC4 was probably $$$75000 \lt W \lt 10^5$$$, because my submission failed on such testcases.
My idea was to have the first query be $$$1,1,1,\dots$$$, $$$10^5$$$ times, and with that info and some NT I would get the lower and upper bound for $$$W$$$: $$$\lceil\frac{10^5}L\rceil\le W\le\lfloor\frac{N-1}{L-1}\rfloor$$$.
Then for each possible integer $$$W$$$ I would insert two words of length $$$\lfloor\frac W2\rfloor$$$ and $$$\lceil\frac W2\rceil$$$, expecting to have two words per line until the true $$$W$$$, and then (with the true $$$W$$$) to have one word per line.
But it seems to fail above $$$75000$$$ because at that point $$$3$$$ words of size $$$25000$$$ can fit on a line. I tried to fix that but I didn't have sufficient time until the end of the contest.
I made the exact same mistake of $$$\lfloor \frac{W}{2} \rfloor$$$ and $$$\lceil \frac{W}{2} \rceil$$$, the fix is actually shocking simple — just use $$$s$$$ and $$$W - s$$$ where $$$s$$$ is the smallest candidate size.
2132F - Rada and the Chamomile Valley helps me increase rating and I'll never disparage it.
I figured out that we will use bridge here. But was not able to implement correctly during contest. Now, I have done some changes, and waiting to submit & see whether it will get accepted or not.
can u elaborate? i had almost finished this exact problem but today's contest started so i left it xd
Both problems involve the Tarjan algorithm to find all edge-biconnected components.
What really!? I revised bridge-finding algorithm just yesterday and upsolved that problem. But I was still not able to solve $$$E$$$ :(
How to solve D div2?
How does this solution works when there is more than one anchor points which has same distance to (1e9,1e9) or (1e9,-1e9)? I thought there would be little differences in this cases on the contest.
Lets take example: anchor points — (0,0) (-1, 1) => both anchor point have same distance to (1e9,1e9)
Its absolutely necessary that (X + 2e9, Y + 2e9) will be on or outside the given plane and on the top right side.
Anchor points at equal distance will be compensating manhattan differences(you can take any point on the top right side). And their distance will be equal from (X + 2e9, Y + 2e9).
Same logic applies for (1e9, -1e9). Hope it makes sense!
How to F1/D1 ?
First query $$$n = 10^5$$$, $$$a_i = 1$$$, lets call the response $$$q_1$$$.
Then check how many values of $$$W$$$ would have satisfies $$$\lceil \frac{10^5}{W} \rceil = q_1$$$. You will get a range of possible values $$$[l, r]$$$.
Observe that this range will always satisfy $$$r \leq 2 \cdot l$$$ and $$$(r - l + 1)$$$ is at most $$$5 \cdot 10^4$$$ (the range [50000, 99999] for $$$q_1 = 2$$$).
So we can just query the following values — $$$l, l, 1, l, 2, l, 3, \cdots, l, r - l$$$. Notice that the corresponding values $$$l, x$$$ will be on the same line if $$$l + x \leq W$$$ or on separate lines if not. So if the response is $$$q_2$$$, the answer is just $$$r - (q_2 - l)$$$.
Is this roughly on the right track for Div1 D2? If so, any hints?
Query $$$n = 10^4$$$ blocks of $$$a_i = 100$$$ each (total length $$$10^6$$$), then:
If response is $$$0$$$, the answer is less than $$$100$$$. In this case we can just query $$$10^4$$$ blocks of $$$1$$$ and exactly one value will match the number of returned lines.
If the response is non-zero, we would have got a response between $$$1$$$ and $$$10$$$ and as such have narrowed the answer space down to at most $$$10^4$$$ candidate width values.
However, this is where I'm stuck on part 2 in two different ways since I don't have a better approach than the initial D1 approach of splitting x into two consecutive blocks of length "smallest candidate length", "remaining length"
a. This would require $$$2 \cdot 10^4$$$ more queries or $$$3 \cdot 10^4$$$ in total.
b. If the range is $$$(100, 10^4]$$$ the size more than doubles, so the approach doesn't work at all there. (maybe it results in a 1:1 mapping to number of returned lines which I can binary search on?)
Just increase $$$a_i$$$ to $$$125$$$ and make sure to query $$$1.5\times 10^4$$$ ones if you get a $$$0$$$. That works.
I forgot I could increase $$$a_i$$$, I was breaking my head trying to adjust the split of $$$n$$$ between the two queries T_T.
Though how do you handle the narrowing down query when it matches the range (125, 12500]?
the dumb [smallest candidate] [remaining length] strat still works (i used 10500 blocks of 120 and i only had to check a bit under 7k values which fits the limit very comfortably)
Either I misunderstand what you're doing in the first query, or that isn't a range you can get from that query. All valid ranges from the first query are of the form $$$[\lceil n/ans \rceil*a_i, \lceil n/(ans-1) \rceil*a_i)$$$, which doesn't match this.
who else got WA4/5 at div 2 F1?
same
Fun fact, you can submit a lot of silly ideas and they will pass test 2 and 3. I wrote a solution which prints the completely wrong value from an array of candidate answers ($$$i$$$-th smallest instead of largest) and still only got WA4.
I suspect test 2 and 3 only check small $$$W$$$ which I suspect will produce a trivial answer for most strategies.
I got a WA on pretest 4 on a submission that assumed $$$W, n \lt =100$$$ (for debugging purposes, forgot to change it back afterwards), so you're probably right.
Can someone explain me C. I cannot even think how can we use dp here
div2C — https://mirror.codeforces.com/blog/entry/145815?#comment-1304972
Got WA on test 2 for div2 D, can someone hint me whats wrong?
https://mirror.codeforces.com/contest/2136/submission/336038149
My idea was essentially to find the distance to the anchor with max (x+y) and the distance to the anchor with max (x-y), then solving the simple 2 equations linear system.
although nnot sure, but can some of the values overflow
intdata type ? like you are assigning3e9to int .. I think that is beyond the rangedefine int long long int
Suppose your were at 1e9, 0. Now when you moved 3 times up, you reached 4e9, 0. Now when you moved down, you have to move atleast 5e9, but in your code you are only moving 4 times.
You should move up one time less.
You made three up and four down. You are not down enough.
how to solve Div2D?
https://mirror.codeforces.com/blog/entry/145815?#comment-1304977
where i went wrong can anyone help 336016059
Please include the link to your submission, so the comment wouldn't be large
Your solution works when you have a single testcase, but fails with multiple testcases on one run. Make sure you erase all the data structures and variables you use.
An example on which it fails:
The correct answer is
8, but yours returns7on one of these tests.ig i'm not solving DIV2 C in this life.
I have been there, please don't give up.. you can do it !!!
BTW I am having similar feelings for problem D nowadays, which I am not able to solve consistentl,y but I keep trying
You are a cheater, please give up voluntarily.
Whats the matter with ur dedaah.. It aint my fault u got a -65
650 AC for div2E ,not even 50 can explain their code.
Sad. Why not Problem (F1 + F2)? Got an O(n^2) solution but no score >.<
Actually, there is a solution that looks quadratic, but is $$$O(\frac{n^2}{\log^{2} n})$$$ (according to authors) that is faster than the intended $$$O(n \log^2 n)$$$. So maybe you could have got AC with your "O(n^2)".
Figured out the idea behind div2 D almost immediately after reading. Brain died during implementation and couldn't figure out the math for the final formulas for the coordinates.
I have made solutions available for Contest-1046 Division-2 in java language you guys can check it on my github account https://github.com/AmbarMishra973/Codeforces-Contest-Solutions.git
You can comment for reviews or doubts Hope it helps please checkout Thanks!!!
Another fun round, congrats to the setters
It's not about winning every time... I tried 7 times in a row and couldn't solve the 3rd problem. But each attempt brought me closer to the actual solution — and that progress is what truly matters.
Hi Register, I noticed that in this round there seem to be some unusual submission patterns — for example, multiple correct submissions clustered very late in the contest. This looks a bit anomalous and may indicate unfair play (like external help or paid solutions). I believe this deserves closer review by Codeforces.
Is there anyone who solve Problem C by fenwick/segment tree
yes I did, I am the retard who did it and wasted soo much time
The solution to Div2D/Div1B is so beautiful; unfortunately I could't figure that out during the contest. And it's not the first time I had problems with the Manhattan metric. Do you guys know any similar problems? Maybe any other nice problems involving Manhattan metric?
Not necessarily a "Nice" problem, but Manhattan Pairs is a similar problem. In general, when you hear "Manhattan metric" you should probably try to split the absolute values into two sums of those that are negative and those that are positive, it has helped me twice already
Thanks for the tips, Frogmaster.
F was a fun problem. I'm surprised that more people solved E than F1.
Yeah, I solved F1 today morning to upsolve and it honestly wasn't that bad, But I guess people consider interactive problems to be harder in general, even when that's not necessarily the case.
Hello, I participated in this contest and I have a question, I tried solving the problem C:"Against the Difference", When I submit my solution, it says that it outputs 8 instead of 0 in the first test case, but when I execute my submission locally, I get the correct result. I tried every C++ compiler I have in my PC and every single time it printed 0. Why exactly does this happen? My submission is the submission 336030723.
This is the code: ~~~~~ #include <bits/stdc++.h> using namespace std; int n; vector a, mgt, DP; vector <pair <int, int> > ls; void solve(); int cp(int i); int main(){ int T=1; cin>>T; for(int i=1; i<T; ++i){ solve(); cout<<"\n"; } if(T){ solve(); } return 0; } int cp(int i){ int l=0, r=n-1; while(l<r){ if(ls[(l+r)/2].first<i){ l=(l+r)/2+1; } else if(ls[(l+r)/2].first>i){ r=(l+r)/2-1; } else{ l=(l+r)/2; r=(l+r)/2; } } return l; } void solve(){ cin>>n; a.assign(n, 0); mgt.assign(n, 0); DP.assign(n+1, 0); ls.resize(0); set temp; for(int i=0; i<n; ++i){ cin>>a[i]; temp.insert(a[i]); } for(auto i:temp){ ls.push_back({i, -1}); } sort(ls.begin(), ls.end()); for(int i=n-1; i>=0; --i){ int aux=cp(a[i]); ls[cp(a[i])].second=i; } vector <vector > tig; tig.resize(ls.size()); for(int i=0; i<n; ++i){ tig[cp(a[i])].push_back(i); } for(int i=0; i<tig.size(); ++i){ for(int j=0; j<tig[i].size(); ++j){ if(tig[i].size()<=j+ls[i].first-1){ mgt[tig[i][j]]=-1; } else{ mgt[tig[i][j]]=tig[i][j+ls[i].first-1]; } } } for(int i=0; i<n; ++i){ if(DP[i+1]<DP[i]){ DP[i+1]=DP[i]; } int ac=mgt[i]; if(ac!=-1){ if(DP[ac+1]<DP[i]+a[i]){ DP[ac+1]=DP[i]+a[i]; } } } cout<<DP[n]; return; } ~~~~~
The competition is very interesting, but there are too many interactive questions that I don't really like
Very llm-like submission
https://mirror.codeforces.com/contest/2136/submission/335958490
Many people have already tried to register for the round by clicking Register.
1c very weak pretest... i hacked >3 people
i hope next time will be div4
my handle: vishansh is disabled, please help...
As a programer, I think the problemset is awesome!
new AI created: https://vuonggpt-fe.vercel.app/
Hi, you must change to user _biscuitbc is top 1 because when I look at SirOcylder's contests, he is at top 2 at that div2 and _biscuitbc is top 1
Hi.. Can anyone please help me debug my solution for C problem 336012397 i am unable to figure this out..
You got accepted on second try, why did you ask?
Hello, I got a warning for plagiarism for my submission [335384073] for problem 2133D. I want to make it clear that I did this problem myself and did not give anyone my code. The similarity is probably by chance. Please revisit my case. Thank you.
%ekramul_1985%
The announcement changed between "at least 1" and "not equal to1" interactive problems,so the number of interactive problems is at least 2(I've discovered it before the contest)
hello , i received a system message about significant similarity between my solution and others (2136C) , i assure you this was unintentional . i wrote the code myself during the contest , the overlap may be due to using the same standard approach . i respectfully ask for your review and clarification thank you
Hello, I got a plagiarism warning for my solution 335982973 of problem 2136C. I wrote this code myself in the contest. The similarity is because the problem has one natural dp approach, so many codes look close. I didn’t share or copy anything. I kindly ask for review and reconsideration. Thanks
Hello, my submission for problem C(335950761) was wrongly flagged as plagiarism. The problem was straightforward, so many solutions looked similar, but mine is my own. Could you please review this and let me know what I can do to restore my rating?
Appeal regarding disqualification in Codeforces Round #1046 (Div. 2), Problem 2136E
Hello,
I would like to respectfully appeal the disqualification of my submission 336011664 for Problem 2136E in Codeforces Round #1046 (Div. 2). It was stated that my solution significantly coincides with others, but I want to clarify the following:
My solution is based on standard, publicly available templates and algorithms: • The Disjoint Set Union (DSU) from https://cp-algorithms.com/data_structures/disjoint_set_union.html , published well before the contest. • The FastScanner input template, which I maintain in my personal GitHub repository prior to the contest. • Tarjan’s algorithm for biconnected components, implemented based on the Codeforces blog https://mirror.codeforces.com/blog/entry/68138, available long before the contest.
I independently implemented and adapted these templates to solve this specific problem, reflecting my coding style and problem-specific logic.
I did not collaborate, share, or copy from other contestants. Similarities arise solely from the use of common, publicly known algorithms widely used in competitive programming.
According to Codeforces rules on third-party code https://mirror.codeforces.com/blog/entry/8790 and MikeMirzayanov’s blog post, using previously published code is allowed if adapted solely by the participant. I have fully complied with these rules.
I kindly request reconsideration of my disqualification and restoration of my rating and results. I am happy to provide any additional clarifications if needed.
Thank you for your time and understanding.
— ambarmishra19
Subject: Request for Review of Similarity Warning for 336010714 for the problem 2136C. I recently received a warning regarding similarity between my submission and those of other participant for problem C. I would like to clarify that I wrote my solution entirely by myself. I sincerely respect the Codeforces rules and have never intentionally violate them. I kindly request you to review this warning once again, the similarity causes due to the common dp approach for the problem. Please consider removing it from my account, This affects my profile integrity, and I assure you that I always participate honestly and fairly.