Hello Codeforces!

We are really excited to invite you to participate in Codeforces Round 1089 (Div. 2), which will be held on Mar/29/2026 17:35 (Moscow time).

You will be given $$$6$$$ "simple" problems and $$$2$$$ hour $$$15$$$ minutes to solve them. Note that one of the problems will be further divided into $$$2$$$ subtasks. Furthermore, some of the problems may be interactive, so please read the guide for interactive problems if you are not familiar with them. This round will be rated for the participants with rating lower than 2100.

The scoring distribution is as follows:

The problems are authored and prepared by simplelife, ritam1234, __baozii__, and me.

We would really like to thank the following people for making this round possible:

• cry for his orz coordination and support throughout the round, and also for rejecting a lot of problems.
• Alexdat2000 for Russian translation.
• __baozii__, wuhudsm and Intellegent for VVIP testing.
• VladiG, sammyuri and macaquedev for their "Special Contribution".
• Dominater069 for LGM testing
• kevinxiehk, awesomeguy856, sammyuri, _istil for Red testing.
• amsraman, awang11, Proof_by_QED, temporary1, VladiG, CutSandstone, -firefly-, AksLolCoding, Friedrich and 0x3F for Orange testing.
• SpyrosAliv, AkShukla, tin.le2, wakanda-forever and Edeeva for Purple testing.
• IceSerpent, DivinePunishment, chromate00, Ermiooo159, expertaq, Ananya_agr, alex_rider123, kryoton_98, susvent, Jteh, apollo07 and beaten_by_ai for Blue testing.
• nik_exists, dipamsen, GlidingNinja_ccn and RJ_Parin_fr for Cyan testing.
• ukcsstudent for Green testing.
• MikeMirzayanov and KAN for the Codeforces and Polygon platforms.
• And finally, You, for participating.

UPD : Editorial link. Hope you enjoyed the round. We are sorry for the unexpectedly hard C2.

UDP2 : Congratulations to the winners!

Top $$$5$$$ overall: (subject to change)

1. Geothermal
2. YuukiS
3. NotNanYan
4. yanchengzhi
5. im_xRayVN

Top $$$5$$$ rated participants: (subject to change)

1. NotNanYan
2. yanchengzhi
3. im_xRayVN
4. NekoType_
5. makeit427

I was solving the Planets Queries I problem in CSES (a standard binary lifting problem).

After getting a few TLE on one of the test cases, I finally got AC, but it took 1.00 seconds to pass that test case, which is way too close. On checking other submissions with exact same logic, and investigating a bit more, I changed vector<vector<int>> declaration in my code to static int array declaration, and my code, with everything being exact same, worked in 0.60 seconds.

Usually there shouldn't be such a drastic difference. While solving codeforces problem, I have observed that vectors and static array take the same time, and sometimes vectors are faster.

Can anyone explain the reason behind this? Thanks.

Submission using vector<vector<int>> : https://cses.fi/paste/7d2b7a0b66df52a2ea28b6/

Submission using static int array : https://cses.fi/paste/6d8b9ef1a192caa1ea28f1/

Update: In my implementation, If I did vector<vector<int>> node(31, vector<int>>(n+1)) instead of vector<vector<int>> node(n+1, vector<int>>(31)), basically swap i and j, the same test case now passes in 0.55 seconds.

Basically in my original implementation, let's say I call dp[i][j], I was fixing j and iterating over i, which is horrible from cache locality POV. It doesn't help that vector allocates multiple heap blocks instead of one continous block. (There was a recent blog on this topic, refer that) Instead of this, fixing i and iterating over j, is much more cache friendly and makes a drastic difference in time.

It doesn't make a drastic difference in static arrays since unlike vector, they are not fragmented. (I am not exactly sure about the reason, will research a bit and then update)

For comparison, I did the same thing with my static array implementation, and now the static array implementation runs in 0.55 seconds as well. There isn't any time difference here.