[Fixed] Speeding Up for Naive Algorithm Hello Codeforces!<br /> <br /> Recently, in JOI 2018 Spring Camp, a young genius [QCFium](https://atcoder.jp/users/QCFium), wrote a naive $O(NQ)$ algorithm in the problem [Examination](https://www.ioi-jp.org/camp/2019/2019-sp-tasks/day1/examination-en.pdf), and got the perfect score. The code is as follows <font color="red">(Fixed on 2025/5/26)</font>:<br /> <br /> <code>#pragma GCC target("avx2")</code><br /> <code>#pragma GCC optimize("O3")</code><br /> <code>#pragma GCC optimize("unroll-loops")</code><br /> <code>//Naive Solution as follows...</code><br /> <br /> I thought that it was very surprising, but actually, even $N,Q \leq 100,000$, with the only 3 lines $O(NQ)$ naive algorithm actually got accepted. To check whether this speedup is actually effective or not, I wrote these two codes: one is with the 3-line speedup, and the other is without the 3-line speedup.<br /> <br /> <spoiler summary="Code A (With speedup)"> ~~~~~ #include <iostream> using namespace std; ...

Full text and comments »

[Tutorial] Subtree lazy propagation on the link-cut tree The link-cut tree is a data structure that can maintain dynamic forest (that is, we can add/remove edges as long as the graph remains a forest) and handle various types of queries efficiently. It can handle not only path aggregation/update queries but also [subtree aggregation queries](https://mirror.codeforces.com/blog/entry/67637). Let's go further and try subtree lazy propagation ! Note that there is a limitation of the lazy propagation operator to be used in this link-cut tree trick : invertibility. For example, subtree add query meets this condition, but subtree bitwise-or update doesn't. Alternative ways ------------------ The top tree can perform subtree update queries quite naturally, without requiring invertibility, but it's a bit hard to implement and has a relatively big constant in running time. The euler tour tree can perform subtree update/aggregation queries efficiently but can't handle path queries. Terms ------------------ auxiliary tree : the splay tree used t...

Full text and comments »

ICPC WF 2026 Team List Hello Codeforces, Earlier this month, the ACPC (African and Arab Collegiate Programming Championship) concluded, determining the teams qualified for the ICPC World Finals from our region. I decided to write a blog post to gather the full team list somewhere (yes, I know this is very early and most championships are still in March, but I'm so excited anyway, and I already had the script for the ACPC list, so why not!) To add your team to the list, please comment these details: - Your region - Your country - Your university - Your team name - Team members' handles Wish everyone the best of luck in preparing for the ICPC, and can't wait to meet you all! <h2>Northern Eurasia</h2> <table> <tr> <th>Country</th> <th>University</th> <th>Team Name</th> <th>Member 1</th> <th>Member 2</th> <th>Member 3</th> <th>Team Rating</th> </tr> <tr> <td>Russia</td> <td>HSE University</td> <td>FFTilted</td> <td><a href="https://mirror.codeforces.com/profile/teraqqq" style="color...

Full text and comments »

Teams going to ICPC WF 2023 (Egypt 2023, 2nd final) — WIP List Hi again! As we decided in [the other blog](https://mirror.codeforces.com/blog/entry/116946), let's have two differents lists, one per WF that will be held on Egypt. We'll fill this post with teams of **THE SECOND WF** in Egypt, assuming that those are the qualified from Regionals 2022/2023. Please add a comment with your team information and I will add it to the post. Info preferred: **{Handles on CF (otherwise, real name), Region, Country, University}** If you see some mistake on the teams, any kind of correction would be appreciated, also if you see here a team that belongs to the other post (or viceversa), let me know. </table> # Top 15 Over-All <table><thead><tr><th>Rank</th> <th>Country/Region</th><th>University</th> <th>Member1</th> <th>Member2</th> <th>Member3</th> <th>Rating</th></tr> </thead> <tr><td>1</td><td>Japan</td><td>&#129353; Tokyo Institute of Technology</td><td>[user:potato167,2024-05-01]</td><td>[user:tatyam,2024-05-01]</td><td>[user:noshi91,2024-05-...

Full text and comments »