Привет, Codeforces!
Я и sevlll777 рады пригласить вас поучаствовать в Codeforces Round 1079 (Div. 1) и Codeforces Round 1079 (Div. 2). Оба раунда состоятся в 11.02.2026 17:35 (Московское время). В каждом раунде будет 6 задач, некоторые из них могут быть разделены на несколько подзадач. У вас будет 3 часа на решение всех задач. Раунд будет проведен в соответствии с правилами Codeforces и будет рейтинговым для обоих дивизионов.
По крайней мере одна задача будет интерактивной, поэтому мы настоятельно рекомендуем прочитать руководство по интерактивным задачам перед соревнованием.
Выражаем благодарности всем, кто помогал нам в подготовке этого раунда:
- Um_nik за предварительное ревью раундов.
- FairyWinx за координацию раундов и помощь в подготовке задач.
- MikeMirzayanov и KAN за лучшую платформу.
- SomethingNew, A_G за VIP тестирование.
- antontrygubO_o, Um_nik, BurnedChicken за красно-черное тестирование раунда.
- PvPro, zeemanz, k1r1t0, BledDest, triple__a, awoo за красное тестирование раунда.
- Noobish_Monk, Kolychestiy, antonis.white за оранжевое тестирование раунда.
- madlogic, robotolev за фиолетовое тестирование раунда.
- Matrosk1n, egor4444ik, slash0t, deni1000, dan00ile, Mox_Taest3r, dariasaligina за синее тестирование раунда.
- IceHydra, bessarab за бирюзовое тестирование раунда.
- Uznik_Postmoderna за зеленое тестирование раунда.
- Pimerroc, Dima-prog-coder, Manatth за серое тестирование раунда.
UPD 1: Разбалловка:
- Div. 1: $$$500 - 750 - (750 + 750) - 2250 - (2000 + 1000) - 3500$$$
- Div. 2: $$$500 - 1000 - 1250 - 1500 - (1500 + 1500) - 4000$$$
UPD 2: Разбор
Желаем всем удачи и высокого рейтинга!
Auto comment: topic has been updated by FairyWinx (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем FairyWinx (предыдущая версия, новая версия, сравнить).
Hope to be specialist.
Good Luck!
Thanks.
.
Dw vatsal chatgpt won't let you get minus, you legit practice div4 a and legit reached 1700 Ong lord
i love your insecurity bro
Is this your comeback for solving fiv4's in practice and solving e's in div1 in contests?
yuuuuu huuuuu insecure kid yu hu
Same, good luck!
Thanks
Friends, I found out why testers often write the first comments under an announcement, they are tagged and see the post as soon as it is published, even before it gets pinned on codeforces main page.
SomethingNew discovered Something new
CONTEST LEAK: This contest may require a computer that is turned on to participate in.
may is precise.
gotta be careful in case one of the problem writers starts accepting code through mail
those who code on their phones...
Phone is just small computer
It is possible to connect a keyboard to a phone.
Considering the sizes it's more connecting a phone to a keyboard.
OMGGGGGG
Hope to be able to do that interactive problem for once.
Not today
I SOLVED C GUYSSSSSSS
Yes! Me too It was pure Math :)
As a tester I wish you good luck
Hope to become expert again:)
So close.. Good luck!
3 hours. 6 problems. One newbie.
Plan: solve A calmly, fight B honestly, and respect C from a safe distance.
See you on the standings.
time to get goomba stomped
Not that important but it will be my 100th contest.
Hope to become pupil again:)
how to become a green tester
users with innate techniques vs users with mahoraga ( llm's)
Because of downvoters,I edited what I wrote here.
I had so much upvotes before :(
wishing to hit a jackpot like hakari in this contest
So true :sob:
Hope interactive problem is not a query on a tree.
rip
Good luck to everyone guys!
GLHF!
JJK???
Hey! I wanna how to be testers
again a contest clashing with codechef starters ...
CF have been arranging contests on Wednesday lately. I'm assuming that's just a coincidence.
Kirara! :o
do we have div4 contests?
hello
Acrux ⭐
imai
mimosa
Gacrux
Hope to become expert again
Do moltbot ai's participate too?
How do you decide whether to keep the duration of the constant 3 hr or 2hr
Are you Dresist because you are expert or you are expert because you are Dresist.
Olá Christopher Ciafrino, bem vindo aos comentários.
Hope that I can solve A and B, or even C! Anyway, GLHF
i hope to be expert
I think this contest will be easy.
This contest must satisfy:
🇧 $$$\ngtr$$$ 🇨
I like problem C. I need more problems like C in my life.
Didn’t think A would be that hard
I suck so bad. Slow solve on A, B, C. Couldn't solve D. Bad performance after another.
I seriously don't know if C is real or troll and why difficulty(C) > D also why is "ALICE" not accepted but "ALice" is accepted in C got a penalty for this! But enjoyed the contest!!
How can you get penalty if your solution would fail on 1st test case only since test case 1 has both Alice and Bob as answers ??
we get penalty for every resubmission right?
Wrong submissions on 1st test case aren't counted for penalty
noice!! never knew this thanks
Crazy that the one dimensional intuition for Div1 D can be extended to two dimensions (I think, I couldn't prove it)
*and for any dimensions without changes
I wonder if we have half the number of solved if A is swapped with D.
This was a complete disaster for me. The problems seemed hard largely because this is the first time I faced such problems (C and D) and I was already feeling ill and also started late because I wasn't present when contest started...
In my opinion, 2C is way easier than 2B. On the other hand, 2A is quite hard (which took me a while). By the way, can someone tell me how to do 2D please? Great contest anyway!
I solved it with sqrt decomposition.
Say you fixed i. Now, you wanna count how many j (i<j) there are such that a[i]*a[j] = j-i. We can iterate over the values the product a[i]*a[j] could have (that is, over all multiples 'm' of a[i]) and checking whether a[i+m] = m/a[i]. Notice we can stop once we reach m >= n, because j-i is at most n. This gives a complexity of O(n/a[i]) for each a[i], and it is doable if a[i] >= sqrt(n).
Now, we need to find a way to solve for a[i] < sqrt(n). My idea was to precompute the answer for all a[i] = k for some fixed k in O(n).
I will iterate over the whole vector. Say I am at the jth element. I wanna check whether this guy matches an index i (i<j) such that a[i] = k and a[i]*a[j] = j-i. Since a[i] is fixed, I simply compute their distance d = k*a[j] and I check whether a[j-d] = k. If it is, I found a pair and I increment the answer.
The total time complexity is O(n*sqrt(n)), because we precompute the answer for a[i] = k < sqrt(n) in O(n) (there are sqrt(n) many values for k) and we compute the answer by "bruteforce" in O(sqrt(n)) for the remaining elements (and there are at most n of those).
Edit: submission
You could have done when iterating for the smaller one you could have subtracted to cover the case for a[i] > a[j] basically the question wants to find i,j such that
j-i=ai*aj so i<j we can have i getting the bigger value in that case j would be smaller and you subtract and we can have i gettig the smaller value and in that case j would be bigger so u add
I solved it with a Sparse Table using a similar pruning logic!
Instead of splitting cases based on $$$\sqrt{n}$$$, I used the Harmonic Series observation for all $$$i$$$ (since all candidate $$$j$$$ must be $$$k \cdot a[i]$$$ steps away from $$$i$$$ for some integer $$$k$$$).
To handle small $$$a[i]$$$ values efficiently, I precomputed a Range Maximum Query (RMQ) Sparse Table. For each $$$i$$$, I jump through the array in steps of $$$a[i]$$$. In my search loop, I check if the 'target value' $$$k$$$ (which is the value $$$a[j]$$$ would need to be to satisfy the equation) is less than or equal to $$$m$$$ (the maximum value in the suffix range $$$[i+1, n-1]$$$).
Essentially, the condition while (step <= max_in_range) prunes the search space dynamically. If the required $$$a[j]$$$ is already greater than the maximum element available in the remaining range, I break immediately. This turns the 'small $$$a[i]$$$ case' into $$$O(1)$$$ or $$$O(\text{very small})$$$ work, avoiding the $$$O(n\sqrt{n})$$$ case-split entirely!
Submission
I think this solution is quite hard for that level.
My solution :
2.We will fix the value of a[i] first -> x, then iterate over j : i = j — a[i] * a[j], just check is a[i] = x.
3.Now do the same thing with fixing a[j] and iterating by i, here we have a problem that pair where a[i] and a[j] <= sqrt(n) are overcounted, so we just add condition that a[i] need to be > sqrt(n).
4.Time Complexity O(n sqrt(n))
5.Submission link : 362679365
You are right, your solution is much simpler.
for C2 was the intended solution to just simulate dfs using the queries and use dp to store how many paths start at each node (and use the dp values to know which query you should make to find the neighbours of the current node)? i got so many WAs
Did the same , but now I see D was easier than C2
Thank you for this contest, problem $$$E$$$ in div2 was amazing!
First time to solve 6 problem in div2 ^_^
One of my worst performances on Codeforces. 1A/2C was an amazing problem. I wish to be able to create creative problems like that.
Expected rating for the Div2 D problem?
1500-1600 would be my guess
this used to be a dumb question
I guess, O(nm / 64) was not the expected solution for E2?
Of course, I believe the solution would use a Suffix Automaton (and obviously the same greedy idea).
In E1 expected sqrr, E2 $$$26mlog$$$ :(
Well, my bitsets worked in 1.3 s
:(
manually written bitset is super fast
I submitted regular bitset in contest to E1 and it was like 2x too slow for E2. I realized after the contest that adding pragmas gets it to pass E2 in 1.7s, so you don't need anything hand-rolled.
apparently my sqrt passes E2 as well :)
For 1E1, I eumerating at each transition which position to modify next and what character to change it to, and then determining how far the resulting string can be matched.
To compute this matching, I implemented an algorithm with a complexity of ( log^3 ): I binary search on the answer, then perform a binary search on positions in the suffix array, and when comparing with a certain suffix in the suffix array, I further binary search on the LCP length.
The overall time complexity is like O(26mlog^2mlogn).
However, it runs extremely slowly in practice.
Is there any possibility to optimize this approach?
in 1e1, I enumerating at each transition, which position to modify next and what character to change it to, and then determining how far the resulting string can be matched.
To compute this matching, I implemented an algorithm with a complexity of ( log^3 ): I binary search on the answer, then perform a binary search on positions in the suffix array, and when comparing with a certain suffix in the suffix array, I further binary search on the LCP length.
The overall time complexity is like O(26mlog^2mlogn).
However, it runs extremely slowly in practice.
Is there any possibility to optimize this approach?
We can except binary search for answer just check in for, and in summary it will be $$$O(m)$$$
how to solve 1A
Bob can win only if there is $$$1 \lt = k \lt = min(p / 2, q / 3)$$$ so that $$$p - k * 2 = q - k * 3$$$. If $$$p \gt = q$$$ such $$$k$$$ does not exist, otherwise, if it exists, we can find it using binary search.
for bob to win , just check if P/Q >=2/3 (if P>=2)
Dont need to use binary search. Just see that k = q — p
Bob can keep the difference $$$q-p$$$ constant. Given this, if $$$p \gt =2(q-p)$$$ then no matter what Alice does, Bob can force the fraction $$$\frac{2(q-p)}{3(q-p)}$$$ eventually. Otherwise Alice can always outrun it.
The final fraction must be $$$2k / 3k$$$, for some $$$k$$$, and the remainder $$$r$$$ must be $$$0$$$.
So, $$$2k + r = p, 3k + r = q$$$ which on subtracting, gives us $$$k = q - p$$$, and $$$k$$$ must be $$$ \gt = 1$$$ and $$$r$$$ must be $$$ \gt = 0$$$, if it is, then Bob will win (since he can just decrement the opposite number of what Alice decrements, and eventually you will reach $$$2k / 3k$$$).
Else Alice wins.
Keeping TLEing on test 38 for E1, not sure if my suffix array computation is too slow or the algo is too slow... Is test 38 maybe alot of tests but small n?
There was a problem same as 2D/1B
This is the reason why I can solve so fast 1830B
I have feeling that F (Double Bracket Sequence) is just implementation and nothing else.
:) ~20 lines authors solution
stop graphz problems, pls.
What should be asked then, Nursery Rhymes? Stop acting as if Graphs is not a topic tag on CF. Some have problems with DP, some with Geometry, some with Interactive and now Graphs.
Div1B/Div2D is a fun problem, I wonder if there's a solution in polylog? I really appreciate if you can tell me.
I don't think O(nlogn) solution is achievable.
during the contest I tried harmonic series, but this O(nlogn) solution only works if the input constraint is changed. exp. the array is a permutation.
With Harmonic Series , It would've been O(N^(3/2)lg(N)),definitely TLE , The most optimal I could Come across till now is O(N^(3/2)) itself
A funny round,except for 1D/2F.
how did you solve 2/d 2/f
Can someone explain the solution to problem 2F/1D
We can first notice that it is never useful to modify the brackets that are already fixed. WLOG we can assume that no brackets are fixed (we can just remove the fixed ones).
Let $$$o$$$ be the number of opening brackets (
(or[) and $$$c$$$ be the number of closing brackets ()or]).Since $$$n$$$ is even and $$$n = o + c$$$, $$$o$$$ and $$$c$$$ have the same parity.
If they are both even we can fix the brackets in $$$\frac{n}{2}$$$ modifications. For each pair of brackets in the same direction, we can "flip" one of them. It is easy to see that $$$\frac{n}{2}$$$ is also a lower bound, and therefore optimal.
If both quantities are odd, then we have at least a pair of different brackets (i.e. one opening and one closing) that should be paired up.
If we can find a pair of brackets that face each other (
(]or[)) then we can fix them in $$$1$$$ modification, and since the rest are in even quantity use $$$\frac{n}{2}$$$ modifications in total. If no such pair exists, then all pairs of brackets are of one of the four following types:)(,)[,](,][. It is easy to see that these types all require $$$2$$$ modifications.This only happens if the left-most right bracket is after the right-most left bracket. That is, let $$$i$$$ be the smallest index of a
(or[, and $$$j$$$ the greatest index of a)or], then if $$$i$$$ < $$$j$$$ we can solve it in $$$\frac{n}{2}$$$, otherwise we must solve it in $$$\frac{n}{2} + 1$$$, since one pair takes $$$2$$$ modifications.P.S. Sadly, I finished implementing this only a few minutes after the contest, otherwise I would've solved all of the tasks :(.
Consider a standard string s made up of only '(' and ')'. For a sequence to be a RBS, the balance at any prefix a[i] should be >=0 {no. of '(' — no. of ')'} and the balance at the end of the string should be = 0. i.e
Note that changing an s[i] = ')' to '(' changes the balance prefix a[i], a[i+1]..a[n] by +2 and changing an a[i] = '(' to ')' changes the balance prefix a[i], a[i+1]..a[n] by -2. SO, to satisfy (1), it is ideal to change the smallest i where a[i] = ')' to '(' to increase the min for all j>=i. Next it is ideal to change the largest i where s[i] = '(' to ')' till a[n] = 0. (so that constraint (1) is still satisfied).
Also Note that if you have "..().." in your string, it is safe to ignore all completed RBS as it does not contribute anything to the constraints and is hence equivalent to our original string. So after removing all '()' using a stack iteratively like for ")()(())(": ) -> )( ->poof ) -> )( -> )(( ->poof )( ->poof ) -> )( the string is still equivalent to the original string. Now it can be seen that all ')' come after '('. so it is finally equivalent to "))))((((" basically x ')' followed with x '(' where the balance goes to -x and then goes to 0.
The minimum operations needed to convert such a string to a valid RBS depends on the number of ')'. Note it is ideal to convert the earliest k ')' and latest k '(' as proved earlier. To satisfy constraint (1), k = ceil(x/2). (changing first k ')' to '(' and hence at the xth ')' balance is k + (-1)*(x-k) which needs to be greater than 0). You need to change the last k '(' to ')' to preserve the total balance in order to satisfy (2). Hence answer for such string would be 2*ceil(x/2) = x if 2|x and x+1 if 2|x.
Now coming back to the problem finally, removing all "..().." and "..[]..", you are left with an amalgamation of ")))(((" — x1 ) then x1 ( and "]]]][[[[" — **x2 ] then x2 [** . If you combine them and get something like "]).)] ([(". you can do similar operations and get 2*ceil((x1+x2)/2) again. Just change the first ']' or ')' with the opening of ']' or ')' which is at the end. example ")...](...[" to be changed to "..." until left with nothing (2|(x1+x2) or something like "](" which requires 2 operations happening with 2 not dividing (x1+x2)) Other than that if you get "])...)... [ ) ..(...[(" . Again using the similar way as before but ignoring the first [ and last ) you will be left with "[)" which would only require 1 operation instead of 2. SO in this case answer is always x.
It is ideal as an operation is only changing 2 brackets atmost.
Hope you understood the solution. I'll try my best to try to explain if something is amiss. Thank you and have a good day!
this is absolutely legendary…
Congraaatss :)
orz, congrats on reaching lgm!
Поздравляю)
Congrats!
gratz >_<
Good quality questions, enjoyed the d2 contest, thank you!
How do you practice?
Random solving of problems with my rating + 100 — 200. I dont see editorial much, and I think practicing regularly is key.
Thanks for sharing!! But how does not going through editorials help.
I do see editorials, either after solving a problem, or after being stuck on it for hours. I Just try to spend a lot of time on the problem, though people recommend limiting it to ~ 40 mins before seeing the editorial.
At First I got TLE for in Div2D trying bruteForce....Then Got the idea to divide it through √N....Then I divided them via occurance with respect to √N...solve them each...and Conquered that
When will the Editorial be released?
If hacks were disabled for problem A to D in Div 2 then why a new test case 21 was added after contest , the same code accepted in contest now give TLE on test case 21.
If hacks were disabled for taks A to D in DIV 2 , then why after the contest a new test case 21 was added in task D. Contest submissions were only judged till 20th test case. The same code that was accepted in contest now gives TLE on test case 21.
screencast: https://www.youtube.com/watch?v=glzqG4iJuqY
brute force has passed div2 D: https://mirror.codeforces.com/contest/2197/submission/362486786
And $$$O(n\sqrt n)$$$ with big constant (double-pointers in vector) got TLE
Even wrote vector by hand will TLE, at last passed by B=300.
And 1D/2F is amazing.
has been hacked now
Can u please explain your approach.
Thanks for the sqrt problem!
I believe the memory limit of E2(div1) is too small. You will immediately get MLE if you build two SAMs.
https://mirror.codeforces.com/contest/2197/submission/362520586 Why my solution of D passed? It should be tle. When all a[i] = 1, the time complexity is O(n ^ 2), isn't it?
Not really.
In case of When all a[i] = 1, the "for (int j : pos[m / i])" will be triggered only once.
keep in mind that the outer loop loops through the multiples of some arbitary number i that must exist in 'a' and has to be less than n due to the fact that j-i < n
Nice solution btw
When will the editorial be available?
for div 2 b i was thinking like that there shouldn't be a cyclic dependency between adjacent values, like Pi can use either (A(i+1) or P(i+1)) or A(i-1) or P(i-1) whichever gives it equal value, and since i will be moving from left to right, i can safely assume left side would have correct matching P and A values.
~~~~~ if (i + 1 < n && (a[i] == a[i + 1] || a[i] == p[i + 1])) { mpp[i] = i + 1; } else if (a[i] == a[i — 1] || a[i] == p[i — 1]) { if (mpp[i — 1] == i) { flag = false; break; } else { mpp[i] = i — 1; } } else { flag = false; break; } ~~~~~ but im getting wrong answer on tc 2 itself... can someone help to find me the issue in this approach?
hey Everyone! when would we get the solutions for this contest ?
can anyone tell where do you get the solutions for the questions of contest ?
Hey everyone!
can anyone tell me where could I get solutions for the questions of contest
They are always available at the end of the announcement blog(like this one), anyways here they are
yea i do know this ,i am asking if any other sources are available ? thank you !
It's so sad that I failed E1 and E2 just because I couldn't find a correct suffix array template :(
I used an old version of ecnerwala's template (which I didn't know was not up to date) and it's actually wrong
After careful consideration, I decided to sleep
For Problem D The idea of the "sqrt decomposition" works on a very similar problem too: https://mirror.codeforces.com/contest/1541/problem/B
Hi, What does VIP testing mean?
Hello codeforces students!
Hello, I received a plagiarism warning for problem 2197E2 and would like to clarify my approach.
The query function and output formatting are unchanged from E1, as the interactive protocol is exactly the same between E1 and E2.
For E2, I independently extended my E1 solution by switching from a binary-search-based approach to a recursive DFS-style exploration. The idea is to incrementally query paths, extend edges when prefixes match, and skip already explored subtrees using cached subtree path counts.
This recursive construction with subtree-size skipping is a standard and natural approach for interactive tree reconstruction problems on Codeforces, and due to the strict interaction rules, the core logic inevitably has limited structural variations.
I used my own personal template and did not view or share code during the contest, nor did I use public IDEs or external tools.
I fully respect the Codeforces rules and understand the need to investigate similarities. I am happy to explain my reasoning further if needed.
Thank you.
Hello, I received a similarity warning for my submission for problem B.
I would like to clarify that I solved the problem independently during the contest. I did not view or share any code with other participants and did not publish my solution anywhere during the contest. The approach I used is a straightforward two-pointer/greedy style solution, so similar implementations may naturally look alike.
Please let me know if any additional information is required.
Editorial when
Hi, I received a plagiarism warning for my submission for problem 2197F.
I would like to clarify that I did not copy any code from other participants, nor did I intentionally violate any contest rules. I wrote my solution independently based on my own understanding during the contest.
I am fully willing to provide further explanation of my solution if needed.
Thank you for your time and consideration.
Can i submit the same code from two of my different accounts on the same contest to increase the rating on both the accounts as my submissions are being removed for the contest.
Hi, I received a plagiarism warning for my submission for problem 2197E1.
I would like to clarify that I did not copy any code from other participants, nor did I intentionally violate any contest rules. I wrote my solution independently based on my own understanding during the contest.
I am fully willing to provide further explanation of my solution if needed.
Thank you for your time and consideration.
I got this message from the codeforces system that says I have cheated on the Codeforces Round 1079 (Div. 1) (2196) round, which causes my Hmzaawy account to be disabled:
Codeforces System message:
Attention!
Your solution 362496700 for the problem 2196C2 significantly coincides with solutions Hmzaawy/362496700, AarushIITM/362524720. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such a violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I have nothing to say, except I do not know this guy, nor have I cheated from anyone, nor have I used any YouTube, nor Telegram, nor used AI to solve the problem and did not use any online compiler!
I did not violate the rules of the platform by any means.
What is required from my end to prove that I did not cheat?
Please keep in mind that this is just a Temporary account!
fun problems
Good luck