Привет, Codeforces!
Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов.
В 04.11.2026 17:35 (Московское время) состоится Educational Codeforces Round 196 (Rated for Div. 2).
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено решить 7 задач за 2 часа. Надеюсь, что каждый участник найдёт для себя интересные задачи в раунде.
Я бы хотел поблагодарить Михаила MikeMirzayanov Мирзаянова за платформы Codeforces и Polygon, без которых серия образовательных раундов бы не состоялась.
Также большое спасибо тестерам: ashmelev, shnirelman, awoo, FelixArg. Ваша обратная связь помогла сделать контест лучше!
Наши друзья из Neapolis University Pafos хотят поделится с вами важной информацией.
Программа бакалавриата Computer Science and AI в Neapolis University Pafos приглашает старшеклассников принять участие в конкурсе по программированию Youth Coding Challenge, который состоится 29 ноября 2026 года. Конкурс является отборочным этапом для участия в направлении Competitive Programming в рамках ACTS 2027.1.
Как один из организаторов лагеря ACTS 2027.1, мы будем рады приветствовать вас в г. Пафос, на Кипре, с 15 по 25 марта 2027 года. Вас ждут лекции, тренировочные соревнования и обсуждение задач с экспертами, среди которых Павел Маврин и Нияз Нигматуллин.
Отбор участников будет проводиться на основании результатов конкурса и предыдущих достижений.
Узнайте больше и зарегистрируйтесь до 27 ноября!
Увидимся на раунде! Удачи в решении задач.
What topics are generally asked in educational rounds
I would assume educational topics.
Name of those topics please
A,B,C are generally math & observation
I just mentioned a wide confidence interval. Agreed to your point though!
Thanks
stdio / io https://cses.fi/problemset/task/1083 https://cses.fi/problemset/task/1069 https://cses.fi/problemset/task/1094 https://cses.fi/problemset/task/1755
loops https://cses.fi/problemset/task/1068 https://cses.fi/problemset/task/1071 https://cses.fi/problemset/task/1072 https://cses.fi/problemset/task/1617 https://cses.fi/problemset/task/1618
adhoc and structs https://cses.fi/problemset/task/1070 https://cses.fi/problemset/task/1092 https://cses.fi/problemset/task/1754 https://cses.fi/problemset/task/2205
recursion https://cses.fi/problemset/task/2165 https://cses.fi/problemset/task/1622 https://cses.fi/problemset/task/1623 https://cses.fi/problemset/task/1624 https://cses.fi/problemset/task/1625
guessing
is problem rating distribution for educational rounds not announced beforehand?
in Div3,4 and educational rounds, the contest format is ICPC alike, which is similar to each problem having 1 point
Update: the contest will contain 7 problems.
why not time also increased :)
Looking for advice
would you participate? from one hand I only do codeforces to practice from the other hand registering for a div2 when I am 2085 is a guaranteed to go down especially when there is a div1 in 3 days where going to 2100+ is practically guaranteed
Just that with all the cheaters and with the fact this is only 2 hours and not IOI — ICPC times I am leaning a bit toward unranked registration but it's kind of cowardly. what do you think?
i cannot offer any advice but i'm curious why anyone would be guaranteed to lose points in a div2 but win points in div1.
Don't try to play the rating. Your goal should be to get better at cp, not to get a bigger number on your profile. Read this: https://en.wikipedia.org/wiki/Goodhart's_law .
is there a hyperlink in Read this??
It wasn't showing for some reason, I removed the formatting.
Yeah you are right, it's just to get better for the IOI + SWERC and I don't have any problem going down in rating in a Div1 it's just feels wrong to do a div2 when I am like 20th in the ranked list because there are cheaters and it would suck to go down a lot of points for that.
but I think from the bigger picture it's really does not matter and you are right
I couldnt open read this btw can you send new link?
Well what can I say, I got what I deserved
would have been place 40 if I did ranked and got +70, I am dying laughing :)
Noooo why 10 min delay
Why it is delayed?
Delayforces
Why delayed?
Don't waste my time to sleep
Thank you so much for the delay
Delay no more
why delay 10 minutes ^o^
yoo I was doomscrolling and forgot to get into the contest, W delay
me too, I was so happy about my result in AI so that I only realized 3 minutes after the contest start =D (W delay)
Honestly, it was a pretty cooked rating distribution:
A: 900, B: 1000, C: 1300, D: 2000.
A == B < C <<<<< D, E, F, G.
Or did I miss some easy observation that makes the trivial solution to D not O(n^3) simulation.
Edit: For me, C felt easier because it was just greedy.
I genuinely found D so much easier than C but then again I hate any bitwise problems
LOL that's what I think about and seriously, C and D should be swapped, but both are not really a hard problem. Just need some observation.
I don't know, the observation for D seemed to be quite difficult compared to C which was just greedy.
You cannot be telling me that binary lifting and lca to count gray vertices is easier.
Math student new to coding so it clicked better in my mind, I genuinely just need to work on bitwise.
I think F<G<<<C<<<<E
You can always get n-1 black vertices with k=n+1: 1 with n, 2 with n-1 and so on. If n is even, this is all vertices.
If n is odd, since we can always get n-1 black vertices, we are always going to be pairing up n-1 vertices with each other, which means the only choices of k that we need to care about are k=n+1 (leaving the middle number unpaired), k=n+2 (leaving 1 unpaired) and k=n (leaving n unpaired). Then for each of these cases just check if the unpaired node would be coloured gray.
Maybe stop larping
nice problems, but too tight TL
I can't be the only one who just assumed that $$$\sum{n} \leq 5000$$$ in E, and spent half an hour trying to optimise my $$$O(t \cdot 5000^2)$$$ solution T_T
?
the solution is in O(5000^2 + sum of n over tescases)
see my submission you can export all the 5000*5000 out to global
read the comment again and apologise when you realise the mistakes in your comprehension
You are right, I knew somewhat ditching all the English lessons in school would hit me :)
5 seconds away from solving G ;_;
397395985 ok Bro
Timsoh be like: ok Bro
This was a competition testing how fast you can code
I think I spent the most time thinking on C :)
$$$C$$$ was harder than everything else.
C took quite a while for me to debug, but I got it!
Now I'm thinking about D
If you haven't found the answer, a hint here
You can always find a $$$k$$$ that colors all vertices black for even $$$n$$$, and some candidates $$$k$$$ that colors $$$n-1$$$ vertices black for odd $$$n$$$. Try to express the $$$k$$$ value with $$$n$$$.
Yeah I solved it, thanks!
I don't know whether I'm stupid or not, but I genuinely believe that C is much, much harder than D and E. Yet somehow, C got significantly more ACs. I'm honestly very confused.
because it's C, most people read in order and never jump
for C, is it the right idea to count 1s at each bitwise place and then check which places will be 1/0 based on parity of the count (odd = 1, even = 0)
and then greedily compare it with 2*m and then for every bitwise place try to construct it?
I just couldn't figure out how to implement the last part
You have the right idea on counting parity.
To implement the last part, if the parity isn't correct (even == 0) then you can just decide to NOT shift a power of 2 (since that has only 1 bit set). and keep doing this from largest bit to smallest bit
Here is my solution, which took me an hour of thinking and brute-forcing to arrive at this observation. .-.
By doubling the i-th element, its value becomes 2i, which changes k to k XOR (i XOR 2i).
Now, we can observe that i XOR 2*i consists of exactly two set bits.
For convenience, we can choose elements of the form 2^k, since doubling such an element simply shifts its set bit one position to the left, resulting in two adjacent set bits in the XOR.
With this observation, we can process the bits from the highest to the lowest and use the operation described above to construct the desired k.
you can look at my solution, I implemented the same approach but with 2*or (111..110) instead of 2^m-1 (1111..1). It was a pain to work out but it works because you move from highest bit to lowest bit and recursively choose only one number from each (10000.. to 1111..) range with top bit set to 1, and then double it, so now it won't impact higher bits we have already traversed. here
I just iterated in reverse and kept a track of xorsum if I xor it with i or with 2*i and kept whichever resulted in a greater xorsum I'm kind of able to prove it but too lazy to find out if the proof's correct
can you share the proof, its too counter-intuitive for me :(
but your idea is so goated!!
$$$0$$$ IQ solution for problem C: you can just toggle a random number until you get a big enough xor.
See 397353027
Unless someone can hack it :D
test cases only have like 4 numbers bigger than 1e5 lol (wishing you luck :))
i think on average it would only take 2n toggles so i think its unhackable
My solutions for A through D:
A:
B:
C:
D:
D was much easier than C. Not my day tho :(
C is such a garbage
BIG L to this round
D is really just https://cses.fi/problemset/task/1136. really fun round tho
BledDest is always goated
That CSES problem is more generic; you can solve problem D with that technique, but problem D also allows a simpler ad hoc solution that uses a fairly straightforward O(n) algorithm.
Screencast with commentary
Could someone hack my solution to C? Filled the answer array with ones and randomly change one position at a time until found
Editorial when?
C was too hard. at least D and C were have to be swapped :)
How do I know if I am ranked or unranked?
I am currently finishing the editorial, it will be posted in about 2-3 hours. Sorry for the delay.
no worries, thanks for the contest
No problem, thanks for the great problems and the round. $$$C$$$ took a lot of time but it was really interesting!
thanks for the fun problems!
Editorial when?
come on... The number of solves was way higher than the difficulty of the problems. Honestly, this is really disappointing...
The number of solutions was way higher than the difficulty of the problems. Honestly, this is really disappointing.
Am I the only feeling that time constraint on D is too low ?
I was lacking time so I went straight to recursion (in python), and I got TLE (even after using bootstrap)
I know recursion is slow in python, but see, I increased the time constraint by moving it to a private contest, and the runtime was 2.8s.
Please tell me if I should ask for rejudging :)
What is the intended complexity for problem G?
Maybe $$$O(n 2^n + q n)$$$.
seems like most $$$O(qnlog\,t)$$$ solutions got hacked due to cache misses rather than it actually being too slow
397436687
Very fasy $$$O(qnlog t)$$$ solution by efficiently using cache.
Is C always solvable by doubling only 1 or 2 numbers? I just doubled N and if the xor wasn't high enough, I iterated from 1 to N-1 and tried doubling one of those.
Seems like that worked?
It's true
let $$$bl(p)$$$ denote the bit length of $$$p$$$
It can be shown that $$$bl(2n)=1+bl(n)=bl(2k)$$$
we need to pick a number $$$x$$$ ($$$0 \le x \lt n$$$) such that $$$x \oplus 2x \oplus 2n \oplus s \ge 2k$$$ (where $$$s$$$ is the xor of all integers less than $$$n$$$)
We'll shown that such a $$$x$$$ exists within the constrain
Define $$$u=2n \oplus 2k \oplus s$$$
$$$bl(u) \le bl(n)$$$ ($$$2n$$$ and $$$2k$$$ have same most significant bit so they cancel out; $$$bl(s) \le bl(n)$$$)
We will show that there is a value of $$$x$$$ such that $$$x \oplus 2x \oplus u \le 1$$$. When this is satisfied, $$$x \oplus 2x \oplus 2n \oplus s \ge 2k$$$ is also satisfied
Look at what happens when we do $$$x \oplus 2x$$$
let $$$d_i$$$ represent the digits of $$$x$$$ in binary
$$$x$$$ digits are $$$0$$$ $$$d_3$$$ $$$d_2$$$ $$$d_1$$$
$$$2x$$$ digits are $$$d_3$$$ $$$d_2$$$ $$$d_1$$$ $$$0$$$
$$$x \oplus 2x$$$ digits are ($$$d_3$$$) ($$$d_3 \oplus d2$$$) ($$$d_2 \oplus d_1$$$) ($$$d_1$$$)
Watch what happens if we consider these digits indvidually and do a prefix XOR
($$$d_3$$$) ($$$d_3 \oplus d2$$$) ($$$d_2 \oplus d_1$$$) ($$$d_1$$$)
($$$d_3$$$) ($$$d2$$$) ($$$d_2 \oplus d_1$$$) ($$$d_1$$$)
($$$d_3$$$) ($$$d2$$$) ($$$d_1$$$) ($$$d_1$$$)
($$$d_3$$$) ($$$d2$$$) ($$$d_1$$$) (0)
We get back $$$2x$$$. We can then right shift by 1 to get $$$x$$$. Now, $$$bl(x)=bl(x \oplus 2x)-1=bl(u)-1$$$. so, $$$bl(x)\lt bl(n)$$$ cuz $$$bl(u) \le bl(n)$$$, as stated earlier
since $$$bl(x)\lt bl(n)$$$, the constrain $$$0 \le x \lt n$$$ is satisfied
Note that when we do the prefix xor, we may not necessarily get last bit as 0. We just ignore that (it won't cause any issues since that bit doesn't matter cuz we only want $$$x \oplus 2x \oplus u \le 1$$$)
To me C is more challenging than D and E. My greedy didn't use exponents of 2 but passed the data，welcome hacking
Wait what?
For problem G, the $$$O(n2^n + qn\log t)$$$ solution works out to only about 2e8 operations, yet with a 7-second time limit, it got TLE!?
For problem D, the $$$O(n\log n)$$$ LCA solution got TLE — and $$$n$$$ is only $$$3\times 10^5$$$, even with a 2-second time limit!?
nooooooo!!!!!
send my rating back T_T.
get my rating back!
7 problems -> 5 problems
rank 40 -> rank 500
Someone might be using the judging machines to mine Bitcoin.
I agree.
I had the same problem and turns out the fix was improving cache locality
Why so many people (including me) got FST on G? Is the pretest too weak?
I think 7s is enough so I used O(n2^n+qn(logt+n)) instead of O(qn) which I think is slightly hard to implement...QAQ
Why didnt my rating increase?