BledDest's blog

Educational Codeforces Round 196 [rated for Div. 2]
By BledDest, 3 days ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of Neapolis University Pafos.

Educational Codeforces Round 196 (Rated for Div. 2) will start on Nov/04/2026 17:35 (Moscow time).

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them. I hope everyone participating finds interesting problems for them to solve.

I would like to express my gratitude to MikeMirzayanov for creating Codeforces and Polygon — without these two platforms, Educational Rounds would be impossible.

Also, big shoutout to the round testers: ashmelev, shnirelman, awoo, FelixArg. Thank you for your feedback!

Our friends at Neapolis University Pafos have message for you:

Computer Science and AI BSc program at Neapolis University Pafos invites high school students to the Youth Coding Challenge on November 29, 2026, the entrance contest for the Competitive Programming track at ACTS 2027.1.

As one of the camp’s organizing partners, we look forward to welcoming you to Paphos, Cyprus, on March 15–25, 2027, for lectures, training contests, and problem discussions with experts including Pavel Mavrin and Niyaz Nigmatullin.

Selection is based on contest results and previous achievements.

Learn more and register by November 27.

See you on the round! Good luck during the contest!

  • Vote: I like it
  • +136
  • Vote: I do not like it

»
2 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What topics are generally asked in educational rounds

→ Reply
»
46 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

is problem rating distribution for educational rounds not announced beforehand?

→ Reply
»
26 hours ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Update: the contest will contain 7 problems.

→ Reply
»
23 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    20 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    20 hours ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it +12 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      20 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      is there a hyperlink in Read this??

      → Reply
      • »
        »
        »
        »
        20 hours ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        It wasn't showing for some reason, I removed the formatting.

        → Reply
    • »
      »
      »
      20 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
    • »
      »
      »
      18 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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 :)

      → Reply
»
21 hour(s) ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Noooo why 10 min delay

→ Reply
»
21 hour(s) ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Why it is delayed?

→ Reply
»
21 hour(s) ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

Delayforces

→ Reply
»
20 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why delayed?

Don't waste my time to sleep

→ Reply
»
20 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thank you so much for the delay

→ Reply
»
20 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Delay no more

→ Reply
»
20 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why delay 10 minutes ^o^

→ Reply
»
20 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

yoo I was doomscrolling and forgot to get into the contest, W delay

→ Reply
»
18 hours ago, hide # |
← Rev. 2  
Vote: I like it -13 Vote: I do not like it

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.

→ Reply
  • »
    »
    18 hours ago, hide # ^ |
     
    Vote: I like it +7 Vote: I do not like it

    I genuinely found D so much easier than C but then again I hate any bitwise problems

    → Reply
    • »
      »
      »
      17 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      17 hours ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    18 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I think F<G<<<C<<<<E

    → Reply
  • »
    »
    18 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
18 hours ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

nice problems, but too tight TL

→ Reply
»
18 hours ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    18 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    ?

    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

    → Reply
    • »
      »
      »
      18 hours ago, hide # ^ |
       
      Vote: I like it +19 Vote: I do not like it

      read the comment again and apologise when you realise the mistakes in your comprehension

      → Reply
      • »
        »
        »
        »
        18 hours ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        You are right, I knew somewhat ditching all the English lessons in school would hit me :)

        → Reply
»
18 hours ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

5 seconds away from solving G ;_;

→ Reply
»
18 hours ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

This was a competition testing how fast you can code

I think I spent the most time thinking on C :)

→ Reply
»
18 hours ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

$$$C$$$ was harder than everything else.

→ Reply
»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

C took quite a while for me to debug, but I got it!

Now I'm thinking about D

→ Reply
  • »
    »
    17 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    If you haven't found the answer, a hint here

    Hint
    → Reply
»
18 hours ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    18 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    because it's C, most people read in order and never jump

    → Reply
  • »
    »
    18 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      18 hours ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      18 hours ago, hide # ^ |
       
      Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      17 hours ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    17 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
18 hours ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

$$$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

→ Reply
»
18 hours ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

My solutions for A through D:

A:

  • If all numbers are positive, delete all except 0 and 1. Same strategy for negative.
  • If the numbers span across 0, then we can cancel 2 numbers with the same absolute, which leaves us with only positive or only negative, which we then refer to the above strategy.

B:

  • The final array must start with smallest value X, and the rest can be multiples of X. This guarantees that any 2 indices offset by X have the same binary string value.

C:

  • We want the final XOR to have all bits be 1 (except the smallest bit doesn't matter)
  • By default assume we multiply everything by 2
  • ^ if we do the above and there are any XOR bits set to 0, then find the corresponding power of 2 (which has only 1 bit set) and DON’T multiply that by 2
  • ^ iterate from largest bit to smallest bit

D:

  • If n is even, then the answer is just n (because every vertex will be black)
  • If n is odd, then we should test out n, n+1, n+2, since these will make all nodes black EXCEPT 1 node. We just need to check if that 1 node is gray. We do this by checking each edge on that 1 node. Collect the vertices reachable by that single edge. If that set contains the pair (k — i, i) then it won't be colored grey. Otherwise, it will.
→ Reply
»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

D was much easier than C. Not my day tho :(

→ Reply
»
18 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

D is really just https://cses.fi/problemset/task/1136. really fun round tho

→ Reply
  • »
    »
    17 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    BledDest is always goated

    → Reply
  • »
    »
    13 hours ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
18 hours ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Screencast with commentary

→ Reply
»
17 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How do I know if I am ranked or unranked?

→ Reply
»
17 hours ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

I am currently finishing the editorial, it will be posted in about 2-3 hours. Sorry for the delay.

→ Reply
»
17 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The number of solutions was way higher than the difficulty of the problems. Honestly, this is really disappointing.

→ Reply
»
16 hours ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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 :)

→ Reply
»
14 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What is the intended complexity for problem G?

→ Reply
»
12 hours ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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?

→ Reply
»
8 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

To me C is more challenging than D and E. My greedy didn't use exponents of 2 but passed the data，welcome hacking

→ Reply
»
3 hours ago, hide # |
← Rev. 2  
Vote: I like it +5 Vote: I do not like it

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!?

→ Reply
»
3 hours ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why didnt my rating increase?

→ Reply