The Ultimate Topic List (with Resources, Problems and Templates) This post took $4$ years to make. And this is the most significant thing that I have ever shared in my whole life. #### Story Hi, I have been doing CP for like $4$ years and from the very beginning what I have been feeling is a need for a comprehensive topic list that will contain all sorts of topics from easy to advanced with corresponding tutorials, problem lists and templates so that I wouldn't have to look at different sites, from here to there. So what do you do when you think something is missing from the world? Yeah, you create that thing! So here I am, sharing the ultimate topic list that you will need in CP. When I say that it took me $4$ years to make it, I genuinely mean it. I have been collecting them from the inception of my CP journey and yesterday I thought that it got its almost complete shape. You may not imagine the sheer excitement hidden under each of the characters of this post. #### Payment You can pay me just by upvoting this blog and by being a bet...

Full text and comments »

My opinion on how to practice competitive programming I'm not very often replying to questions about how to practice, but as I'm getting enough of them (and I've just seen another blog about practicing) let me tell you about it. Of course, every time when you ask someone good about how to practice, he/she will reply to you to "solve a lot of problems" and that's true, there's no other way. Anyway, I've thought about it and actually I'm able to tell a bit more. I know some people, I've seen many people practicing (including me) and I have an opinion. Many people practice in some organized way. High schools organize IOI/OI training contests every Saturday, universities organize ICPC training contests once a week, people try by their own to solve three problems each day, websites host rounds and so on. Here's a secret: it's a sh*t. Yep, that's true. If you want to be really good and to make it happen you compete in a training once a week, you do it only to be able to make excuses "but I'm training so hard" when you see no progress. ...

Full text and comments »

0 Problems Remaining [日本語記事(For Japanese Speakers)](https://maspypy.com/codeforces-all-ac) ---- Previous post: https://codeforces.me/blog/entry/150057 Submission: [submission:384239819] 2026/07/26 03:13:42 JST (2026/07/25 18:13:42 UTC) I have solved every problem in the Codeforces PROBLEMSET except for those for which I determined that obtaining an accepted verdict is impossible.  # Scope I considered the problems listed in the [PROBLEMSET](https://codeforces.me/problemset). I have solved very few problems from the [GYM](https://codeforces.me/gyms). The only collection I worked through systematically was the PROBLEMSET. I determined that it is theoretically impossible to obtain an accepted verdict for the following 31 problems: [problem:775A], ([92101](https://codeforces.me/problemset/problem/921/01) ... [92114](https://codeforces.me/problemset/problem/921/14)), [problem:927A], [prob...

Full text and comments »

Red Isn't Impossible _I waited for more than a year to write this blog._ I started CP in July 2017, I always dreamed about reaching red, and it finally happened. I didn't become red like talented contestants in 1-2 years, but it took me more than that. The start of my CP journey was average (you can see my graph); It took me more than six months to reach pupil, then another six months to get specialist, and it took me more time to achieve higher ranks. I didn't have any mentor or coach. So, I asked many stupid questions, which you can find if you read my old blogs. One of these questions is, "What's the importance of Dynamic Programming?" (I drafted this blog xD), But of course, I don't motivate people to ask these types of questions as they usually can be answered by just searching. I failed many times during my journey in CP, especially in important competitions (IOI21 and IOI22). I stopped CP many times because I was frustrated and believed I could never improve. For example, I stopped when I w...

Full text and comments »

[Tutorial] Generating Functions in Competitive Programming (Part 1) Hi everyone! Inspired by the recent [Codeforces Round 641](https://codeforces.me/contest/1349), I decided to write an introductory tutorial on generating functions here. I am by no means an expert in generating functions so I will write about what I currently know about them. [user:MiFaFaOvO,2020-05-15] has written a really interesting [blog](https://codeforces.me/blog/entry/76447) here on Codeforces about more advanced applications of generating functions, but I think there is no English tutorial on the basics of this topic yet (or at least on CP sites). Thus, I would like to share about this topic here. I plan to split this tutorial into two parts. The first part (this post) will be an introduction to generating functions for those who have never learned about them at all, and some standard examples and showcases of generating functions. The second part will be a collection of several applications of generating functions in CP-style problems. If you are already familiar with ge...

Full text and comments »

Self-deception: maybe why you're still grey after practicing every day I generally don't like to give much advice on "how to practice", but recently I have been thinking a lot about this and I realized that there is something that I believe affects a lot of people (though it is admittedly hard to tell) that barely gets talked about: self-deception. Self-deception is a devious thing. It can be very hard to detect, yet can be fatal to improvement. This blog is mainly directed to greys, greens and cyans that can't get out of these categories. Most examples are given with that in mind. That being said, I believe others have something to think about as well. This is my first blog on such "psychological issues" and I don't know if I'll ever make another one. It's certainly a difficult topic to write about because for most of the blog, the message is "your practice is not as good as you think it is" or even "you aren't as good as you think you are" which can of course be a hard thing to hear. Thus, I have to somehow be very gentle while getting the poin...

Full text and comments »

How to practice Competitive Programming [Um_nik version] CP is about solving problems fast. And as absurd as it may sound, I believe that <span style="color:blue">SOLVE</span> and <span style="color:red">FAST</span> are very different and almost independent parts, and you need to practice them separately. Let’s look at some <span style="color:red">contest</span>, like a CodeForces round. For the sake of simplicity let’s assume that every problem has some *difficulty*, which is a numerical value denoting how hard it is, bigger values correspond to harder problems (it is not true, but it is an ok-ish approximation, at least if we consider subjective difficulty for a fixed person). Contests are made for a wide range of participants, and problemsetters strive to make contests interesting for a wide range of participants, which means having a *smooth difficulty gradient*. Well... as smooth as it is possible with 5-6 problems. <spoiler summary="Graph 1"> ![ ](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/677e0ae2-a8df-4874-aff...

Full text and comments »

Unimportant Um_nik Update Hello Codeforces! I have some big news. I am trying to fight depression and live a fuller life. That includes some self-realization, maybe even (I don't even want to think about it) a job. I love cp, and I love teaching, and I know I already tried that, but I believe that this is the way. With the help of my wife, I started to work on some related projects, and today we want to share them with the world. All of them are in the early stages, but we set a hard deadline for March 1, so... Um ================== Um... I am starting a series of educational YouTube videos / selected problems. Every episode of Um is focused on one problem. I will explain how to solve this problem and talk about some related concepts. The idea is to show off some cool concepts using real problems. The kicker: the problem is made public at least a week before the episode airs. So you can use Um as a source of problems. I will try to choose nice problems that highlight some ideas, and problems ...

Full text and comments »

Some thoughts on recent discussions Hello everyone! I finally decided to write some response/explain my view after all recent discussions of my problems and rounds I coordinate, and I would like to make a few points. **1.** After some recent contests there were a lot of comments saying that Data structure problems should appear as easy problems (say, D2A-D2D in a Div2 of $6$ problems)    I don't think I agree with this. To begin with, I don't think that having Data Structure problem is a requirement for a good contest at all, not just in first few positions.  However, for positions D2A-D2D, I just don't see a way to properly include data structure problems. Take some Data Structure problem, it consists from two parts: <ul> <li> Knowing/implementing the Data Structure </li> <li> Actually thinking about the problem, and how this Data Structure...

Full text and comments »

Mike, alts and unfriendly comments I know that the following content might not be welcomed and I will lose lots of contribution, but I should write something about such a bunch of chaotic comments under there. I may delete this tomorrow if I find my words useless. ### What happened Several months ago, Mike posted a blog about banning [user:orzdevinwang,2024-10-07]'s alt, [user:zh0ukangyang,2024-10-07], and more alts. Lots of participants, including myself, were angry because [user:zh0ukangyang,2024-10-07] is such a talented coder and codeforces didn't treat the rule of single account seriously at that time. Then more and more alt accounts with high rating are reported, including mine. After that I didn't use alts anymore, and most of high-rated Chinese participants(100% in my friends) discarded their alts and followed the rules. We might think that the rules are not that perfect, but rules are rules. I believe that no one will say "Banning [user:zh0ukangyang,2024-10-07] is unacceptable". But I know what y...

Full text and comments »

(The Ultimate) Code Library Hey everyone, I am sharing my personal code library where I compiled **almost all** the important templates that you will need in CP (saying almost just for courtesy). Most of the codes are originally written by me and some of them are collected from others but modified in a cleaner way. Link: [https://github.com/ShahjalalShohag/code-library](https://github.com/ShahjalalShohag/code-library) It took me around 4 years to complete the list. Maybe each line is just a line to you but to me it tells a story of the excitements I had while learning those stuffs, the sleepless but fun nights I had to seek knowledge. ###### Why am I sharing this library? - Just so that your learning path becomes a bit smoother. - Knowledge hidden inside my head or codes in a private code-library will be useless when I am dead, so it's better to share those among people before I die. Also, you can make me happy(as in to pay me) just by upvoting this blog and giving a star to the repository. I beli...

Full text and comments »

Complex FFT is not as bad as you think ... Probably. Hi everyone! As some of you _might_ already know, I don't like NTT. Primary reasons for this are: - I don't like modular arithmetic optimizations (Montgomery, etc). - I don't like NTT mods, and prefer good, old $10^9+7$. - I do like algebra of complex numbers. But, to my regret, the overwhelming mainstream in modern competitive programming is NTT. Primary reasons are: - It's allegedly faster. - It needs less memory. - It has no precision issues. - People don't like algebra of complex numbers. There is nothing I can do about the last, but today I'll address the first 3. Optimizing complex FFT was on my mind for quite some time, but I didn't really work on it _that much_ until the [blog](https://codeforces.me/blog/entry/142063) by [user:Qwerty1232,2025-04-24] on optimizing NTT has dropped, which motivated me to actually put some serious effort into this. In this blog, we will primarily focus on optimizations that are specific to complex arithmetic...

Full text and comments »

Welcome to Bingo-CP Hello Codeforces! Are you tired of only doing virtual contests? Want a more fun way to compete with friends, alone or on a team? Try Bingo-CP. ### What is Bingo-CP? Bingo-CP is a free web app that turns Codeforces practice into a quick social game. Problems are placed on an n×n bingo board. Teams of 1–4 players compete at the same time. The first team to complete any row, column, or diagonal wins. Try it: https://bingo-cp.vercel.app/home ### How to play **1.** Click "Create Match" as in the picture. **2.** Choose grid size (3×3 to 6×6), start time, duration, rating range, and mode. **3.** Add team members by Codeforces handle (1–4 each). **4.** Start the match. All teams solve at once. The first accepted submission claims the square for the team. **5.** First team to complete a row, column, or diagonal wins. Solves are detected automatically from Codeforces submissions, so no one needs to claim squares manually. ### Match options Start time and du...

Full text and comments »

When will Codeforces end? The last mark in the updated ranking history As you know, Codeforces recently added the ability to scroll through the user's rating history. I decided to take this opportunity to find out how long this wonderful service plans to exist. To do this, I went to my page, looked at my rating <spoiler summary="Spoiler"> and began to cry </spoiler>  Next, I began to zoom out as much as possible. At one point, I got something that looked like the flag of Indonesia.  After zooming out a bit more and scrolling a bit to the right, I found that at some point new divisions stop being added. To be more precise, this is about the 251st millennium:  It seems that we are close to a solution! It remains only to zoom in to see a more accurate value.  So, 275760 is, apparently, the last year of Codeforces' existence! Let's zoom in even more to get the accuracy up to a mont...

Full text and comments »

The Reason You are Bad at Codeforces — You are Not Russian Enough If you are triggered by this clickbaity blog title, you are probably interested in improving your Codeforces skills. Now, I will share my point of view on the differences between Codeforces and ICPC contests, and how you can, in my humble opinion, maximize your Codeforces rating gain. I mostly consider that all conceivable competitive programming problems need three aspects of skill: 1. Observation &mdash; the ability to understand the problem and come up with non-trivial properties. 2. Technique &mdash; the ability to apply a well-known algorithm or data structure to the problem. 3. Implementation &mdash; the ability to code fast and debug fast. Collaterally, I refer to these three skills as Russian-ness, Chinese-ness and American-ness, respectively, for reasons you will soon see below. ## Observation (Russian-ness) Observation means that you stare at some problem for a sufficient amount of time and you are able to reduce it to some easier problem. One good proble...

Full text and comments »

Matrix Exponentiation tutorial + training contest tl;dr &mdash; video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.me/gym/102644 (register by finding this contest in GYM instead of using the link directly) video editorial: [part 1 (ABCDEF)](https://www.youtube.com/watch?v=kQuCOFzWoa0) and [part 2 (GHI)](https://www.youtube.com/watch?v=RA_SpxP2t54) codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices) The youtube tutorial ([link](https://www.youtube.com/watch?v=eMXNWcbw75E)) focuses on intuition and graph-like visualization . Or, if you prefer, below is a shorter (less detailed) text tutorial instead. You can practice by solving a set of 9 educational problems in GYM https://codeforces.me/gym/102644. ABCD are easy, EF medium, GHI are hard. If you are stuck, see hints below or watch the full solution analysis &mdash; [part 1 (ABCDEF)](https:...

Full text and comments »

You won't believe how this simple trick defeated the unexplained bug destroying every top LGM ### TL;DR Currently people are discussing a slowdown bug on Codeforces that seems to happen randomly, and can cause code to run 100x slower and get TLE. More details in [user:pajenegod,2024-03-03]'s [blog post](https://codeforces.me/blog/entry/126654). In this article, I present a mitigation: add the following to your code. ~~~~ #include <windows.h> void *operator new(size_t size) { if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr; throw std::bad_alloc{}; } void operator delete(void *ptr) { HeapFree(GetProcessHeap(), 0, ptr); } ~~~~ <spoiler summary="If you use malloc/free in C++ (you shouldn't), also change them."> ~~~~ void *my_malloc(size_t size) { if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr; throw std::bad_alloc{}; } void my_free(void *ptr) { HeapFree(GetProcessHeap(), 0, ptr); } ~~~~ </spoiler> <spoiler summary="If you use aligned new/delete in C++, also change the...

Full text and comments »

[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.me/blog/entry/69287?locale=ru)]** Hello, CodeForces. I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming. I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.) Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke...

Full text and comments »

[Tutorial] Common Mistakes in Competitive Programming and How to Avoid Them One thing is for sure. You do make mistakes. I also make miskates and that's what makes us human. But what we can surely do is &mdash; to try to minimize the errors that we make throughout our life. I have compiled some of the mistakes that I made in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in C++ as it is the most used language for CP. **So, if you are new to CP, stick with me as you might don't wanna repeat the mistakes that I made when I was a beginner.** #### Mistake 1 Check out the following code: <spoiler summary="Code"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int a = 1000'000'000,b = 1000'000'000; long long product = a * b; cout << product << '\n'; return 0; } ~~~~~ </spoiler> The outp...

Full text and comments »

[Tutorial] Li Chao Tree Extended Hello everyone! I discovered a new (?) trick on how to apply lazy propagation on the Li Chao Tree and decided to write a blog about it. I've personally never seen it before (outside of myself), nor have I seen a problem that needs the Extended Li Chao Tree specifically, but it *can* overkill some problems. Of course, I might not be looking hard enough... You can learn about the basics of Li Chao Tree from [cp-algorithms](https://cp-algorithms.com/geometry/convex_hull_trick.html) or [this simple blog](https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html). The Extended Li Chao Tree can do the following problems (and other variations): ## Problem 1 There is an array $A$ of size $N$. There are $Q$ online operations: - Range Line Insertion. Given $l$, $r$, $a$, $b$, do $A_i = \max(A_i, a \cdot i + b)$, $\forall i \in [l, r]$ in $O(\log^2 N)$ - Range Line Addition. Given $l$, $r$, $a$, $b$, do $A_i += a \cdot i + b$, $\forall i \in [l, r]$ in $O(\log^2 N)$. - Po...

Full text and comments »

CP-Algorithms: Hacktoberfest 2024 + call for contributors and maintainers Hi everyone! <img src="/predownloaded/82/15/821540e8f87d8a2b2d468377aacbba80b0aa1623.png" style="float:right;" width=100px> I'm posting this on behalf of **[CP-Algorithms](https://cp-algorithms.com/)**, a community project that [started off](https://codeforces.me/blog/entry/13198) in 2014 by [user:RodionGork,2024-10-13] as a translation of [e-maxx](http://e-maxx.ru/), a Russian go-to resource at the time by [user:e-maxx,2024-10-13] for learning core competitive programming algorithms. Since then, CP-Algorithms grew quite a lot (which also prompted a rename from original project name `e-maxx-eng`) and includes a lot of new, original articles, and a lot of translated articles were enhanced and/or extended or even completely rewritten, amounting to a total of 157 articles at the moment. At the moment, the project is largely maintained by [user:Jakube,2024-10-13] and [user:adamant,2024-10-13] (that's me), but as it happens, we don't have as much time to dedicate to it as we used...

Full text and comments »

A Huge Update on The Ultimate Topic List Hi, around 3 years ago I compiled most of the Competitive Programming topics in one place [here](https://codeforces.me/blog/entry/95106) with relevant resources, templates, and problems. It got great responses, it now has 4000+ upvotes and the blog website has been visited 200k+ times! But it contained links to only 1-2 resources and problems per topic and it didn’t contain basic topics for beginners. Also, there was no way of tracking your progress. This time I decided to improve it, by a lot. I took this project one month ago and it took me on average 6h-10h per day for the last one month to complete this project (also I was doing a full-time job). I hope it was worth it! The new version is not just a blog, it is a full-fledged website with multiple features (I have hosted it on one of my existing websites):  - **Topics:** The website contains around 500 topics and tricks. Not all topics are ...

Full text and comments »

On setting D2A and D2B problems Disclaimer: as always, everything in this blog is just my opinion. Some problemsetters don't take easy problems seriously. One very popular opinion is that the D2A-B problems are just stupid implementation exercises intended for beginners to learn how to code.   It's true that D2A-B problems are mostly like this on most platforms. This is one of the reasons why a lot of people don't like combined rounds: they think that solving D2A-B problems can't be interesting and just takes time which could be spent on solving fascinating problems of higher level. From point of view of most participants, easy problems just can't be good, because if problem requires some thinking than it's not easy enough for D2A-B level. Easy problems can't be interesting, they say!   This situation really upsets me. This kind of attitude from the ...

Full text and comments »

Train Better with ThemeCPs (+ Website)! Hello Codeforces! I am excited to share with you my competitive programming innovation which successfully propelled me to master (2100+)! This is the **<span style="color:black;">Theme</span><span style="color:red;">CP</span>** training method, which stands for **Themed <span style="color:red;">C</span>odeforces <span style="color:red;">P</span>rogressions**. Use at your discretion -- your Codeforces practice may get too effective and addictive!  **Want to read this blog in document form (with images)? Check out the following Google Doc!** https://tinyurl.com/themecp #### What is **<span style="color:black;">Theme</span><span style="color:red;">CP</span>**? **<span style="color:black;">Theme</span><span style="color:red;">CP</span>** is an experimental training system wherein users train on a perpetual ladder for ratings in **[<span style="color:gray;">900</span>, <span style="color:black;">3</span><...

Full text and comments »

I Reached GM after 5 years Hello Codeforces! I did it! My main goal for 2022 was to reach red and I succeeded in the last contest of the year by getting +1 delta and going from cursed 2399 to 2400! I was very happy but scared to celebrate because I was worried that my rating would go down to 2399 again after the cheater removal. But now it’s 2401, so I think I’m safe now. Why am I writing this blog? I'm very excited about this achievement, it means a lot to me and I want to share my happiness with Codeforces. Also people ask me in DM quite often about how I got onto this level or who I am in general, so I think it's time to summarize it all into one blog post. Oh, wait… You don’t even know me, so why should you keep reading this blog post? Let me introduce myself a little first. I’m a high schooler from a small European country where few people do Codeforces. I love competing in OI and MO, I always did. One day, my father found the Codeforces website and suggested that I should start practicing there. At ...

Full text and comments »

I have solved problems on Codeforces for 500 days in a row It's been a while since I started my journey into competitive programming and in this year and (almost) a half I would say that I learned a bit not only about problem solving but also about myself, so I wanted to share my reflections on some mental aspects of practicing competitive programming hoping they can help someone else. Please note that these reflections are merely personal and mostly stem from personal experience, if you disagree with something I would like to know your point of view! I would also like to thank [user:Intellegent,2025-12-08], [user:turska,2025-12-08] and [user:LMeyling,2025-12-08] for proofreading.  #### Some background I used to do math olympiads for 8 years before starting university, in hindsight I did not really like it that much since I never practiced on my own and would've rather played League of Legends / Minecraft / VALORANT or whatever game I was obsessed at the time. ...

Full text and comments »

[Photos Dump] Jollybee CP Team, the Luxor WF, and the Indomie Aftermath Whether or not you went to the ICPC WF 2023 in Luxor, you might remember us from the [Indomie trade offer blog](https://codeforces.me/blog/entry/127903) a while back. Aside from my team ([user:rfpermen,2024-04-30], me, [user:vioalbert,2024-04-30], and [user:siplusplus,2024-04-30] as coach) in the previous blog, of course our university's team for the 46th WF ([user:Owmicron,2024-04-30], [user:zeroscar,2024-04-30], [user:KerakTelor,2024-04-30], and [user:Yoshiyuki,2024-04-30] as coach) also joined us in many of our activities, including finding people to trade and/or give the two boxes of Indomie we brought to Luxor. In this blog, I'd like to share some of the pictures we ([Jollybee](https://www.instagram.com/binusjollybee/), the CP team in our university) took with others during the WF. **UPD:** There were several issues with the images; they weren't loading properly. The images are now hosted on ImgBB. ## Signed T-Shirts After doing something similar when I was parti...

Full text and comments »

Lecture #3 — Exchange arguments (sorting with dp) Hi. I'm back from USA! I will do a new lecture tomorrow (Thursday) at 2pm CEST on my Youtube channel: [https://www.youtube.com/watch?v=7hFWrKa6yRM](https://www.youtube.com/watch?v=7hFWrKa6yRM). Watch me live (and ask questions), or just watch the video later. This will be part 1, and I will do part 2 in a few days (maybe Tuesday). **UPDATE** &mdash; part 2 is coming on Thursday, same time. Link: [https://www.youtube.com/watch?v=gXxu-Cr4b4c](https://www.youtube.com/watch?v=gXxu-Cr4b4c). There are no prerequisites this time. I recommend reading the materials below in advance, and trying to solve problems 1 and 5. If you are strong, just read problems and see if you can't solve something (maybe problem 8?). ### Technique "Exchange Arguments" If we're given $n$ items and we should choose some of them and choose their order, we should sort them with some strange/tricky comparator, and then do $O(N^2)$ dynamic programming. The dp should be $dp[pref][used]$ &mdash; best po...

Full text and comments »

I might get stigmatized for this, but here it goes Recently, Moscow Fall Workshops has taken place (it ended about one week ago), and I wanted to address some issues that came into my mind during that period. As you might notice, it took me some time to build the courage and get in the right mindset to write about this. First of all, I want to say that I am a huge supporter of programming camps and, in general, initiatives to enhance the joy of doing competitive programming and I respect the efforts of building communities around CP. I have always had a kind of excitement when thinking about participating in programming camps (Petrozavodsk, Moscow Workshops, etc.) and their “hardcore” style with lots of contests. I therefore appreciate the immense efforts of organizers, problem setters, and testers, when preparing this camp. ### Main point Coming towards the main point of the blog, I felt that the last programming camp was a bit… underwhelming. Moreover, I’m having a hard time trying to justify the costs of doing such a camp,...

Full text and comments »

[Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm What's a Voronoi Diagram? ------------------ Given a set $S$ of $n$ points in the 2D plane, the Voronoi diagram is a partition of the plane into regions. The region associated with a point $p\in S$ contains precisely the points $q$ such that $q$ is closer to $p$ than any other point in $S$. In other words, a point $q$ belongs to the region of its nearest neighbor. <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Euclidean_Voronoi_diagram.svg/1024px-Euclidean_Voronoi_diagram.svg.png" width="300px" height="auto"/> The Voronoi diagram can be represented by the planar graph of boundaries between regions. A vertex in this graph is where three or more segments meet (or a point at infinity), and an edge is a segment connecting two of these vertices. The way the regions were defined, we see that a segment contains the points equidistant to two points in $S$, so it is part of their perpendicular bisector. Similarly, a Voronoi vertex is equidistant to three or more v...

Full text and comments »

[Tutorial] Square Root Techniques _This is my 100th CF blog!_ This is a list of techniques with $O(\sqrt n)$ time complexity. Watch the lecture https://youtu.be/BJhzd_VG61k, with timestamps! 1. Square root decomposition &mdash; split the sequence into blocks of fixed size. 2. Splitting objects (e.g. vertices) into light and heavy. 3. Square root decomposition by the time of queries & rebuilding the structure. 4. Mo's algorithm &mdash; processing queries in proper order and updating the answer by erasing/inserting new elements. https://cp-algorithms.com/data_structures/sqrt_decomposition.html 5. Strings &mdash; if the sum of lengths is $S$ then there are at most $\sqrt{S}$ distinct lengths. 6. Birthday paradox & baby-step giant-step. See P4 and P6 [here](https://codeforces.me/blog/entry/95571), and see https://cp-algorithms.com/algebra/discrete-log.html. P1. [problem:398D] P2. [problem:220B] P3. <s>[problem:86D]</s> (actually, skip this one because it's boring) P4. Count triangles in a graph, i....

Full text and comments »

"Algorithms in Depth" Stream Series: Kicking Off With FFT Hi Codeforces! I’ve long believed that it's _really_ worth revisiting the same competitive programming topics multiple times. The first time, you’re just trying to survive and maybe grasp the basics. The second time, you’ve solved some problems, you know where you got confused, and you're ready to absorb more. By the third time, you’ve seen and solved enough to start appreciating the subtleties — the tricks, advanced applications, deeper meaning. But most lectures I’ve seen are designed as a one-size-fits-all — trying to cover everything from scratch _and_ dive into the advanced stuff in one go. That’s rarely optimal. Take binary search. I once talked about it for six hours straight. A beginner at that lecture would’ve probably quit CP immediately. And that’s ok. Beginners don’t need all that. But the truth is, there _is_ that much depth to explore even in seemingly simple topics like binary search — once you're ready. Yet many people only see the beginner version once and mo...

Full text and comments »

How to Effectively Practice CP + Problem Solving Guide This is a slight tweak of [a practice guide](https://www.reddit.com/r/usaco/comments/pk3tjp/the_ultimate_usaco_practice_method/) I wrote a while ago on USACO reddit since I thought it could be helpful to people here. Some USACO specific sections or extra clutter I left out here that aren't needed for a general audience. This should cover all general cp advice I have so I never have to retype. #Introduction This is a post on how I believe is the best method to practice modern day competitive programming based on my experiences. I assume you already have some knowledge and know simple things like binary search and dfs/bfs, but **read the footnote if you are complete beginner** (never code, solved <50 problems, div2 A/B too difficult, grey or stuck low pupil). First, a quick tl;dr of the practice strategy before a bunch of specifics and explanation: >**In short, mostly you only need to use codeforces (no matter what contest you're training for), find a rating range where you c...

Full text and comments »

F.A.Q. (in PM) Q1: I'm a newbie. What should I do to become great coder? A1: <s>Stop doing competetive programming</s> Solve problems. Q2: I'm doing CP for two months and I'm still <s>not red</s> green. What should I do? A2: <s>You are lazy and impatient</s> Solve more problems. Q3: You became a red in less than two years, it is unbelievable! A3: No, it isn't. <s>You can do it too if you will solve fucking problems.</s> Q4: You became a red blah-blah-blah such a huge fan blah-blah. Oh, and what should I do to become as great as you? A4: ... right. You already know the answer. Solve problems. <s>I hate you.</s> Q5: I'm not good at DP [or something]. What can you suggest? A5. Maybe you should try to <s>stop asking stupid questions and</s> solve some problems on DP? Or read some blogs and editorials. Q6: I can't solve a problem / understand your code. Can you help me? (Well, it is not a bad question in general. It is a good (if you really want me to explain something not...

Full text and comments »

Сompetitive programming tutoring – help me fulfil my dream Hi, everyone! My name is Aleksandr Mokin. I've been teaching competitive programming for 3 years as my main job. I was a winner of the All-Russian Olympiad in Informatics in 2012, an awardee in 2011 and 2013. In 2018 I became a finalist of the ICPC world programming championship. In 2019 I started teaching and have helped dozens of people to make progress and reach their goals ([see people's feedback](https://profi.ru/profile/MokinAB/)). Since then I've developed my own approach. I don't just guide people through notorious algorithms, but also teach concrete techniques on how to solve real problems and quickly write a working code. Now I've decided to try bringing it to another level. I want to reach the worldwide audience: feel free contacting me on [Facebook](https://www.facebook.com/rembocoder/), [Telegram](https://t.me/rembocoder), private messages or e-mail: [[email protected]](mailto:[email protected]). My base rate is **$50/h**. If I get enough feedback, I p...

Full text and comments »

Refact.ai Match 1 (Codeforces Round 985, Div. 1 + Div. 2) Hello, Codeforces! We (KDOI Team) are glad to invite you to take part in [contest:2029], which is the 8th CP contest held by us! You can view the previous rounds by us [here](/blog/entry/135847). - Number of problems: $9$ ($0$ interactive); - Start time: [contest_time:2029]; - Contest duration: $180$ minutes; - Score distribution: $750-1250-1750-2250-2500-3000-3500-5000-5500$. The problems were authored and prepared by [user:Error_Yuan,2024-11-05], [user:wyrqwq,2024-11-05], [user:Otomachi_Una,2024-11-05] and me [user:sszcdjr,2024-11-05]. --- <img src="/predownloaded/73/e1/73e1593107761ee6b925164110aa7307488b2215.png" style="float:right; margin: 0 0 2em 2em; width:300px;"/> A few words from our sponsor: We’re [Refact.ai](https://refact.ai/?utm_source=codeforces&utm_medium=post&utm_campaign=round_09112024&utm_content=cf_short_09112024), an open-source AI Coding Assistant, and on November 9th, we’ll be hosting our first round on Codeforces! Winners will receive ...

Full text and comments »

[Tutorial] Generating Functions in Competitive Programming (Part 2) Welcome to Part 2 of my tutorial on generating functions. The [first part](https://codeforces.me/blog/entry/77468) focused on introducing generating functions to those without any background in generating functions. In this post, I will demonstrate a few applications of generating functions in CP problems. Let us start with some relatively straightforward examples. Note: Unless stated otherwise, all computations are done modulo a convenient prime (usually $998244353$). Also, $[n]$ denotes the set $\\{1,2,...,n\\}$. ### Blatant Applications in Counting Problems **Problem.** [AGC 005 Problem F](https://atcoder.jp/contests/agc005/tasks/agc005_f) You have a tree $T$ with $n$ vertices. For a subset $S$ of vertices, let $f(S)$ denote the minimum number of vertices in a subtree of $T$ which contains all vertices in $S$. For all $1 \le k \le n$, find the sum of $f(S)$ over all subsets $S$ with $|S| = k$. Constraints: $n \le 2 \cdot 10^{5}$. <spoiler summary="Solution"> First, ...

Full text and comments »

[Tutorial] Graph Potentials, Johnson's Algorithm, and Min Cost Max Flow In this tutorial I'll introduce potentials as it applies to directed graphs and discuss a few of its applications. I haven't seen many resources about this topic, so I decided to write one. Prerequisites: - Shortest path algorithms ([Dijkstra](https://cp-algorithms.com/graph/dijkstra.html) and [Bellman-Ford](https://cp-algorithms.com/graph/bellman_ford.html)) - For the Min Cost Max Flow section, you should be familiar with [Ford-Fulkerson](https://cp-algorithms.com/graph/edmonds_karp.html). But you can benefit from this blog with just the Johnson's Algorithm section if you're not familiar with flows. Introduction ------------------ For notation, let's say there is a weighted, directed graph $G=(V,E)$. Let $n=|V|$ and $m=|E|$. For simplicity, let's assume there are no loops or multiple edges between the same pair of nodes in the same direction. For an edge $u\to v$, we will use $w(u\to v)$ to denote its weight. Let's motivate the idea of a potential, so the definition d...

Full text and comments »

What to be careful about when submitting your problems to other contests This is a story about my recent contest participation. Let's call the contest X. X was an international contest with online qualification rounds and the onsite Finals, with trip and hotel expenses covered by the organizer. In other words, X was a very important contest for me. Hoping to go to the Finals, I participated in the qualification round. However, when I opened the last problem, I immediately remembered that the exact same problem had previously been submitted to AtCoder. I also knew that the submitter of that problem was among the organizers of X. Let's call the author of that problem Y. I immediately messaged Y about this issue. At first, I thought that Y had simply forgotten that he had submitted the problem to me, but the situation was a bit more complicated. Y _did_ remember he had submitted the problem to me but still used it in another contest. Why? Because I had given him permission! To make things clear, let me show you the relevant chat log betw...

Full text and comments »

Introducing cp-notes.com — a place for your interesting competitive programming problems! **Update in 2025:** I've mostly forgotten about this site, but recently something rather funny came up: I was looking for a way to get a relatively large number of free subdomains (name of the url not mattering at all), when I realized I was still paying for cp-notes.com. So I tried to login to the AWS account owning the domain (which I haven't done in years), but it prompted me to check the email associated with it for a verification code... Unfortunately, I had used my Columbia university email out of convenience, but that has been disabled! (which I suspect has something to do with me dropping out?) I actually can still update the website (not that I was planning to) since I have some keypair saved which allows programmatic access, but not being able to use the console is a huge pain. I could also contact AWS support, but I feel like that would take a while... Anyways, it is time for me to express some of my frustrations: Fuck Columbia University! In addition to disabling my emai...

Full text and comments »

[IOI 2025] Travel Log: 68 Hours, 0 Luck, 1 Chicken Dear CP and IOI community, This is my first time leading the team at the IOI! However, after this experience, I will be having a long, hard look in the mirror before ever considering it again. TL;DR: Every single step went wrong — even the ones you thought _couldn't_. Part of the Serbian team (two contestants and a guest) was traveling with me, while the rest traveled separately with the deputy, due to a training camp. Failing before even departing ----------------------------- Our intended route was: Belgrade → Zurich → São Paulo → Santa Cruz, followed by a separate domestic flight to Sucre. We planned to depart on the 26th and arrive on the 27th. However, a major storm hit Europe that day, and many flights to/from Zurich were delayed — including ours. Because of that delay, we missed our connection to São Paulo, and consequently all following flights. _The other part of the delegation did not have this problem._ Logistic problems ----------------- We were re...

Full text and comments »

Finding all primes up to half a billion in 83 ms Hi everyone! I was itching to apply SIMD in another problem, and this time my attention picked the following problem: --- **[Library Checker &mdash; Enumerate Primes](https://judge.yosupo.jp/problem/enumerate_primes)**. You are given $N$, $A$ and $B$. Find $\pi(N)$, and print all $p_{kA + B} \leq N$. It is guaranteed that $N \leq 5 \cdot 10^8$ and that the total number of primes to print is at most $10^6$. --- After some tweaking, I managed ([#336744](https://judge.yosupo.jp/submission/336744)) to reduce my time consumption in this problem to **83 ms** and memory consumption to **25 MiB**, which makes it a top-1 submission on the Library Checker. For comparison, the top-2 solution ([#148169](https://judge.yosupo.jp/submission/148169)) takes 172 ms and 15 MiB, meaning that what I describe here is a 2x improvement in terms of the running time. We can also compare it to what appears to be the state of the art of sieving, the [primesieve](https://github.com/kimwalisch/...

Full text and comments »

How to ask for help in PM There was a blog today with a similar title, and although it was (I think, not really sure as I didn't get a good look) some kind of satire/joke blog, I wanted to post some serious advice about things I (don't) like to see when people are PMing me. However I decided that this wouldn't be in the spirit of the blog and decided to make a separate blog. And now that blog is deleted anyway. While it's not a bad thing to write messages to more experienced users, most people who write me do things that make them very difficult to deal with. These are my opinions, but somewhy I feel that many reds will agree. Some things here feel silly to write because they are so obvious. But I'm only writing them because people regularly mess them up. [cut] $~$ ####Use punctuation and spelling. There are some [very simple rules](https://codeforces.me/blog/entry/82186#comment-689836) that make your messages infinitely more readable. I find it especially strange when many of these messagers call...

Full text and comments »

CP-Algorithms: Discord server, donation campaign and more Hi everyone! <img src="/predownloaded/82/15/821540e8f87d8a2b2d468377aacbba80b0aa1623.png" style="float:right;" width=100px> It was a while since I [posted](https://codeforces.me/blog/entry/135081) last update about **[CP-Algorithms](https://cp-algorithms.com)**. As a general reminder, it is a community project that [started off](https://codeforces.me/blog/entry/13198) in 2014 by [user:RodionGork,2025-08-23] as a translation of [e-maxx](http://e-maxx.ru/), a Russian go-to resource at the time by [user:e-maxx,2025-08-23] for learning core competitive programming algorithms. Since then, CP-Algorithms grew quite a lot (which also prompted a rename from original project name `e-maxx-eng`) and includes a lot of new, original articles, and a lot of translated articles were enhanced and/or extended or even completely rewritten. In this blog, I would like to share a bunch of updates about the site, to make sure it's still in the collective memory &#128517; ### New maintainers ...

Full text and comments »

Rumination on AI and competitive programming An OpenAI model can now achieve a rating of 1800 in Codeforces. That made me wonder about the future of competitive programming and why we do this. I came up with some opinions, which I'll be glad to share with you. ## AI killed the competitive programming? I don't think that's happening, because competitive programming is useless! Some people might think CP is less interesting because AI can solve CP problems &mdash; but come on, problemsetter can solve those problems, unless they are really bad. Many people still play Chess just fine, and I recently enjoyed participating in Sudoku competitions, although I was completely aware that computers would wreck me in a second. It didn't matter, and I didn't see how it could. CP problems are not "open problems" &mdash; if they are, the problemsetters are to blame. So, you are not contributing anything to the world by solving CP problems; it all comes down to personal interest. As long as CP is fun for people, they will do it. ## Flag...

Full text and comments »

Problem Database - Idea for a CP-related project I can sometimes see people doing some CP-related projects for their courses/portfolio/community, and I want to suggest an idea of such a project that would benefit me as a CodeChef Admin and all the problemsetters, I believe. Issue: There are a lot of problems on different platforms, and it is really hard to check if some problem was already used somewhere or not. Sometimes googling works, but most of the time I have to rely on my own experience and memory, which are far from perfect. It's hard to search for problems, because they usually have some kind of story, and the same problem can be formulated in a lot of different ways. Proposed solution: Create some kind of smart database, that will collect the problems from all known sources and will have some very smart search engine that would focus on the internal meaning of the problem, instead of how it is formulated. I have no idea how to do any of that :) I would assume that it would require some kind of very smart ML and a l...

Full text and comments »

Codeforces Month of Blog Posts (win $300) **TL;DR:** Write an interesting CodeForces blog post until February 15th and win $300. **UPD: Second place will receive $50.** **UPD2: Competition is over, The results are available [here](https://codeforces.me/blog/entry/113041).** I am a huge fan of CodeForces and specifically CodeForces blog posts! There are tens and hundreds of gems posted on this platform throughout the years. Thankfully, recently there was added the [catalog](https://codeforces.me/catalog) page where a lot of cool articles can be found. Personally, if I want to remember some classical algorithm, I would go to websites like [cp-algorithms](https://cp-algorithms.com/), but CodeForces is the place where new or rare stuff is born, where new points of view emerge. I think it is one of the most valuable functions of this website, and I would like to facilitate its growth. I know that many people have cool ideas in their minds that they came up with or maybe something that is known only in their community on ...

Full text and comments »

IICPC Global Codefest 2026 Hello! Registrations for IICPC Global Codefest 2026 are opening soon. This is the first global edition of India's largest offline competitive programming competition. **About IICPC Codefest** IICPC (Intercollegiate Informatic and Competitive Programming Camp) is an academic and industry-backed organization focused on identifying, evaluating, and nurturing high-potential students in competitive programming, algorithms, and computer science fundamentals through rigorously designed, large-scale competitive examinations and camps. We organize Codefest, a multi-stage competitive programming competition conducted across India. This year, we are opening participation to international students from 50+ countries. **The prelims is individual participation, and online for international students. The deadline for registration is 15th January, 23:59 IST**. <img src="https://i.ibb.co/bRJt7y44/codefest-banner.png" height="50"> **Competition Structure** Prelims &mdash; Janua...

Full text and comments »

AI might erase CP, but not us I haven't slept for 20 hours and I can't fall asleep. I've been reading others' topics on AI, and I had a sort of epiphany. These ideas have been brewing inside me for many years, and I thought it might be time to share them with the community. --- There were times when I was a "competitive programmer" at the core. I spent many years doing that exclusively. I've never been to IOI, but I like to think that I've reached some good heights. Two years ago, I stopped writing online competitions. I've written a few offline competitions after that, but eventually, I decided to stop that too. Yet somehow Codeforces still attracts me. I don't want to solve problems, but I keep typing codeforces.com into the address bar. *Why?* Just yesterday, I didn't have an answer. --- Imagine a layperson asking you what competitive programming is. What are you going to say? My answer has always been "Oh, we solve interesting algorithmic problems with time constraints and other limits". Many ...

Full text and comments »

Confession: I sent problem H to goodbye Going to be 100% honest here, I sent problem H to goodbye. I feel really bad to authors of Goodbye 2023 for ruining their round, it seems the round would have been better by just removing H. As much as the community is out here roasting [user:74TrAkToR,2023-12-31], I also had a part to play in this contest. I wish to be as transparent as I can here without saying any classified information (apologies to [user:KAN,2023-12-31] and [user:74TrAkToR,2023-12-31] if anything here shouldn't be disclosed). To give some context, here is what went down in goodbye round from my perspective: - 13 days before contest: KAN asks me if I can source a 1E for goodbye. I asked traktor to send me the testing gym so that I could gauge how hard the 1E should be. He told me he will send me after he translates the statements. (UPD: Note that the IMO 1986 problem was already removed before this stage which is why a new 1E was needed, I never saw this IMO problem) - 11 days before contest: traktor send it...

Full text and comments »

CP Series *This is my first blog post and it's not a tutorial. Pls don't hit me.* CP Series ================== One beautiful day, I decided to draw a comic series related to competitive programming for my friends on a whim. It is mainly about dumb stuff that I remember happened during my competitive programming journey in college. On another beautiful day, I acquired the idea of making this post.  ### Motivation Here are some reasons for why I decided to draw this. *I absolutely have to write this for self-justification and so that when I lose motivation, I can read this and regain my motivation, producing a never-ending loop.* 1. I like drawing. Actually, it's a love-hate relationship. 2. Initially, this is intended to be a joke, but somehow some of my friends are genuinely looking forward to it. They told me it's funny *smh*. So, I'll at least continue it until I run out of ideas. 3. *I want to be able...

Full text and comments »

On "is this greedy or DP", forcing and rubber bands #### Introduction When it comes to "problem-solving techniques", there are roughly 3 levels: 1. Concrete algorithms (Kruskal's algorithm, Li-Chao tree, fast Fourier transform) 2. General patterns (dynamic programming, greedy, square-root decomposition) 3. Meta-strategies ("how do I even go about solving this problem?") There is some grey area, but in general this classification works well. [Many tutorials](https://codeforces.me/catalog) have been written about ideas that fall into 1 or 2. But very little has been written about the third category. On the catalog, I think the only blogs that really qualify are [this](62730) and [this](20548). There is also [this](92248?#comment-809401) valuable comment. As to why there is so little written, I think I can identify two reasons. - Most strong contestants don't really consciously think about these. After solving a problem with FFT, it's hard not to know you used FFT. If you used DP, even if you did it without thinki...

Full text and comments »

Bitwise operations 2 — popcount & bitsets Part 1 ([link](https://codeforces.me/blog/entry/73490)) introduces basic bitwise operations. This is part 2 and it's mainly about (in)famous bitsets and example problems. Also, see links to very useful advanced stuff at the bottom. EDIT: here's [video version](https://www.youtube.com/watch?v=jqJ5s077OKo&list=PLl0KD3g-oDOHpWRyyGBUJ9jmul0lUOD80) of this blog (on my Youtube channel). ### Built-in functions In C++, `__builtin_popcount(x)` returns popcount of a number &mdash; the number of ones in the binary representation of $x$. Use `__builtin_popcountll(x)` for long longs. There are also `__builtin_clz` and `__builtin_ctz` (and their long long versions) for counting the number of leading or trailing zeros in a **positive** number. Read more [here](https://www.geeksforgeeks.org/builtin-functions-gcc-compiler/). Now, try to solve these two simple tasks in $O(1)$, then open the spoiler to check the solution: <spoiler summary="Compute the biggest power of 2 that is a divisor o...

Full text and comments »

FAQ, Advice & AMA This post assumes you're super ambitious. But don't take any advice too seriously -- we're all different. This is simply what worked for me and might work for you. Choose your own path. #### Useful Links - [LI2 Contests](https://codeforces.me/blog/entry/131164) -- used this course when I was starting out. - [usaco.guide](usaco.guide) -- a collection of great articles & problems on almost all topics. - [OI Checklist](https://docs.google.com/spreadsheets/d/15b1ZaP1owTfTcA4vQ69A5S_wUd_vJmM8Slwu6FiWgP4/edit?usp=sharing) -- my OI Checklist. - [Pavel Mavrin's youtube channel](https://www.youtube.com/channel/UC9WDkCyUlNTncq1Y-mFSgLQ) -- watched his great lectures when I was younger :) - [qoj.ac](qoj.ac), [loj.ac](loj.ac), [dmoj.ca](dmoj.ca), [oj.uz](dmoj.ca), ... #### How do I start? **Advice:** join a great community (school, club, ...), try solving problems, and find someone who can answer your silly questions. I wouldn't have started CP if not for my school. Of c...

Full text and comments »

All You Need is Randomly Guessing — How to Improve at Codeforces I hope [my previous blog](https://codeforces.me/blog/entry/126310) has convinced you that the best way to improve at Codeforces is to be more Russian, i.e. to improve your math capability. Unfortunately, humble mortals such as you and I are not gifted with the talent that esteemed Russian grandmasters such as 74TrAkToR had: _Surely, it is beneficial to have a code reference for many algorithms and data structures, but I also think that just superficially knowing the algorithm and maybe having implemented it once or twice before is sufficient to use it without a reference?_ _&mdash; Some other Codeforces grandmaster_ Therefore, in this blog I will explore the dark side of Russian-ness &mdash; randomly guessing &mdash; that is forsaken by every Russian grandmaster of the light side I know. However, it has been very helpful to me, and I hope that it serves you well, too. ## Example 1 I will start by using an example to demonstrate my thought process. This problem [1923C](h...

Full text and comments »

Caveats of using optimize("Ofast") with target("avx2") Hi everyone! As you may know, it is often recommended to put these lines in your header: ```cpp #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2") ``` And they're usually great!^[1] Well, until they aren't. For last 2-3 days I was riddled with the issue that [CP-Algorithms Library](https://lib.cp-algorithms.com) would perform very well on Library Checker, but whenever I tried to also apply it on Codeforces, it will fail to speed up the code, and sometimes would even make it much slower. As I finally figured out the cause, I'd like to write a blog about it, so that other people don't waste as much time. Mitigating these issues improved my running time on [problem:1975G] from **1530 ms** in [submission:316602668] to **203 ms** in [submission:352602775]. ##### Tl'dr See the "Takeaway" section at the bottom. [cut]<br> ##### Example problem I will reproduce the issue on a simple example: <hr> **[problem:911G]**: You are given an...

Full text and comments »

My Summer CP School, rating 1000-2200 Hi, I'm going to teach competitive programming classes this Summer, starting with a 4-week batch to see how it goes. I hope to make 2 or 3 groups of ~12 students, each group aimed at some CF rating. We will use problems from Codeforces, CSES, Atcoder, Polish olympiad (only higher group), and my modifications and follow-ups. There will be homework, some to be discussed next lesson. - Dates: June 24 to July 19 (4 weeks) - Time: morning-noon in Europe - 2-3 lessons per week, 1.5h or 2h each - Price: around 20 USD per hour, 260-440 USD total per person - Platform: Discord and/or Google Meet Please fill [this form](https://forms.gle/v1q7qZKU1YnNWRbaA) to get a 5% early-bird discount. I will use the results to choose and announce groups (difficulty and frequency) in 1-2 weeks. Feel free to ask questions in the comments, or DM me. <spoiler summary="regarding the idea of USACO classes"> I already mentioned [here](https://codeforces.me/blog/entry/129009) my plan to do USAC...

Full text and comments »

Efficient linear algebra for dummies Hi everyone! Some time ago I started developing a linear algebra library for Library Checker, and it turned out to be much fun. I'd like to write this blog to outline how one can implement a linalg library with a very good Library Checker performance, while also avoiding highly technical low-level details that are common in other similar blogs. Instead, we will learn a few high level ideas that will let us write a code that the compiler will then optimize using all these fancy techniques _in our stead_. Huge thanks to ~ToxicPie9,2024-05-08 and [user:magnus.hegdahl,2024-05-08] for explaining me some of the optimizations used here! You may also look into ~sslotin,2024-05-08's [entry](https://codeforces.me/blog/entry/101655) about how it can be sped up even further with more advanced and low-level techniques. ### Tl'dr. In this blog, I present my [matrix library](https://cp-algorithms.github.io/cp-algorithms-aux/cp-algo/linalg/matrix.hpp), which maintains a simple and elegant...

Full text and comments »

CP mentoring for charity Motivation ------------------ Many people in the CP community are truly concerned about the war in Ukraine. Rightly so, it is currently affecting millions. Regardless of how many political discussions are held here, they don't really change that much. Let's try to address genuine human suffering instead. CP mentoring for charity ------------------ I would like to host a couple of 1-hour CP mentoring sessions this Saturday. The prerequisite for attending one is donating at least 20$ to any charity supporting victims of the war. Of course, you are more than welcome to donate more. If you think this is something for you, sign up for one of the six slots via this Doodle link: https://doodle.com/meeting/participate/id/ZdP68j6a The slot **should** disappear after it is chosen by one person. But I have never used Doodle as a booking management system before, so I don't guarantee that everything will work as planned... we'll sort it out :) Please donate only **after** y...

Full text and comments »

Implementing Dinitz on bipartite graphs Hi everyone! if you read about [Dinic algorithm](https://cp-algorithms.com/graph/dinic.html) on CP-Algorithms, especially the [section](https://cp-algorithms.com/graph/dinic.html#unit-networks) about how it works on unit networks, you'll notice that its supposed runtime for bipartite matching is $O(E \sqrt V)$, where $E$ is the total number of edges, and $V$ is the total number of vertices of a bipartite graph. Let's try it out on the following problem: **[Library Checker &mdash; matching on Bipartite Graph](https://judge.yosupo.jp/problem/bipartitematching)**. Given a bipartite graph with $V, E \leq 2 \cdot 10^5$, find the maximum matching. The implementation of the Dinitz algorithm that I typically use looks as follows: <spoiler summary="code"> ```cpp struct unit_network { int n; vector<int> to, cap; vector<vector<int>> g; unit_network(int n): n(n), g(n) {} void add_edge(int a, int b, int cp) { g[a].push_back(size(to)); ...

Full text and comments »

Osijek Competitive Programming Camp 2023 winter Hi everyone! <center><a href="https://ocpc.mathos.unios.hr/index.php"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a></center> I am happy to announce the [Osijek Competitive Programming Camp](https://ocpc.mathos.unios.hr) that is scheduled to happen on **18-26 February 2023** in Osijek, Croatia. The camp is hosted by the [Department of Mathematics at J. J. Strossmayer University of Osijek](https://www.mathos.unios.hr/index.php/en/) and is brought to you by the organizing team of [user:adamant,2022-12-21] (that's me!), [user:-is-this-fft-,2023-01-06], [user:mblazev,2023-01-06], [user:Tomx,2023-01-06] and [user:antontrygubO_o,2023-01-05]. The camp is inspired by various competitive programming camps that we attended during our active years in ICPC, and is aimed to help college students prepare for ICPC regional contests and finals. The camp will consist of 7 ICPC-style contests and 2 days off. Up until now, most top competitive programming training...

Full text and comments »

Let's stop making anti-GPT problems? There seems to be a general trend of problem-setters going out of their way to ensure that their problems aren't solvable by AI. This obviously restricts the meta to the kinds of problems that AI is bad at: which, in practice seem to primarily be ad-hoc problems that require multiple observations. This approach doesn't always (and in my opinion, rarely) yield the most enjoyable/natural problems to humans. The only motivation for this tendency is to ensure that CF ratings and leaderboards in contests retain some meaning. What I want to express from this blog: **I think we should stop intentionally making anti-GPT problems and optimize problem-setting for human enjoyment, with a complete disregard for how AI models (and people using said models to cheat) perform on these problems.** I will try to explain why I think so below. There are only two ways (distinct in their relevance to CP) in which AI gets better in the future: <ol> <li> It becomes smarter than humans a...

Full text and comments »

[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges #### Introduction This is a tutorial/exploration of problems that can be solved using the "DFS tree" of a graph. For a way too long time, I didn't really understand how and why the classical algorithm for finding bridges works. It felt like many tutorials didn't really explain how it works, kind of just mentioned it in passing and quickly just moved on to implementation. The day someone explained what the DFS tree is, I finally understood it properly. Before, it took me ages to implement bridge-finding properly, and I always had to look up some detail. Now I can implement it at typing speed. But more importantly, I began to see how the same techniques can be used to solve graph problems that have more or less nothing to do with bridges. The thing is, when you have a black box, you can only ever use it as a black box. But if you have a box that you understand well, you can take it into pieces, repurpose the pieces for completely different things, all without getting lost...

Full text and comments »

crazySegmentTree: Segment Tree implementation with 5x faster queries than bottom-up tree Hello, Codeforces! A few days ago [user:MohammadParsaElahimanesh,2021-04-06] posted a blog titled [Can we find each Required node in segment tree in O(1)?](https://codeforces.me/blog/entry/89377) Apparently what they meant was to find each node in $\mathcal{O}(ans)$, according to [ecnerwala's explanation](https://codeforces.me/blog/entry/89377?#comment-777885). But I was too dumb to realize that and accidentally invented a parallel node resolution method instead, which speeds up segment tree a lot. A benchmark for you first, with 30 million RMQ on a 32-bit integer array of 17 million elements. It was run in custom test on Codeforces on Apr 6, 2021. - **Classic implementation from cp-algorithms:** 7.765 seconds, or 260 ns per query - **Optimized classic implementation:** (which I was taught) 4.452 seconds, or 150 ns per query (75% faster than classic) - **Bottom-up implementation:** 1.914 seconds, or 64 ns per query (133% faster than optimized) - **Novel parallel implement...

Full text and comments »

Heuristic algorithm for Hamiltonian path in directed graphs (It's a translated version of my blog at https://peehs-moorhsum.blog.uoj.ac/blog/6384. ) Finding a Hamiltonian path in a directed graph is a well-known NP problem. However, about a year ago, I came up with the following heuristic algorithm which has GREAT performance on random graphs(by first generating a hamiltonian path, adding random edges, then randomly permuting indices) and many CP problems. Here is the idea of the algorithm: We maintain a subset $S$ of edges, ensuring there's no cycle and each vertex has in-degree and out-degree at most 1. Whenever $|S|$ reaches $n-1$, we find a hamiltonian path. We start with $S$ empty. Each time we pick a random edge $e \notin S$. If we can add $e$ to $S$ without violating any rule, we simply add it to $S$. Otherwise, if $e$ won't create a cycle and violate with exactly one edge e', we replace e' with $e$ with 50% probability. Repeat until $|S|$ reaches $n-1$. We can use LCT to check cycles. Here's my code, which takes le...

Full text and comments »

August Classes & Huawei IOI Camp 2024 Hello, everybody. <spoiler summary="August CP School, cancelled"> August CP School ---------------- I'm again organizing group classes after trying the format [last month](https://codeforces.me/blog/entry/129878). There will be problem-solving, homework, and recordings. I can make a lecture on some topic per requests. There will be two groups. You can attend both, just don't spoil anything in the lower group. (Btw. I also want to do 3-month weekly classes after Summer.) 1. Medium group: [16:00-17:30 CEST](https://www.timeanddate.com/worldclock/fixedtime.html?iso=20240808T16&p1=262&ah=1&am=30), 90-minute lessons, CF max rating 1500-1800 2. Hard group: [18:00-20:00 CEST](https://www.timeanddate.com/worldclock/fixedtime.html?iso=20240808T18&p1=262&ah=2), 2-hour lessons, CF max rating 1900-2200 - Dates: August 8 to 26 or 29 (6 meetings in total) - Every Monday and Thursday - Price: 200 USD per person (so around 20$ per hour, or 13$ if you're going to attend both groups)...

Full text and comments »

PSA on Meta Hacker Cup (must read if its your first time!) Meta Hacker Cup is upon us again. Along with it comes the unique format where we have to run our code on large test cases ourselves. Unfortunately, past experience shows that not everyone knows how to do this reliably. Usually, after the first round, many people lose points as a result of an unreliable workflow. This time, let's try to prevent that from happening. Sorry for the somewhat self-important title, but I really do wish that everyone understood this and that no one will fail the contest because of this. ### Don't EVER copy-paste huge files A lot of people's workflow to run a solution is the following: - Click some green button in the IDE - A box comes up, copy-paste the input into that box - The output shows up somewhere This may work well for running your solution on small sample test cases. It is **terrible** for running your solution on the huge test cases in Meta Hacker Cup. In last year's Round 1, the full test case for [problem C](https://www.facebook.com...

Full text and comments »

The very first red LLM cheater? Let me introduce you to [user:lequoctran181,2025-04-06] a.k.a Lê Trần Quốc Anh, a shining star in the competitive programming community from National Economics University, Hanoi. He is a philosopher who talks about CP-ing quite a lot on his Facebook page, sharing tips, talking about his journey, etc...    I admit, he is skilled, but not at cp, but at cheating. The first time I paid attention to this account was in December of 2024, where he had 2 different templates, submitting C and D only around 10 minutes apart from each other, and achieving rank 35 on [contest:2042], notice how he didn't space down, and the different way of naming variables:   Now, after this "achievement", of course, he would be very proud, as seen bragging about it here on the blog post of the round: ![ ](h...

Full text and comments »

Petition to Restrict the Coach Mode Authority Tighter Happy New year, Codeforces. I had this idea for about a month. I heard problem setters complaining about some people used their coach mode authority to enlarge some problems' TL in the Gym just for letting their submissions passed. What's worse, these guys even forgot to change it back, which causes some troubles for participants afterwards. Moreover, I also have similar experience. Back in 2020, I did [SWERC2019](https://codeforces.me/gym/102501/) with my friends. Then after a few days, I returned and found that my competition record disappeared from the scoreboard. Someone must press the 'to practice' or 'devirtualize' button. If you press those buttons, the website will ask you if you confirm your action (which is not reversible). Therefore, I pretty sure there is someone who just don't want to see my partipation record on the scoreboard for some reasons that I could never realize. Just in case some of you don't know (maybe hasn't discovered yet) what the coach mode can do...

Full text and comments »

[Tutorial] Supporting Priority-Queue-like Undoing on DS _Good morning!_ In this blog, I will present an online algorithm that can perform priority-queue-like undoing on a data structure, given a few assumptions. I will also present and solve a generalization of that problem. For context, I highly recommend reading this blog that shows how to solve the easier problem of queue-like undoing. That blog gave me the inspiration for the trick I will describe here, but I will still try to write this blog so that it can be understood without it. Thank you [user:Noam527,2023-01-08] for introducing such a great trick to the competitive programming community. [[Tutorial] Supporting Queue-like Undoing on DS](https://codeforces.me/blog/entry/83467) Acknowledgment ----------------- Huge thanks go to [user:peltorator,2023-02-20] for hosting a [blog contest](https://codeforces.me/blog/entry/110840). His generous prize of $300 got many people to write blogs on new, interesting ideas, and it was one of the main reasons I wrote this blog. I'm...

Full text and comments »

e-maxx-eng/cp-algorithms update + free shirts from Hacktoberfest 2018 I hope most of you know your project [**e-maxx-eng**](https://cp-algorithms.com/). If you heard about it the first time: there is this really awesome Russian website ([link](http://e-maxx.ru/algo/)) about algorithms used in competitive programming by [user:e-maxx,2018-10-02]. **e-maxx-eng** is a community project that translates the material, so that competitive coder from all around the world can read and learn from the incredible useful and detailed source. Currently we have a pretty good and huge number of articles about algorithms, data structure, their implementation, lots of applications and general useful tips. Here's a quick updates on what we achieved in the last year: * There are translations available to over 100 articles (about 71% of all articles). Last year it was only about 45%. * We published a couple of original articles (e.g. about the [Sqrt Tree](https://cp-algorithms.com/data_structures/sqrt-tree.html), [Convex hull trick and Li Chao tree](https://cp-algorith...

Full text and comments »

My CP Course "Zero to Hero" is now open for pre-registration! Having had a ton of experience with CP, I have decided that I could share my knowledge the best with the world by making a course! This course currently has lessons designed for people of many levels, from newbies to low masters. Currently, I have opened pre-registration. I'm currently just trying to get an idea of how many people would be interested in such a course (and also to catch possible bugs on the website). Here is the course website: http://course.williamlin.io/ 100 lucky winners who pre-register will be given beta access to the course for free! Pre-registration won't be open for long though, so be sure to do it quick! **Update:** Thanks to every who pre-registered! The pre-registration assessment proved to be tough, and we decided to offer spots for beta access even for those who did not pass the test! Look out for an email from [email protected] for your decision letter, as well as solutions and more opportunities to gain beta access to the course! **Up...

Full text and comments »

Codeforces Round #538 (Div. 2) **TREMBLE BEFORE THE MIGHTY OMEGALULGRAPE**  Hello Codeforces! We are honored to invite you to Codeforces Round #538 (Div. 2), which will take place at [contest_time:1114]. The round will be rated for all Division 2 participants **(with rating less than 2100)**. Still, we warmly welcome Division 1 participants to join us out of competition. You will be given **6** problems to solve in **2 hours.** The round's problems were initially prepared by Duy-Bach ~Akikaze,2019-02-05 Le, Xuan-Tung ~neko_nyaa,2019-02-05 Nguyen and Xuan-Quang ~xuanquang1999,2019-02-05 D. Nguyen. **There will be an interactive problem in this round.** Learn more about interactive problems [here](https://codeforces.me/blog/entry/45307). This is our first attempt in making a Codeforces round, so suggestions are much welcome to help us improve ourselves. ;) We also want to thanks many friends for making this round possible: - Dmitry ~_kun_,2019-02-05 Sayutin...

Full text and comments »

Educational Codeforces Round 104 Editorial [problem:1487A] Idea: [user:BledDest,2021-02-16] <spoiler summary="Tutorial"> [tutorial:1487A] </spoiler> <spoiler summary="Solution (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (int& x : a) cin >> x; cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl; } } ~~~~~ </spoiler> [problem:1487B] Idea: [user:adedalic,2021-02-16] <spoiler summary="Tutorial"> [tutorial:1487B] </spoiler> <spoiler summary="Solution (adedalic)"> ~~~~~ fun main() { repeat(readLine()!!.toInt()) { var (n, k) = readLine()!!.split(' ').map { it.toInt() } k-- val floor = n / 2 println((k + (n % 2) * k / floor) % n + 1) } } ~~~~~ </spoiler> [problem:1487C] Idea: [user:BledDest,2021-02-16] <spoiler summary="Tutorial"> [tutorial:1487C] </spoiler> <spoiler...

Full text and comments »

CP trainer — a new tool for training Hello, <br/> I created a project for training and analyzing your performance during contests: [cp-trainer.com](https://cp-trainer.com). I believe it has some unique features non-existent in competitive platforms and can provide as a more sensible tool for training, especially for more experienced users, who have participated already in a bunch of contests. Below I will briefly discuss its functionalities: Problem recommender ------------------ In this section, we will discuss the heuristics used for problem recommender, the system offers for the user 10 problems with the highest value of this heuristics. First we need to introduce a couple of metrics: <ul> <li> <b> get_dict_accuracy </b> — Dictionary of form (<b>tag</b> : average number of submissions to accept problem with this tag during contest) </li> <li> <b> ratings_average_time_diffs </b> — Dictionary of form (<b>rating</b> : average time in seconds to solve the problem with this rating during contest) </li> <li...

Full text and comments »

LOVE BABBAR and ANUJ BHAIYA Exposed!!! Lets first give the introduction of these two **DUMBOS**. **BABBAR:** Runs a YouTube channel having 300K+ subscribers **ANUJ BHAIYA:** Runs a YouTube channel having 170k+ subs. **Who am I?** _Ans_: I am also among one of the YouTubers who belong to the company Amazon. **Why am I writing this post?** _Ans_: I am wanting to clear the misconception that they have spread about the company, and how they are misusing there wrong doings to wrongly influence people to do wrong tasks. **Background**: Recently Babbar posted that he will be resigning Amazon. Next Anuj posts that Amazon asked him to choose YouTube or Amazon, and he makes a video that he left Amazon for students. The moment Anuj released the video, Babbar felt he will loose out on fame, so within an hour, he posted on Linkedin that he also stood with 3L students over Amazon. The screenshots of these things are below..  ![ ]...

Full text and comments »

[Contest] Statement Not Found: Season 2 #### Do you think you can solve CP problems without reading the problem statements? Let's find out! On [August 28, 2022 (Sunday) 19:30-22:00 GMT+8](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Statement+Not+Found+-+Season+2&iso=20220828T1930&p1=122&ah=2&am=30), I will hold an unofficial fun contest called Statement Not Found. As you can deduce from the title, there will be no problem statements (except title and samples). Your goal is to collect as many points as possible within 2.5 hours :) Obviously, this round is **unrated**. It is somewhere between April Fools contest and a legitimate contest. The contest will be OI-style, meaning there will be no time penalty. You are allowed to use any resources online to help solve the problems. There will be **12** problems. **Scoring Distribution:** 200-400-700-700-700-800-800-900-1100-1100-1100-1500 (Total: 10000) **Please read all problems** as problem difficulty is very subjective and a 1100-point problem might b...

Full text and comments »

On Div2ABs 2 years ago, [user:antontrygubO_o,2022-04-27] wrote [a blog](https://codeforces.me/blog/entry/75163) about div2ABs where he expressed his opinions that d2ABs should not be about "here is a statement, please implement what is written there". Thanks to him, the quality of d2ABs (and problem quality in general) have certainly improved. However, I still believe that there still quite large differences between how coordinators/problemsetters view d2ABs and how the intended participants view them. From the survey made by [user:kpw29,2022-04-27], we can see that most people agree that most people agree that we should **primarily** consider the target audience when proposing a task. I too think if a task is boring to div 1 contestants, we should not think of that as a reason to immediately disqualify a problem from being a d2A.  I think when people judge the interesting-ness of d2As, they try...

Full text and comments »

Please restore Kotlin 1.6 Update: The current settings of 1.9 should run at least as fast as the previous Kotlin 1.6. Dear codeforces and [user:MikeMirzayanov,2024-01-16], Please restore Kotlin 1.6. This issue could be serious enough to end my CP career. The short story is that Kotlin 1.6 is the only 32-bit version. Without Kotlin 1.6 we must submit in 64bits, and in many situations this will be too slow. As the only 32 bits version available of the language, it should not have been removed to begin with. After using the exact language version on Round 920 (Div.3) having decent success, I found that I was unable to submit in Kotlin 1.6: It seems that Kotlin version 1.6 had been removed.  If this is a mistake, please restore it. If this is simply the result of having three languages versions being too much: You could probably remove 1.7.20, as 1.9.21 seems to be superior in every way. ...

Full text and comments »

Streaming my push for LGM Hi! It's been a while. My YT has certainly changed direction, but that's beside the point. I have been "silently" grinding for LGM over the past few months and sporadically earlier &mdash; avoiding explicitly doing contests, but doing plenty of virtuals and general practice. For now, I would put myself in the 2800s rating-wise (for a more detailed and dynamically updated log of the virtuals, see [here](https://docs.google.com/spreadsheets/d/1ocT7fbWmAoJCdRV05mVyJ6RBLo8LF9xAFkALdYfIIw8/edit?usp=sharing#gid=827979571/)). I want to hold myself accountable better. Getting myself to wake up is pretty damn hard. So I've opted to stream my grind over my winter break from college (roughly 3 more weeks of break, and probably streaming throughout school too), not only for myself, but as some sort of motivation for everyone to work harder (perhaps to create an environment where one can tune in and grind for themselves alongside). Logistics: I won't have a set start time, it will be soon aft...

Full text and comments »

[Tutorial] Proving the inverse Ackermann complexity of Union-Find #### Introduction Most of us are familiar with the union-find data structure and the two optimizations one can do on it: _union by rank_ and _path compression_. Most tutorials will introduce these methods and state that if both optimizations are used, the complexity will be $\mathcal{O}((n + m) \alpha(n))$. Here, $n$ and $m$ are the number of vertices and queries respectively. What is $\alpha$? Generally, we are told that $\alpha$ is some mysterious function that grows very slowly: $\alpha(N) < 5$ where $N$ is the number of subsets of particles in the observable universe and whatnot. What it is is usually not clarified very much. And there is typically no proof (or intuition and other such justifications) as to why the complexity is like that: usually we're told that the complexity analysis is quite long and complicated. At the time of writing, both [cp-algorithms](https://cp-algorithms.com/data_structures/disjoint_set_union.html) and [Wikipedia](https://bit.ly/3EvnzrI) are like th...

Full text and comments »

Teamscode Spring 2023 Editorial This is the editorial for a recent contest [Teamscode](https://www.teamscode.org/). The problems are open for upsolving on [this gym](https://codeforces.me/gym/104287). Problems were prepared by [user:oursaco,2023-04-06], [user:dutin,2023-04-06], [user:thehunterjames,2023-04-06], [user:Bossologist,2023-04-06], [user:Esomer,2023-04-06], and me. ### [A. What do you do when the contest starts? Are you busy? Will you solve Bingo?](https://codeforces.me/gym/104287/problem/A) <spoiler summary = "Editorial"> <spoiler summary = "Are you busy?"> 1. WorldEnd/SukaSuka 2. Bocchi the Rock </spoiler> <spoiler summary = "No Sweep"> 1. Thomas </spoiler> <spoiler summary = "Multiplication Table"> 1. Lycoris Recoil </spoiler> <spoiler summary = "Greatest Common Multiple"> 1. Bokuben </spoiler> <spoiler summary = "A Certain Scientific Tree Problem"> 1. A Certain Scientific Railgun </spoiler> <spoiler summary = "Two and Three"> 1. Quintessential Quintluplets...

Full text and comments »

C++17, competitive programming edition C++17 is now [available](http://codeforces.me/blog/entry/57646) on codeforces, community [wants](http://codeforces.me/blog/entry/15643?#comment-413401) new edition of [C++ tricks](http://codeforces.me/blog/entry/15643) by [user:Swift,2018-02-19], so, let's start! Disclaimer: I have done only few examples of new features, which in my opinion are related to competitive programming. Feel free to comment and provide more real-world examples or ask to elaborate some features with more examples or explanations. ### Fold expressions * I think that everybody knows, what reduce or fold means, but a c++11 example: ``` vector<int> v = {1, 3, 5, 7}; int res = accumulate(v.begin(), v.end(), 0, [](int a, int b) { return a + b; }); cout << res; // 16 ``` * In C++17 there is also folding support for a template parameters list. It has the following syntax: ``` (pack op ...) (... op pack) (pack op ... op init) (init op ... op pack) ``` * For example, implement a template...

Full text and comments »

[Tutorial] A Way to Practice Competitive Programming : From rating 1000 to 2000 Dear Codeforces Community.<br /> <br /> Today I want to share some ways to practice competitive programming and getting rating. I think this is helpful for those who is practicing competitive programming hardly but rating is sluggish. (By the way, on July 17th, I have a project of competitive programming said CombNaf in Japan. I did a lecture about this. Great thanks to the CombNaf's organizer is [user:Nafmo2,2017-07-17].)<br /> <br /> I will write this by **4 steps**: rating **<font color="grey">1000</font> --> <font color="green">1250</font>**, **<font color="green">1250</font> --> <font color="aqua">1500</font>**, **<font color="aqua">1500</font> --> <font color="blue">1750</font>**, **<font color="blue">1750</font> --> <font color="purple">2000</font>**, in Codeforces Rating System.<br /> <br /> Before writing about each step, I wrote it as premise: You don't have to do this way. This is just a way to practice. Ways to practice is different among people, so I think this may n...

Full text and comments »

A List of Useful Equations in Competitive Programming Hi, I am super excited to be back with another list. This time it is a **collection of some useful equations in Competitive Programming**. ### Motivation Do you find it bad if you couldn’t solve a problem just because you didn’t know about a certain equation? Do you find it difficult to take a quick look at an equation that you know exists but forgot about it while solving a problem? Do you think that all the equations that are important in CP are just cluttered and you are too lazy to collect them in one place? Well, then you are in the right place! I am here to solve all of the aforementioned problems. I believe you should not waste your precious time searching the internet for important equations. You should solve more problems. I am here to undertake the nasty task of collecting things. ### Payment Everything comes with a cost. You need to do something for me. That is you need to upvote this blog. Pretty easy! ### Acknowledgement Thanks to the following guys ...

Full text and comments »

MIT Mystery Hunt Disclaimer: This blog is not about competitive programming; you probably will not learn anything about algorithms and data structures. In other words, it doesn't qualify for [this initiative](https://codeforces.me/blog/entry/110840), but I want to give a link to it anyways because I think it's cool. I love solving problems. No, seriously. I LOVE it. The mindset described in [this blog](https://codeforces.me/blog/entry/91114) is 100% how I feel. But it is not constrained to competitive programming problems. I loved math problems for a much longer time, and physics was somewhere there. But I also love solving puzzles. And playing puzzle games on the computer (well, on consoles). And participating in intellectual games. I am not as good in them as in cp, but it was never about being good for me, I just love the process. And I think that there might be some people with a similar love for puzzles among competitive programmers, this is why I decided to write this blog on CF <s>and no...

Full text and comments »

[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution **Edit**: I have realized that this blog has been sent quite a lot on discord servers, so I am adding a content page at the start to help organize this blog better. ## Prerequisites Let us first define the classical knapsack, unbounded knapsack and subset sum problems. #### Subset Sum There are $N$ items. The $i$-th item has weight $w_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i = C$. #### Knapsack There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized. #### Unbounded Knapsack There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a **multiset** $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized. You should know how to do both versions of knapsack in $O(NC)$ and subset sum in $O(\frac{NC}{32})$ before reading this blog. In this blog post, I will just show some res...

Full text and comments »

CodeCraft-21 and Codeforces Round #711 (Div. 2) Editorial [problem:1498A] ================== #### [**Video Editorial**](https://www.youtube.com/watch?v=lV5cb8wh3sE) **Author and Problemsetting:** [user:ninja_28,2021-03-29] **Editorialist:** [user:sigma_g,2021-03-29] <spoiler summary="Hint"> Can you think of the simplest properties that relate a number and its sum of digits? </spoiler> <spoiler summary="Hint 2"> Note that if $X$ is a multiple of 3, then **both** $X$ as well as the sum of digits of $X$ are a multiple of 3! Can you put this property to use here? </spoiler> <spoiler summary="Hint 3"> If $X$ is a multiple of 3, then $\texttt{gcd-sum}(X) \ge 3$. Therefore, we are guaranteed that at least every third number will satisfy the constraints required by our problem $(\texttt{gcd-sum}(X) > 1)$. </spoiler> <spoiler summary="Solution"> Therefore, for the input $n$, we can simply check which one of $n$, $n+1$, and $n+2$ has its gcd-sum $> 1$, and print the lowest of them. </spoiler> <spoi...

Full text and comments »

Wanting to get contribution is good I initially wrote a longer comment on [user:Radewoosh,2018-08-17]'s blog but realized the following part is a completely separate thing. ### **Wanting to get contribution is a good thing.** It's an incentive to literally contribute to the community. This is how rankings work. People dream to be top10 rating one day and it motivates them to work harder. The "top contributors" list has the same goal: to incentivize people to help others. I don't mind if someone says "you want to get to top10 contribution" to me, and I joke with friends about it (also about [user:Swistakk,2018-08-17] and [user:Radewoosh,2018-08-17]). The bad thing is that a comment like this can be seen by others and make them less motivated (maybe unconsciously) to contribute. You likely don't realize how much the feedback matters. Preparing contests isn't more profitable than working in a company, but it's so rewarding to know some people liked your problems that it motivates you to do it again. It should be si...

Full text and comments »

Editorial of Pinely Round 3 (Div. 1 + Div. 2) The official implementations of all the problems are [here](https://drive.google.com/file/d/1q2PHS9nJt84FRwfMoiMslQULFE4dTMU4/view?usp=sharing). <spoiler summary="Timeline of the round proposal (may contain spoilers)"> (problems D', H', etc. were not used) - Feb 19, 2022: I proposed problem D' to [contest:1654], but it was not used. - Mar 13, 2023: I invented problem A. - May 16: I invented problem H'. - May 19: I realized problem G can be solved in $O(n)$ time and we used it in the Italian team selection test for IOI. - Jul 04: I opened a Div. 1 proposal containing A, D', G, H' and other problems which are not going to be used. - Aug 09: I invented problem I, with intended solution in $O(n^3)$. - Sep 27: I invented problem C. - Oct 14: [user:errorgorn,2023-12-23] replied to my contest proposal. - Nov 02: I invented problem D''. [user:errorgorn,2023-12-23] solved problem I in $O(n^2 \log n)$. - Nov 08: I invented problems E and F. I didn't propose problem F because I th...

Full text and comments »

An IDE for competitive programming: fetch testcases from websites, test on testcases in one click, and more When solving CP problems, are you tired of copy-pasting the testcases, and compare the outputs with the answers by eyes? Today I'll recommend a free-software IDE for those who want to automate everything in competitive programming. [](https://github.com/coder3101/cp-editor/releases/latest) [](https://github.com/coder3101/cp-editor/releases) CP Editor began from running testcases in one click, and has been grown into an IDE with many features, like parsing sample testcases from websites and submitting to Codeforces inside the IDE. It's cross-platform and lightweight, and most important, specially designed for competitive programming. You can learn about more features on the [official website](https://cpeditor.github.io/). It's also recommended...

Full text and comments »

The Toxic Mindset in Competitive Programming and How to Fight It #### Introduction Rating is a great measure of skill and a nice way to observe progress by comparing yourself to your past self and seeing where you stand in the community. As great measure as it is, there are a lot of problems that come with it. They have nothing to do with how the rating system works but rather with how human beings function. In this blog post, I will talk about some of the most pressing personal problems that come up with rating and try to provide some advice on how to solve them, speaking from personal experience and from the experience of a lot of other people I know. #### Associating self-worth to rating This is, in my opinion, the most significant problem people face, and it also pretty much contains all the following problems as a subset. It's extremely easy to fall into this rabbit hole since, as a competitive programmer, it only feels natural to associate our rating with intelligence and, respectively, our intelligence with self-worth. Why is this su...

Full text and comments »

Story about edge coloring of graph You are given a graph $G$, and for each vertex $v$ you have to assign a positive integer **color** such that every adjacent pair of vertices (vertices directly connected by edge) have different color assigned. You have to minimize the maximum color assigned: In other words, you have to minimize the number of distinct assigned colors. But that's [graph coloring](https://en.wikipedia.org/wiki/Graph_coloring) (vertex coloring). It's hard. Ok, one more time: You are given a graph $G$, and for each **edge** $e$ you have to assign a positive integer **color** such that every adjacent pair of edges (edges sharing same endpoints) have different color assigned. You have to minimize the maximum color assigned: In other words, you have to minimize the number of distinct assigned colors. This is the edge coloring of graph, and I will talk about this now. *Note that this can be interpreted as "graph coloring (vertex coloring) of line graphs". In that sense, you can consider in a similar...

Full text and comments »

First time becoming red In yesterday's contest [contest:1815] I've got the achievement which I could not imagine just half a year ago &mdash; reach 2400 rating and become GM. The first time I learned about CF was on 2022.2, that time I registered this account and took my first contest. But my first submission [submission:146390589] on contest got TLE, and I solved 0 problem in this contest. (At that time I didn't know that's because the efficiency of `java.util.Scanner` is extremely low) And because I needed to deal with graduation thesis, I didn't use CF until the end of last year, when I restarted CF contest. At 4th and 5th contests I solved div2D problems to reach blue. In my 9th contest, I first time solved div2E problem in contest, and I became purple in my 12th contest. In my 14th and 15th contest, I solved div2E problems twice and became orange. In the next weeks, I started to hit the upper limit of my skill, and dropped from orange twice. In order to improve my skill of competive programming...

Full text and comments »

Top 10 best Codeforces blog posts of 2021 (in my humble opinion) I really like good blog posts. And that's the main reason I like Codeforces. But as we all know, it's hard to find good blog posts here. So let's help each other and share our favorite posts, which were uploaded to Codeforces in the last year! I will share my top 10, and I encourage you to share some of your favorites in the comments. #### 10. [Heuristic algorithm for Hamiltonian path in directed graphs](https://codeforces.me/blog/entry/90513) by [user:Miracle03,2021-12-24] An absolutely incredible algorithm which kinda sometimes solves the Hamiltonian path problem on some random and special kind of graphs. #### 9. [I compiled a list of almost all useful blogs ever published on Codeforces](https://codeforces.me/blog/entry/91363) by [user:parveen1981,2021-12-24] This blog has a purpose that's similar to the purpose of the blog you're reading right now. A great source of interesting blog posts! #### 8. [Fast modular multiplication](https://codeforces.me/blog/entry/96759...

Full text and comments »

[Tutorial] Simulating Cost Flow You can also read this on my blog: https://mzhang2021.github.io/cp-blog/simulating-cost-flow/ Thanks to [user:gabrielwu,2023-07-19] for proofreading. --- This post assumes knowledge of [min/max cost flow](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem) and a rough understanding of the high-level methods for solving (successive shortest path and cycle canceling). Knowledge of specific algorithms and implementation details are not expected. Also solutions to some problems will use [Aliens trick](https://web.archive.org/web/20210511092429/http://www.serbanology.com/). --- The cost flow problem is a well-known problem in literature that a whole slew of competitive programming problems can be formulated as. Unfortunately, competitive programming problems typically have constraints set too high for directly running even the most state of the art cost flow algorithm. However, in certain problems the flow network will have a very specific setup that allows us to figure ...

Full text and comments »

You can do it, too! Introduction ------------------------------- So, I set myself [that challenge](https://codeforces.me/blog/entry/81383) to retire as a red coder before 24.09.2020... and I failed **miserably**. At least I am less delayed than most civil infrastructure projects. This blog will be a recap of this _short_ challenge with a mixture of some tips on practicing (for all levels!), some random life advice and, of course my bad sense of humour. It is dedicated to all those who aren't wonderkids, go from failure to failure and feel like banging their head into a wall during most of their competitive programming journey. Whatever your goal is, I'd like to strengthen your beliefs &mdash; you can do it! How it all started ------------------ My skill level has been in constant stagnation for years. I've always thought that I'm just not talented enough to be a grandmaster. Although I've been red twice in the past, it was quite lucky and the next contests were solid $-137$ and $-189$ so th...

Full text and comments »

Sums and Expected Value — part 2 ### Instruction I recommend this blog also for red users. Read the theory and problems below, try to solve them. For solutions and extra insight/tips, watch my stream on Monday or watch the video later. If you aren't familiar with EV or summing problems, see part 1 first: [http://codeforces.me/blog/entry/62690] (http://codeforces.me/blog/entry/62690). I will stream a lecture on Monday at [14:00 CEST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=EV+lecture+2&iso=20181029T14&p1=262) &mdash; [https://www.youtube.com/watch?v=HDk6zQw0Rdo](https://www.youtube.com/watch?v=HDk6zQw0Rdo) (also [Twitch](https://www.twitch.tv/errichto)). I will go through theory and problems from this blog. ### Expected Value theory, part 2 We roll a 6-sided die. Remember, EV of square of the number of pips is something different than square of EV: $$E(X^2) = \frac{1+4+9+16+25+36}{6} = 15.166666\ldots$$ $$E(X)^2 = (\frac{1+2+3+4+5+6}{6})^2 = 3.5^2 = 12.25$$ Two events are ...

Full text and comments »

How optimal is your CP setup? Click here and find it out! Recently I thought a lot about optimizing my setup. I don't think it is an important aspect of cp, as it barely affects the performance, but it is fun to think about nonetheless. In this blog, you will be able to determine whether you have an optimal setup or not. I will list the criteria and points you get for satisfying each one of them. In the end, I do the breakdown for different point ranges. I won't include things like **having a monitor** or **having an internet connection**, but I will be including basically everything else that comes to my mind. If you see something missing from the list, let me know in the comments, I will probably update my list then. This blog is mainly made for laughs, but if you are new, you will probably learn something new, even though **it won't help you to increase your rating**. ### You can compile and run your code. - $0$ points: I don't know how to run my code before submitting - $10$ points: I compile my code b...

Full text and comments »

Random notes on Lyndon decomposition I recently solved some problems that involved the concept of Lyndon decomposition. Honestly, most of them were too hard to understand for me. I'm just trying to think out loud about things I've read, so I can learn ideas or better takes from smarter people? Note that I will omit almost all proofs as I can't do that. I believe all unproven claims below are facts, but it is always great to have doubts about anything. ## 1. Lyndon decomposition, definition, and algorithms Partly copy-pasted from [this link.](https://cp-algorithms.com/string/lyndon_factorization.html#lyndon-factorization_1) A string is called simple (or a Lyndon word), if it is strictly smaller than any of its own nontrivial suffixes. Examples of simple strings are $a, b, ab, aab, abb, abcd, abac$. It can be shown that a string is simple, if and only if it is strictly smaller than all its nontrivial cyclic shifts. As a corollary, it can be observed that simple words are never periodic (it is not a repetition o...

Full text and comments »

Codeforces Round 1012 (Div.1, Div. 2, based on THUPC 2025 — Finals) There will, and there shall be a THU round! =========================================== Nihao Codeforces! After the unfortunate event which led to [contest:2081] and [contest:2082] being unrated last week, we’re back and stronger than ever! Tsinghua University’s Student Association of Algorithmic Competitions (THUSAAC) is pleased to invite you to participate in [contest:2089] and [contest:2090] on [contest_time:2090]. This round will be RATED for everyone. You will be given 2 hours and 30 minutes to solve 5 problems for division 1 and 6 problems for division 2, and two of each will have subtasks. **Note the unusual time of the round.** Our team of amazing problem setters include: [user:Iam1789,2025-03-20], [user:Ecrade_,2025-03-20], [user:E.Space,2025-03-20], [user:QuietBeautifulThoughts,2025-03-20], [user:gyh20,2025-03-20], [user:spiritualkhorosho,2025-03-20], [user:dapingguo8,2025-03-20], [user:myee,2025-03-20], [user:abruce,2025-03-20], [user:_lucien,2025-03-20]. Some of ...

Full text and comments »

On continued fractions. Part 3: In competitive programming Hi everyone! It's been quite some time since I wrote two previous articles in the cycle: [Part 1: Introduction](https://codeforces.me/blog/entry/73655)<br> [Part 2: Properties and interpretation](https://codeforces.me/blog/entry/73687)<br> **Part 3: In competitive programming** This time I finally decided to publish something on how one can actually use continued fractions in competitive programming problems. Few months ago, I joined [CP-Algorithms](https://cp-algorithms.com/algebra/continued-fractions.html) as a collaborator. The website also underwent a major design update recently, so I decided it would be great to use this opportunity and publish my new article there, so here it is: <center><big><b><a href = "https://cp-algorithms.com/algebra/continued-fractions.html">CP-Algorithms &mdash; Continued fractions</a></b></big></center> It took me quite a while to write and I made sure to not only describe common competitive programming challenges related to contin...

Full text and comments »

[cp-tricki] Welcome to cp-tricki! Hi there! Some long time ago, I and [user:SashaT9,2023-10-01] thought of an idea to create a collection of little tricks useful in competitive programming. We believe that such a website can both boost beginners, and be useful for experts as a reference website containing many example problems, which can be used, for example, to recall something, or, say, make an educational contest. It worth to say that there are already a bunch of blogs here with the same purpose. Our main feature is that we provide not just a list of tricks with their brief descriptions, but a detailed pages for each of them. This project was inspired by [tricki](https://www.tricki.org/) (currently dead) project. I already posted a test blog in order to demonstrate this format [here](https://codeforces.me/blog/entry/118108). We run a website based upon mkdocs (similar to cp-algorithms): https://cp-tricki.github.io/ Now we wrote five more or less simple (but unfortunately unpolished) pages: 1....

Full text and comments »

CP Editor: An Editor for Competitive Programming This blog is outdated. See https://cpeditor.org ================== Hi Guys! For the past couple of weeks, I was working on a new Code Editor for Competitive Programmers. Today, I am happy to present it to you all, the first release of CP Editor. But First, **Why we need a new editor**? There exists so many code editor of all types, written in all languages but all of them are tailored down for Development of Software and none is specially focused for Competitive Programming. As competitive Programmers, we need our Editor to be Fast, Reliable and Something that just works. We focus mostly on correctness of our code and this involves compiling and re-running on sample test cases again and again. CP Editor is Fast written in Native C++ (Qt), Cross-platform (works everywhere), and has all basic features that a competitive programmer needs from an editor. CP Editor takes away your responsibility of compiling the code and running it on your sample test cases. It automatically w...

Full text and comments »

Outstanding members of my cp library I like to build my [cp library](https://github.com/demidenko/olymp-cpp-lib). I am not aiming to fill it by each algo I have met, so content looks poor. Instead I am focusing on frequently used features or implement convenient api for powerful methods. Also I like to rate cp libraries of others and currently I noticed that my lib have enough implementations which I never seen before, so I want to share it with community. Hope it will inspire you to improve or rewrite your library and eventually rethink about some algorithms (which happens to me couple times). ## #5 Centroid decomposition [graphs/trees/centriod_decomposition.cpp](https://github.com/demidenko/olymp-cpp-lib/blob/master/graphs/trees/centriod_decomposition.cpp) This one is the perfect example of what I am calling convenient api. I've seen a lot of centroid decomposition snippets and almost all of them is template code or unfinished data structure with piece of code where you need to add your solution. I have s...

Full text and comments »

Osijek Competitive Programming Camp, Winter 2024 Hi everyone! <center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a> <a href="https://icpc.foundation/"><img src="https://ocpc.mathos.unios.hr/images/ICPC.svg" height="100px"></a></center> <center> <b>Sponsored by</b><br> <a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london"> <img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;"> </a> <a href="https://pinely.com/"> <img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;"> </a> </center> After successful camps last year ([winter wrap](https://codeforces.me/blog/entry/113438), [fall wrap](https://codeforces.me/blog/entry/121684)), we are happy to announce that Osijek camp will be returning on **17.-25. February 2024** &mdash; just in time to prepare for the Wor...

Full text and comments »

[Tutorial/Parody Post] Common Mistakes in Competitive Programming and How to Avoid Them Yesterday [user:YouKn0wWho,2023-01-11] posted a [blog](https://codeforces.me/blog/entry/111217) explaining common mistakes in competitive programming and how to avoid them. I was greatly inspired by that post so I decided to make my own. I have compiled some of the mistakes that I didn't make in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in Rust as it is the most beloved language for CP. #### Mistake 1 Check out the following code: <spoiler summary="Code"> ``` fn main() { let x: i32 = 1_000_000_000; let y: i32 = 1_000_000_000; println!("{}", x * y); } ``` </spoiler> The output should be $10^{18}$. But if you run the code, you will get a different output. Why? <spoiler summary="Reason"> Because it won't even compile....

Full text and comments »

Help Ukrainian Olympiads Hello. I am from Ukraine. I am sure that you know about the situation in my country and about things happening right now. Many people are giving infinitely valuable help to Ukrainian refugees, donating to UAF and simply helping spread the truth. I am sure we have such people also in our community. Ukraine, Ukrainians, and personally I appreciate your help highly. Thank you so heartily. But now I am here to ask you, the Codeforces community, for help. There is no safe place in Ukraine right now &mdash; everywhere you might get killed by a missile strike, so holding the IOI selections is obviously impossible. Our dear friends from Poland decided to help us. They will organise everything for us, but they need money. [→ Click here to donate ←](https://zrzutka.pl/en/v7pdbm) Ukrainian competitive programmers are one of the most powerful cp-eps in the World. Our the most recent achievements: - Baltic Olympiad in Informatics &mdash; 4 gold medals, 2 bronze medals - International Z...

Full text and comments »

cp-algorithms.com update + Hacktoberfest For everybody new to [**cp-algorithms.com**](https://cp-algorithms.com/). It is a community project, that started as a translation project of the Russian algorithm website [e-maxx.ru](http://e-maxx.ru/algo). In the meantime most of the articles are translated, multiple new articles have been added, old articles have been improved and extended. In total we have 143 article about different competitive programming topics, anything from algebra, graphs, string algorithms, data structures, geometry, and more. So check it out ;-) Although in the last months not many improvements/new articles has been done (I've been busy with work/study), the website is still growing a lot. Especially last October we had a lot of new content. A year ago we had translated only 71% of the Russian articles from e-maxx.ru, today over 85% are translated. And according to Google Analytics the number of users is growing still a lot. Last year we had over 250.000 users. The following graph shows the user numbers ...

Full text and comments »

Sports Programming or Competitive Programming? Which one should we use? Competitive Programming is used more often but it has stupid abbreviation (Cerebral Palsy and Child Pornography). Some Youtube accounts about Pokemon Go were actually banned for using that because of Combat Points. [Here](https://www.bbc.com/news/technology-47278362) you can read things like _"My Club Penguin video had been flagged for sexual content"_. This also means it isn't cool to write _"I'm addicted to CP"_ in any social media. Urban Dictionary says that SP means Sex Party, but I don't think it's common and at least it isn't something shameful/harmful. I think the Polish term is "programowanie sportowe" (sports programming) but sometimes we just say English words "competitive programming". The Russian say "Спортивное программирование" (sports programming), in Portuguese it is "Maratona de Programação" (programming marathon). What do you say in your language? In particular, I would like to hear native speakers to state their opinion. And Sport...

Full text and comments »

GoForGold Camp 2024 — Wrap I just returned from the **1st** edition of the [**GoForGold** camp](https://codeforces.me/blog/entry/135929) in India &#x1f1ee;&#x1f1f3;, where I had the privilege of teaching some of the brightest Indian students as they prepare for the upcoming ICPC World Finals. After organizing camps in [Syria](https://codeforces.me/blog/entry/118493), [Uzbekistan](https://www.linkedin.com/feed/update/urn:li:activity:7144180416655118336/), Azerbaijan, and [Croatia](https://codeforces.me/blog/entry/134097), this was yet another incredible experience of helping students push closer to their competitive programming goals. A highlight of this trip was witnessing the unique approach of Newton School of Technology. They brought teachers right from industry to university to fill the gap &mdash; a truly innovative structure that left a lasting impression. Congratulations to the top three winners in Div. 1:<br> &#x1f947; [404_solution_not_found](https://codeforces.me/team/168505): [user:P.V.S...

Full text and comments »

The Brazilian IOI 2023 Team was selected and it is stacked Hello codeforces! Because of weird scheduling issues, the brazilian TST is normally made at december of the year before IOI, different from the rest of the countries. So, today was the last day of TST and after 4 days of contests we have our team settled:  From left to right, we have: - Leonardo Valente Nascimento ([user:definitelynotmee,2022-12-10]) - Rafael Nascimento Soares ([user:Deepesson,2022-12-10]) - Arthur Lobo Leite Lopes ([user:LoboLobo,2022-12-10]) - Pedro Suyama Leston Rey ([user:pedroslrey,2022-12-10]) In case youre curious, here is a screenshot of the scoreboard so you can see how everyone went.  We were quite comfortably above 5th place in the end, but i had a headache on the first day so i wasn't even top 4 on it. The problems were also really good, as they typically are (even though i can't say the same...

Full text and comments »

Fenwick bitset _Okay guys, I know it sounds like [Top 10 optimizations 2017- (collectors edition)](https://codeforces.me/blog/entry/53168) but hear me out_ Hi everyone! Recently, a problem **[ordered set](https://judge.yosupo.jp/problem/ordered_set)** has been added to Library Checker. Essentially, the problem asks you to maintain a set $\\{a_1,\dots,a_n\\}$ that supports the following operations: 1. Insert an element; 2. Erase an element; 3. Find the $k$-th smallest element; 4. Find the order index of an element; 5. Find lower bound of an element; 6. Find pre-upper bound of an element. Of course, all these [can be done](https://judge.yosupo.jp/submission/248515) with GNU policy-based data structures (pbds) in $O(\log n)$ per query, which leads to the shortest code. At the same time, it has a huge constant factor in practice, so a natural question arises. What would be the fastest way to solve this? One of my [earliest blogs](https://codeforces.me/blog/entry/11275) already addre...

Full text and comments »

Codeforces Round #554 (Div. 2) Once again, **TREMBLE BEFORE THE MIGHTY OMEGALULRIPGRAPE.**   *(He last walked the Earth in round [538](https://codeforces.me/blog/entry/65033) btw.)* Hello Codeforces! We are here to invite you to Codeforces Round #554 (Div. 2), which will take place at [contest_time:1152]. The round will be rated for all Division 2 participants **(with rating less than 2100)**, yet any Division 1 participants are welcome to join us out of competition. The round will be cat themed. Raise your paws and prepare your catnips! *(Or even cat memes, while you're at it).* You will be given **6+1** problems ( **6** problems, one of them has **2** subtasks ) to solve in **2 hours.** The round's problems were prepared by Xuan-Quang ~xuanquang1999,2019-04-23 D. Nguyen, Duy-Bach ~Akikaze,2019-04-23 Le, Stefan ~stefdasca,2019-04-23 Dascalescu, Quang-Minh ~MofK,2019-04-23 D. Nguyen and our dear Codeforces coordinator ...

Full text and comments »

[Tutorial] Online Dynamic Connectivity The World Finals are right ahead, and if everything works as I expect, you will probably have to wait a lot of time before the contest, dress rehearsals, or anything else. I prepared this blog post so that you have something to keep yourself occupied. # Goal Our goal is to maintain connectivity in fully-dynamic query streams. In other words, we want to solve this problem: * Insert an edge $e = (u, v)$ into a graph * Delete an edge $e = (u, v)$ into a graph * Find if two vertices $u, v$ are connected * Find the size of connected components where the vertex $u$ belongs. The *offline version*, where you can *cheat* (aka, read all queries before answering, and answer everything at the very end of the program) has a very cool solution commonly known as *Offline Dynamic Connectivity*. This is enough in most CP problems, where this *offline* solution is rarely considered cheating. Unfortunately, people in the academia are not chilling and consider this a kind of cheating (n...

Full text and comments »

[Tutorial] Easy Introduction to Kitamasa Method ### Before Reading... 1. Sorry for my poor English skill. 2. The propose of this article is "EASY" introduction to Kitamasa, so strict proofs can be omitted. ### What is Kitamasa Method? Kitamasa Method can compute N-th term of linear recurrence ($A_N = c_1A_{N-1} + c_2A_{N-2} + \cdots + c_KA_{N-K} = \sum_{i=1}^{K} c_iA_{N-i}$) in $O(K^2 \log N)$ or $O(K \log K \log N)$ when you manipulate polynomial with FFT. ### Let's transform the equation The goal of Kitamasa is find $d_i$, such that $A_N = \sum_{i=1}^{K} c_iA_{N-i} = \sum_{i=0}^{K-1} d_iA_i$. In other word, we can compute N-th term using **first K elements** instead of **before K elements**. If we can get $d_i$ in $T(N, K)$, we can compute N-th term in $O(T(N, K) + K)$ time. We can find $d_i$ just using $A_i \leftarrow (c_1A_{i-1} + c_2A_{i-2} + \cdots)$ . For example, let's think about $A_N = 2A_{N-1} + A_{N-2}$. ($c_1 = 2, c_2 = 1$). * $A_5 = 2A_4 + A_3$ * $A_5 = 2(2A_3 + A_2) + A_3 = 5A_3 + 2A_2$ * $A_5 ...

Full text and comments »

Ten years of Competitive Programming Hey Codeforces! I’m AmirReza PourAkhavan, Codeforces Contest Coordinator. I let the story become complete and I’m sharing it now. The story is about a 16-year competitive programmer, who left his family and migrated to another city alone to follow competitive programming. After seven years, he advanced to the International Collegiate Programming Contest World Finals, twice. ### Why I’m writing this Six years ago someone asked me [here](https://codeforces.me/blog/entry/45186?#comment-297837) to write my story. I think it can help you to never give up. ### A brief about me I've been doing competitive programming for ten years. I advanced to ICPC (International Collegiate Programming Contests) World Finals twice, in 2019 at Porto and 2020 at Moscow. At ICPC World Finals 2020, our team took high-honored place twenty-four, which is equal to the top 0.03% of 200k students participating in ICPC. <center> <br> <img width="50%" src="/predownloaded/c2/0c/c20c501bba688...

Full text and comments »

After-stream thoughts Hello again. Next stream will start tomorrow (Wednesday) at 2pm CEST ([your timezone](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Errichto+Stream+%233&iso=20181003T14&p1=262)), solving problems from POI 22, round 1 ([link](https://szkopul.edu.pl/p/default/problemset_eng/oi/22)). It will be on my [Youtube channel](https://www.youtube.com/channel/UCBr_Fu6q9iHYQCh13jmpbrg). I did two streams this weekend that you can now find on my youtube [channel](https://www.youtube.com/channel/UCBr_Fu6q9iHYQCh13jmpbrg). The first with quite easy Codeforces problems that I solved from scratch (I haven't seen them before), also implementing them. The second one with a bit harder Topcoder problems that I've solved before, but I didn't necessarily remember the solution now &mdash; and for those I only described the solution, without implementation. The streams were fine but there are a lot of things to improve. I wanted to see two things: 1. Can I stream? Am I able to try to sol...

Full text and comments »

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall Hello Codeforces! I just uploaded the [first paper of my life](https://arxiv.org/abs/2404.08173) to arXiv, and I'm happy to share this with the community, especially because it is very related to competitive programming. Here is the [presentation](https://docs.google.com/presentation/d/1OE9cPSLMl4cHFqxjbPL8FRXo4ZKmRvTHKqgJbcoRobU/edit?usp=sharing) I gave in MIT Theory Lunch. ## What's the problem? Everyone knows the Floyd-Warshall algorithm for computing the shortest path, it goes like this: ~~~~~ rep(k, n) rep(i, n) rep(j, n) A[i][j] = min(A[i][j], A[i][k] + A[k][j]); ~~~~~ And everyone knows this *incorrect variant* of Floyd-Warshall. I certainly implemented this when I was learning CP, cause I kinda wanted to "fix the loop order". ~~~~~ rep(i, n) rep(j, n) rep(k, n) A[i][j] = min(A[i][j], A[i][k] + A[k][j]); ~~~~~ This is bad, it does not compute the shortest path. It does, however, compute "something". Imagine someone gives you a sparse graph and asks you to ...

Full text and comments »

CP Editor 5.0 : Submit to codeforces right from CP Editor Check : https://cpeditor.org ================== Hi Guys! CP Editor met Competitive Companion in 3.0, giving it the ability to parse contests from over 30+ online competitive programming websites. Now, with CP Editor 5.0, it met CF tools, a wonderful tool by [user:xalanq,2020-01-09] which can do all most everything in code-forces, even submit solutions. Read more about CF tools in his [blog](https://codeforces.me/blog/entry/66552). *If you are a pro-user and like vim keybindings, using cf-tools on your favorite terminal with tmux would give your more than what CP Editor has to offer but at the same time, it is very time consuming and difficult to setup on windows.* Let's dive into what is new for us in CP Editor 5.0 - **Submit solution to Codeforces from CP Editor**, you don't need to copy or upload your solutions manually. Let CP Editor do it for you with just one button click. This feature requires that you have `cf-tools` installed and you have correctly configured c...

Full text and comments »

[Tutorial] Convex Hull Trick — Geometry being useful ### The problem Let us consider the problem where we need to quickly calculate the following over some set $S$ of $j$ for some value $x$. $$\max_{j \in S} \{m_j \cdot x + c_j\}$$ Additionally, insertion of new $j$ into $S$ must also be efficient. This will most likely be encountered with DP problems. For example, the recent problem [problem:1083E] from Round #526 has the following DP formulation after sorting the rectangles by $x$. $$f(i) = x_i \cdot y_i - a_i + \max_{1 \le j < i}\{-x_j \cdot y_i + f(j)\}$$ The problem requires quick calculation of the above define maximum for each index $i$. How can this be done? ### The idea Notice the special form of $m_j \cdot x + c_j$. This is identical to the equation of a straight line with slope $m_j$ and Y-intercept $c_j$. So the problem is equivalent to being given a set of lines and asked for the maximum $y$ value any of those lines can give at a particular $x$. If you draw a bunch of straight lines on a plane, you'll...

Full text and comments »

Implicit Prime Factorisation Those of us who have been doing cp for a long time, have come to love the representation of numbers as an infinite prime power vector i.e. $$n = \prod p_i^{e_i} = [e_1, e_2, \ldots ] = v_n$$ Where $n$ is a number and $p_i$ is the $i$ th prime number. This has many useful properties for problems, such as mapping $$n \times m \sim v_n + v_m$$ $$n / m \sim v_n - v_m$$ $$n \mid m \sim v_n \le v_m$$ $$\gcd(n, m) \sim \min(v_n, v_m)$$ $$lcm(n, m) \sim \max(v_n, v_m)$$ All the above operations are done elementwise. However in some cases, the problem authors may forbid you from factorising the numbers, by perhaps increasing $n$ to around $10^{36}$ where there isn't any simple factorisation algorithm to do it in reasonable time. However using effective prime factorisation, we can use these properties freely on a set of numbers. If this set contained all integers, then it would require us to truly prime factorise the integer. However, we only need to use these operations on a subset...

Full text and comments »

From 0 to ICPC in 1 Year **Welcome to my first blog!!** <br> &nbsp;&nbsp;&nbsp;&nbsp; I'll be sharing my journey in the cp world and how I managed to qualify to ICPC 1 year and 3 months (sorry for the clickbait) into my cp career. If you're curious what it took to achieve this, or if you're looking for some motivation or inspiration, this blog is for you :) <br> A special thank you to [user:alnq417,2024-12-12] for helping me cook this blog <3 <br><br> ### _Starting My CP Career:_ _LCPC 2023 Fail_ &nbsp;&nbsp;&nbsp;&nbsp; One month before LCPC 2023 (Lebanese Collegiate Programming Contest), my university informed me about the competition. I was a second year student at that time so I quickly formed a team and registered, not knowing anything about the competition at all. I had high hopes, thinking it would be something similar to what I was studying at university and I assumed I'd do well. <br><br> &nbsp;&nbsp;&nbsp;&nbsp; Fast forward a month, I solved the easiest 4 problems in the competition and r...

Full text and comments »

Competitive Programming Roadmap (target: [gray, blue]) tl;dr ------------------ - Competitive programming roadmap [here](https://drive.google.com/file/d/16Jydn250Ue7K7hOfzLxw4p5jFF4ZCqWT/view?usp=sharing). - It should be suitable both for newcomers and for people with some experience with CP: let's say, up to blue on Codeforces. - It contains ~ 100 "must-know" problems about various topics: ad-hoc, STL, binary search, DP, number theory, graphs. - There are solution sketches at the bottom, don't feel guilty reading them if stuck. Why? ------------------ Many people new to Codeforces seek advice about how to get better / which problems to try. Other people are stuck on gray / green even after solving a lot of problems. This roadmap aims to be a solution. My take: to be good at competitive programming, you have to know "what to think" and "how to think" when you try a problem. - "What to think": you have to know a decent amount of standard problems / techniques. Sometimes, a problem requires steps / observations that seem ob...

Full text and comments »

[Tutorial] Solving Linear Recurrences with various methods, Including O(N logN logK) using FFT <spoiler summary="Hi this is my first educational blog on codeforces......"> I have been procrastinating to write this one for over 15 months by now, but thanks to [user:crackersamdjam,2021-12-06]'s [comment](https://codeforces.me/blog/entry/97534?#comment-864474), I finally did it! Any suggestions or improvements or constructive-criticism to the blog, is heavily appreciated. In this blog, I tried to avoid too many technical terms (especially in the last section), and tried to make it beginner friendly. </spoiler> Linear Recurrence : Introduction ------------------ Fibonacci Sequence is one of the simplest examples of a linear recurrence: $F_x = F_{x-1} + F_{x-2}$, with $F_0 = 0, F_1 = 1$ Here is a more general example of a linear recurrence: \begin{align} R_{x} = \sum_{i=1}^{n}{C_i \cdot R_{x-i}} \end{align} where $C_i$ is constant and $R_x$ is the x-th term of the recurrence. Since $R_x$ depends on the previous $n$ terms of the recurrence, it is called a li...

Full text and comments »

Some common CP code practices which I think would be better changed Hello. After getting prize on ICPC 2020 Seoul Regional and writing Round #633, I almost stopped solving CP problems and entered quant industry. Now I have no job so I am not busy until I get next job, so I often describe my thoughts on online websites. This article is one of those. In this post, I am going to write about some common CP code practices which I think would be better changed. Before enumerating practices, I want to specify that this post is mostly focused to: 1. Who wants to get dev jobs 2. Who wants to create their practices from CP to productions without switching code style too much (i.e. Not having too different mindset for coding styles in CP and real applications) If you just don't care, it's ok. I am not saying writing CP-style codes is bad, unless you believe you can use same practices on productions. Now let's dive in. ### `using namespace std;` What happens if you include big header files like `bits/stdc++.h` and do this? Bunch of functions, class...

Full text and comments »

Новый ресурс для изучения алгоритмов **TL;DR** Хочется сделать новый e-maxx с актуальными алгоритмами и удобными реализациями с упором на продвинутые алгоритмы, про которые мало где можно прочитать. Сейчас уже есть 23 статьи, собранные по ссылке: [peltorator.ru/cp_book.pdf](https://peltorator.ru/cp_book.pdf). Последние изменения доступны по [ссылке](https://peltorator.ru/cp_book_changes). TeX исходники доступны на [гитхабе](https://github.com/Peltorator/peltorator-cp-book). Веб-версию можно найти по сссылке [peltorator.ru](https://peltorator.ru). Всем привет! Я хотел бы показать, над чем я работал последние 4 месяца. Начнем издалека. Все мы любим e-maxx, все мы им пользуемся. Однако я уверен, вы тоже чувствуете, что он не идеален. Во-первых, он уже не обновлялся 9 лет, и за это время появилась куча разных новых актуальных алгоритмов, о которых можно прочитать только в случайных статьях на codeforces и подобных сайтах, да еще и в основном только на английском языке (или китайском). Во-вторых, часто коды, которые есть...

Full text and comments »

Useless CP Information #6: How Much Harder is Div 1 vs Div 2? Hey guys it's your favorite <strike>purple</strike> not anymore CF shitposter here. We're back to hopefully non-controversial useless information lol I think anecdotally we all have this gut feeling that it's harder to get a X perf in a div 2 than a div 3, and in turn harder to get X perf in a div 1 than a div 2. Is this urban legend or a real phenomenon? Methodology ------------------ I took several of the most recent separated div 1 and div 2 rounds where the div 1 round has the same problems shifted by 2 positions. For each contestant in the div 2 round, we'll: - Calculate and record their div 2 perf - Convert to estimated div 1 score by dropping problem A/B, adjusting timestamps on the rest of the problems, and recalculating the score based on the problem values for div 1. (We will discard anyone who solves C/D/E/F before A/B) - Calculate and record their div 1 perf from the new score we calculate. ### Calculating performance (CP lesson time!) Using FFT, our...

Full text and comments »

CP Editor 2.0.3 : Everything you wanted is here Check : https://cpeditor.github.io ================== Hi Guys ! Around a week ago, I released the first version of CP Editor. If you are reading about CP Editor for first time. I request you to read my [previous blog](https://codeforces.me/blog/entry/71673) first. Many user liked it and I got many suggestions about enhancements and some bug reports as well. I liked your over whelming response, it made me happy. Now it's time for me to make you happy. Enough talking, let's get into what's new in CP Editor 2.0. It is a big release and hence a long blog ;-) ##### Dark theme Last time there was a dark theme but it only made the editor dark. So, it wasn't truly dark theme. Now with this new release CP Editor packs a system-wide dark theme. Have a look here  ##### Dependency Updates Just like any other software, CP Editor also have a long acyclic dependencies, and over the weeks many were updat...

Full text and comments »

Taylor Formula in CP This blog appeared due to the [competition](https://codeforces.me/blog/entry/149422) from [user:cadmiumky,2026-01-26]. Many thanks to him for the initiative. Preliminaries: Taylor formula. ------------------ Let us start with a reminder. Consider a function $f$ that is $n + 1$ times differentiable. Then it is known (from the calculus course) that $$ f(x_0 + h) = \sum_{i = 0}^{n} \frac{f^{(i)}(x_0)}{i!}h^i + \varepsilon_n(h), $$ where $\varepsilon_n(h) = \frac{f^{(n + 1)}(x_0 + \xi)}{(n+1)!}h^{n + 1}$ for some $\xi \in [0, h]$. Ok, that's nice, but how on earth is this applicable to competitive programming? Let's see an example. Counting probabilities ------------------ I couldn't find the exact statement of the problem, so I will write it in a way I remember it. If you know the exact contest it comes from, please, share it with me. **Petrozavodsk Winter Programming camp, 2017** Consider $n$ slot machines in a row. Each of these machines has a number $p_i$ ...

Full text and comments »

LI2 Contests Announcement — Free Programming Course Hi everyone! I'm thrilled to invite you to the **LI2 Contest &mdash; free collection of high-quality contests to master every topic** &mdash; here, on Codeforces! [Group Link! Click here!](https://codeforces.me/group/jtU6D2hVEi/blog) ### Current avialibale list of topics: Loops; Prefix Sums; Sortings; Binary Search; Recursion; Sweepline; Two Pointers; Linear Data Structers (stack, queue, etc); Graphs, DFS, BFS; Dynamic Programming; DSU; Shortest Paths; Minimum Spanning Tree; Greedy; ... ### Why this course? I believe that finding high-quality problems is the hardest part of practice, especially when you are only getting your feet wet with competitive programming. There are many lectures and articles, but not so many open collections of problems for each topic. ### Time-tested I guarantee you that this course is time-tested, **I used it myself**. LI2 is short for Boarding Lyceum №2 in Kazan &mdash; the school I study in. So we've been using this course for...

Full text and comments »

Editorial of Codeforces Round #768 ### [problem:1631A] Author: [user:humbertoyusta,2022-01-27] <spoiler summary="Hint 1"> Think about how $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$ will contribute to the answer. </spoiler> <spoiler summary="Hint 2"> The maximum of one array is always $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. How should you minimize then? </spoiler> <spoiler summary="Solution"> Let $m_1 = \max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. The answer will always be $m_1 \cdot m_2$ where $m_2$ is the maximum of the array that does not contain $m_1$. Since $m_1$ is fixed, the problem can be reduced to minimize $m_2$, that is, minimize the maximum of the array that does not contain the global maximum. WLOG assume that the global maximum will be in the array $b$, we can swap elements at each index $x$ such that $a_x > b_x$, ending with $a_i \leq b_i$ for all $i$. It can be shown that the maximum of array $a$ is minimized in this way. Time complexity: $O(n)$ <spoiler ...

Full text and comments »

IQ is Pure COPE, Here's Why (Useful CP and Life Information #5?) Background ------------------ On CF I think you can tend to see people attributing good rating to IQ. This is often associated with hopelessness when people are stuck in gray/green. I think it's the perfect cope &mdash; it's the easiest thing to say that completely explains why you're 1100 and your friend is orange, and, bonus, if anyone tries to prove you wrong, you can just claim that they are privileged and intelligent. You may think I am 2000 and thus out of touch to be able to comment on this topic, which _may_ be true. However, I was also once a noob who got 28/1000 on a USACO silver round. And I was pretty overweight as a kid and sucked at sports and always thought of myself as not having the genetics to be an athlete, but [I now hold the squat, bench, and deadlift 18-and-under state records in my powerlifting federation](https://pa.liftingdatabase.com/records-default?recordtypeid=72&categoryid=603&weightclassid=5). (Probably not for long though lol) A lot of this i...

Full text and comments »

Kotlin Heroes Editorial [problem:1170A] Idea: [user:Vovuh,2019-05-28] Solution: [user:elizarov,2019-05-28] <spoiler summary="Tutorial"> [tutorial:1170A] </spoiler> <spoiler summary="Solution"> ~~~~~ fun main() { val q = readLine()!!.toInt() repeat(q) { val (x, y) = readLine()!!.split(" ").map { it.toInt() }.sorted() println("1 ${x - 1} ${y - x + 1}") } } ~~~~~ </spoiler> [problem:1170B] Idea: [user:MikeMirzayanov,2019-05-28] Solution: [user:elizarov,2019-05-28] <spoiler summary="Tutorial"> [tutorial:1170B] </spoiler> <spoiler summary="Solution"> ~~~~~ fun main() { val n = readLine()!!.toInt() val a = readLine()!!.split(" ").map { it.toInt() } var m1 = 0 var m2 = 0 var c = 0 for (x in a) { if (m2 > x) { c++ } when { x > m1 -> { m2 = m1 m1 = x } x > m2 -> { m2 = x ...

Full text and comments »

Brief introduction of rook theory and its application to a problem ###Rook theory Imagine a board of $n \times n$ , and upon that you are going to put some rooks on it, without letting them attack each other. (Recall that rook attacks all squares vertically and horizontally from where it is located) and you are going to calculate how many ways there are to do it. Obviously, it is $n!$ . What about the situation with some cells forbidden then? Here comes the rook theory. The rook theory utilise two polynomials: rook polynomial and the hit polynomial. Let's call the set of forbidden cells $\mathfrak{B}$ . **Rook polynomial:** Rook polynomial is that $R(x) = \sum{r_kx^k}$ , where $r_k$ is the number of ways to put $k$ rooks on $\mathfrak{B}$ ; **Hit polynomial:** Hit polynomial is that $H_n(t) = \sum{h_{n,k}t^k}$ , where $h_{n,k}$ is the number of ways to put $n$ rooks on the board with $k$ rooks on $\mathfrak{B}$ . According to the Principle of Inclusion and Exclusion, we've got $H_n(t) = \sum{r_k(n-k)!(t-1)^k}$ . What...

Full text and comments »

[Tutorial] On Variations of String Matching Hello, Codeforces! Following the recent motivation of writing educational blogs thanks to [user:peltorator,2023-01-14] ([context](https://codeforces.me/blog/entry/110840)), I decided to write another blog on strings, specifically on variations of the very classic String Matching Problem. **Prerequisites** <br> 1. KMP &mdash; [cp-algorithms](https://cp-algorithms.com/string/prefix-function.html) <br> 2. Aho-Corasick &mdash; [cp-algorithms](https://cp-algorithms.com/string/aho_corasick.html) <br> 3. FFT &mdash; [blog](https://codeforces.me/blog/entry/111371) by [user:-is-this-fft-,2023-01-14] Throughout this blog, $n$ will be the size of the text (or sum of sizes of texts, if applicable), and $m$ will be the same for the pattern. Simple Pattern Matching ------------------ **Input**: text $T$, pattern $P$. <br> **Updates**: none. <br> **Query**: in which positions does $P$ occur in $T$? This is just KMP. **Complexity**: $\mathcal O(n + m)$ Multiple Patterns...

Full text and comments »

Stop Looking at Standings Story Time ------------------ It's been about a year since I started CP and reached Expert pretty fast. However, for some reason or the other, I couldn’t reach CM. I got pretty close multiple times but lost rating as soon as I was one contest away. It felt like I was collecting every 18xx rating lmao.  At least in the beginning, the reason I wasn’t CM was, well, I genuinely wasn’t at that level yet. However, towards the end of the year, I felt like I was of that strength, but for some reason couldn’t convert that into the rating jump I needed. I think some of you would be able to relate to this &mdash; you feel stronger than your current rating, but can’t reach there, and maybe there’s something holding you back psychologically. Beating Psychological Pressure During a Contest ------------------ I tried to do something different in the last 2 contests I wrote to deal with pressure. Firstly, I stopped...

Full text and comments »

Guessforces Bestforces — How I Guessed My Way to GM  *It turns out that randomly guessing works in Div. 1 too...* I have reached GM thanks to **randomly guessing**. **Ask me anything!** Since I have already argued in theory [how randomly guessing helps CF rating](https://codeforces.me/blog/entry/12687), I figured that I might as well compile a list of problems I guessed on my way to GM, to give some empirical evidence to all esteemed grandmasters before my rating falls off. So let us get started! ## [1975D &mdash; Paint the Tree](https://codeforces.me/contest/1975/problem/D) *Just solve the problem manually and claim it is the best solution.* Surely *it is.* <spoiler summary="Spoiler"> After playing a bit with the two pieces I found that I always make them collide. Fortunately, it suffices to randomly guess that the red piece and the blue piece will first travel to meet each other and then traverse the tree. I still have no idea why ...

Full text and comments »

The Ultimate Equation List This is **a collection of all important equations in Competitive Programming**. # Motivation Do you find it bad if you couldn’t solve a problem just because you didn’t know about a certain equation? Do you find it difficult to take a quick look at an equation that you know exists but forgot about it while solving a problem? Do you think that all the equations that are important in CP are just cluttered and you are too lazy to collect them in one place? Well, then you are in the right place! I am here to solve all of the aforementioned problems. I believe you should not waste your precious time searching the internet for important equations. You should solve more problems. I am here to undertake the nasty task of collecting things. # The Equation List 1. Axiom of extensionality: $\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y]$ 2. Axiom of regularity: $\forall x[\exists a(a\in x)\Rightarrow\exists y(y\in x\land\lnot\exists z(z\in y\lan...

Full text and comments »

A Beautiful Technique for Some XOR Related Problems ## Inspiration I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P So here I am, sharing it on CF. I also created a [personal blog](https://drschwad.github.io/), so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^\_^ ## Introduction Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on ...

Full text and comments »

Writing a book on geometry — Update Hi, I've updated my geometry book over at [https://vlecomte.github.io/cp-geo.pdf](https://vlecomte.github.io/cp-geo.pdf). I hope you like the new content, and I would really appreciate any feedback: suggestions, comments, typos you found, etc. :) The changes I made: - Finished the chapter on "basics" and made some changes based on your feedback from last time. - Added a whole chapter on precision issues and how to deal with them. I think some of the problems and ideas in this chapter are not obvious to all and I think they can be useful for people who don't feel very confident in geometry. The codes are mostly untested for now so take them with a grain of salt (and tell me about the mistakes you find). In a few weeks, I will hold a Gym contest showcasing geometry techniques/concepts that are not very common at the moment but could help make interesting problems and add some variation to geometry in ICPC-style or online contests. There will be 5 problems for 3-4 hours...

Full text and comments »

Computing n! modulo pᵏ for small p Hi everyone! There is an [article](https://cp-algorithms.com/algebra/factorial-modulo.html) on cp-algorithms about how to compute $n!$ modulo prime number $p$. Today I was wondering, how to do it if we need to compute modulo $p^k$ rather than just $p$. Turns out one can do it efficiently if $p$ is small. #### Motivational example **[Xiaoxu Guo Contest 3 &mdash; Binomial Coefficient](https://www.acmicpc.net/problem/19124)**. Given $1 \leq n,k \leq 10^{18}$, find $\binom{n}{k}$ modulo $2^{32}$. There are also some projecteuler problems that require it, including with several queries of distinct $n$ and $k$. #### Task formulation and outline of result To clarify the task a bit, our ultimate goal here is to be able to compute e.g. binomial coefficients modulo $p^k$. Thus, what we really need is to represent $n! = p^t a$, where $\gcd(a, p)=1$, and then report $t$ and $a$ modulo $p^k$. This is sufficient to also compute $\binom{n}{r}$ modulo $p^k$. We will show that, ass...

Full text and comments »

CP Toolkit V2 UPDATE!! <hr /> CP TOOLKIT V2 NEW UPDATE!!! ================== This new update comes PACKED with a ton of new features, which I'll list below. Newly Added Core Features ------------------------- **Graph Editor** An intuitive editor where nodes move smoothly. Build and edit graphs with drag-and-drop interaction.  **Graph Generator** Generate Trees, Cactus Graphs, Complete Graphs, Connected Graphs, Planar Graphs, Forests, and more. Perfect for creating custom test cases.  **Big Integer Calculator** Handles large integer operations with full precision. Great for number theory problems.  **Array Visualizer** Cleanly displays 1D and 2D arrays. Automatically adjusts font size and cell spacing for large arrays.  **NTT-Friendly Prime Generator** Select primes of specific length and base. Browse from a list of 320,...

Full text and comments »

Nimbers and Sprague-Grundy theorem Hi everyone! Today I'd like to write about the so-called Grundy numbers, or nimbers. I will start by providing a formal recap on the Sprague-Grundy theorem and then will advance to the topic that is rarely covered in competitive programming resources, that is I will write about nimber product and its meaning to the game theory. _I was asked to add the following to the blog: THANK SIR MASTER [user:ADAM_GS,2022-06-12] FOR GREAT AND VALUABLE REVIEW SIR_ ## Prerequisites Familiarity with the following concepts: - Basic [set theory](https://en.wikipedia.org/wiki/Set_theory) notion: [union](https://en.wikipedia.org/wiki/Union_%28set_theory%29), [cartesian product](https://en.wikipedia.org/wiki/Cartesian_product) and [symmetric difference](https://en.wikipedia.org/wiki/Symmetric_difference) of sets, [set of all subsets](https://en.wikipedia.org/wiki/Power_set) denoted as $2^A$, etc; - [Groups](https://en.wikipedia.org/wiki/Group_%28mathematics%29) and [fields](https://en.wiki...

Full text and comments »

Asking for help FAQ What to do when you need help with a problem? 1. If there is an editorial, read it. If you don't know some technique, google it and read a tutorial. 2. Ask a friend for help. It's very useful to find someone in your university/country who also does competitive programming. 3. _"I'm getting WA and don't know why."_ Try to find a counter-test. Take an accepted code if it's available, and write a brute force otherwise. Test it against your solution on thousands of random tests, especially small ones. 4. _"My code doesn't work on this test."_ Use some debugging tools (google them for your OS/IDE) or just print values of everything you compute. I use gdb and valgrind. Simulate the program on paper too. This way you should find an exact place where something incorrect happens, or you will see that your approach is completely wrong. 5. _"The output differs on my machine and in Codeforces/anotherPlatform."_ It's likely "undefined behavior", e.g. you don't initialize a local...

Full text and comments »

Is Competitive Programming Slowly Dying? Am I right that CP is slowly dying? Today I got little rating bonus placing so high. For example, compare <a href="https://codeforces.me/contest/2084">Codeforces Round 1015 (Div. 1 + Div. 2)</a> with <a href="https://codeforces.me/contest/2237">today's round</a>. Back then, the performance of 38th place was <b><span style="color:black">3</span><span style="color:red">046</span></b>: <img src="/predownloaded/f4/3e/f43e1d65b15147c29191f32a071ee1db49122025.png"> Now, the performance of 38th place is only <b><span style="color:red">2862</span></b>: <img src="/predownloaded/d4/6b/d46be58bdc4a91cc1c65da9395b3eb153b87a282.png"> The performance of 2nd place back then was <b><span style="color:black">3</span><span style="color:red">980</span></b>: <img src="/predownloaded/6b/ab/6bab113152ef21889af2c54a81cdb4a8edeadaa9.png"> Now, the performance of 2nd place is only <b><span style="color:black">3</span><span style="color:red">660</span></b>: <img src="/predownload...

Full text and comments »

Operations on polynomials (on cp-algorithms) Hi there! During preparation of [Oleksandr Kulkov Contest 1](https://codeforces.me/blog/entry/65678) I started writing some template for polynomial algebra (because 3 problems in contest in one or another way required some polynomial operations). And with great pleasure I'd like to report that it resulted in [this article](https://cp-algorithms.com/algebra/polynomial.html) on [cp-algorithms.com](https://cp-algorithms.com) (English translation for e-maxx) and [this mini-library](https://github.com/e-maxx-eng/e-maxx-eng-aux/blob/master/src/polynomial.cpp) containing all mentioned operations and algorithms (except for Half-GCD algorithm). I won't say the code is super-optimized, but at least it's public, provides some baseline and is open for contribution if anyone would like to enhance it! Article also provides some algorithms I didn't mention before. Namely: - Interpolation: Now the described algorithm is $O(n \log^2 n)$ and not $O(n \log^3 n)$ as it was before. - Resultant...

Full text and comments »

Trick Bites: Daily CP Tricks & Video Upsolves Hello Codeforces! This is my very first blog post here, Lately I've been working on a series called **Trick Bites**. ### The Idea I wanted to share some special CP tricks. Some of them are uncommon but surprisingly easy (like Dinkelbach's algorithm), while others are just common tricks that everyone needs to know. I've started releasing a new problem every day to highlight a specific trick. With each problem, I upload a short, straight-to-the-point Arabic video explaining the trick and the optimal solution. ### Why this blog? I wanted to create this blog to be a permanent archive. I will be updating this exact post daily with the new problem links and video solutions. My hope is that by saving all this content in one organized place, it can become a useful resource for anyone looking to learn some tricks! --- ### The Trick Bites Archive (Updated Daily) [Group Link](https://codeforces.me/group/reRlOrZJrU/contests) *(I will update this list every day with the late...

Full text and comments »

New Era of CP: Introducing 1v1 Blitz Style Showdowns Hey CF Community, ================= Competitive Programming has always been a solo grind — countless hours of solving problems, climbing the rating ladder, and pushing your limits. But what if we made it more dynamic, personal, and real-time competitive? Introducing a new format that redefines the CP experience: **1v1 Blitz Style Showdowns**. #### What Is a Blitz Style Showdown? - A unique format where users can schedule a battle, and others from across the globe can join in. - Players can set a desired rating range to match with suitable opponents. - Both participants receive the same set of problems under a strict time constraint. - The blitz mechanism makes it even more intense — only one player can solve a problem. - Global leaderboard is created based on user performance(Currently Beta version). #### Features of Our Platform - **Solo Battles**: Practice in a contest-like environment with a time based point-decay system. - **Room Battles**: Compete with your C...

Full text and comments »

Codeforces Round 906 Editorial [problem:1890A] idea: [user:Cocoly1990,2023-10-28] <spoiler summary="Solution"> [tutorial:1890A] </spoiler> <spoiler summary="Code"> By [user:Cocoly1990,2023-10-28] ~~~~~cpp // Time complexity O(nlogn) because of map #include <bits/stdc++.h> const int MX = 100 + 5; int main() { int t; std::cin >> t; while (t--) { int n; std::cin >> n; std::map<int ,int> occ; for (int i = 1; i <= n; ++i) { int x; std::cin >> x; occ[x]++; } if (occ.size() >= 3) puts("No"); else { if (std::abs(occ.begin()->second - occ.rbegin()->second) <= 1) { puts("Yes"); } else { puts("No"); } } } return 0; } ~~~~~ </spoiler> [problem:1890B] idea: [user:Imakf,2023-10-28] <spoiler summary="Solution"> [tutorial:1890B] </spoiler> <spoiler summary="Code"> By [user:Imakf,2023-10-28] ~~~~~cpp #include <bits/stdc++.h> bool ok(std::string s) { for ...

Full text and comments »

The Intuition Behind NIM and Grundy Numbers in Combinatorial Game Theory There are already many wonderful resources online for learning the basics to combinatorial game theory, but the intention I have for _this_ guide in particular is to try to make them more intuitive. Why does XOR work for Nim? Why does mex produce the Grundy numbers? When it was taught to me, it was more or less just as 'magic' to memorize, but now I think I have a decent understanding of why they are true, so now that I have a grasp of the intuition behind it, I decided I should record my thoughts into a blog. Nim games ================== Suppose we are playing a Nim game. As we know, Nim games usually follow this sort of template: - There are $n$ piles of stones, and each pile contains $p_1, p_2, p_3, \cdots p_n$ stones, where each of the $p_i$ is some nonnegative integer. This collection of piles defines our game state. - There are two players who take turns removing stones. The current turn player may remove as many stones as they wish, so long as all the stones come f...

Full text and comments »

I'm Geothermal. AMA! After reaching 3200 in yesterday's contest, now feels like as good a time as any to hop on this bandwagon. Feel free to ask questions in the comments and I'll respond to as many as I can. A few sidenotes: ### Thoughts on Practicing In my streams, by far the most common questions I receive are variants of "how can I improve at competitive programming?" I'm happy to offer advice if people have specific questions about training related to their particular circumstances, but I wanted to write down some general thoughts so that I can redirect people who ask about general practice strategies (in this AMA or in my future streams) to this post. I endorse most of the advice given [at this link](https://github.com/Errichto/youtube/wiki/How-to-practice%3F). In short, I recommend solving problems around or slightly above your skill level (I like to go to [clist.by](https://clist.by/problems/) and choose Codeforces problems with luck between around 25% and 75%). If you run out of id...

Full text and comments »

[Tutorial] Amogus Trick omg hi Codeforces! I've been meaning to write a blog about this interesting, but not (as far as I know) documented trick for a while. I've decided to call it the Amogus trick after the first problem where I encountered and used it. Prerequisites ------------------ - [DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html) - Basic knowledge of [2-SAT](https://cp-algorithms.com/graph/2SAT.html) (definitely not required, but it may make the blog easier to understand) Focus Problem: [problem:1594D] ------------------ First, let's solve an easier version of this problem, where we just need to find whether there exists a configuration of player roles (i.e. Crewmate or Imposter) such that all the statements made by players so far are true. Let's look at the two different types of statements made by players separately. - **Case 1: Player $i$ claims Player $j$ is a crewmate.** Now, if Player $i$ is a crewmate, Player $j$ will also be a crewmate. Similarly, ...

Full text and comments »

[Tutorial/Parody] How to practice basic topic in CP (Episode 1) Not long ago [user:ToxicPie9,2023-01-11] posted a <a href = "https://codeforces.cc/blog/entry/111254">blog</a> explaining common mistakes in competitive programming and how to avoid them. I was greatly inspired by that post so I decided to write an episode on my own. Today I will mention four topics that I learned why practicing Competitive Programming and I will also mention how to build them. Also, in most cases, I will give you a chance to find out what the hard part is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in Python as it is the most **powerful** language for CP. #### Segment trees Definition: <spoiler summary="Click me"> A Segment Tree is a data structure that stores information about array intervals as a tree. This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array. This includes finding the sum of...

Full text and comments »

IOI 2018 impressions and conclusions Hi there! As you all are aware, IOI 2018 is now over, and I felt the need to write a few lines about it, about my experience of it, and about my conclusions. I don't normally do that, but this was my last IOI and likely the end of my intense CP career. So, the problems were absolutely great! Big up to the scientific committee. However, I'm sort of addicted to the codeblocks debugger which ruined the whole experience for me. As a matter of fact, the only reason for which codeblocks remained my primary editor was because its debugger was awesome and the only alternative of a better editor that I saw (better on the long run, including future real-life programming experience) would be vim which I knew is not even close to as friendly when it comes to user friendliness of debugging. I've also had competitions on a regular basis for 7 years and never had a time interval where I could say: well let's try something new cause we don't have anything useful to do (as I would always tell mys...

Full text and comments »

[Tutorial] Fully Dynamic Trees Supporting Path/Subtree Aggregates and Lazy Path/Subtree Updates Hey everyone! Usually when I post stuff on CF I just drop an external link to my blog, but this time I would like to also paste the same content natively on CF to see if it leads to more engagement. You can read the exact same article on my blog [here](https://mzhang2021.github.io/cp-blog/ds5/). Also, special thanks to [user:alien_lover,2022-06-10] and [user:gabrielwu,2022-06-10] for proofreading. --- ## Motivation We will solve **[this problem](https://dmoj.ca/problem/ds5)**. ## Prologue The original name of this problem is [SONE1](https://darkbzoj.cc/problem/3153), originating from the fiery depths of Chinese OI. Amazingly, the Chinese have figured out how to augment the link/cut tree to solve this problem (ref [1](https://www.cnblogs.com/clrs97/p/4403244.html), [2](https://blog.csdn.net/iamzky/article/details/43494481)). Maintaining subtree aggregates with a LCT isn't difficult, and there's a well-known [Codeforces article](https://codeforces.me/blog/entry/67637) ...

Full text and comments »

Competitive Programming in the Era of AI **Read the original post on :** https://www.vibhaas.net/posts/Competitive-Programming-in-the-era-of-AI/ <br> <div align="center"> <img src="/predownloaded/3e/ae/3eaee0e93cf1784ab4923157729c81dd3a080fcf.jpg" alt="Wanderer above the Sea of Fog, Caspar David Friedrich" width="70%"> <br> <small><i>Wanderer above the Sea of Fog, Caspar David Friedrich</i></small> </div> <blockquote> Picture this. You've had a draining week at university or at work. You're exhausted, and you need a break. Most people would play a few video games, grab a few beers with their friends, or just sleep. But you have the (mis?)-fortune of being addicted to this weird, aesthetically questionable website called Codeforces (or AtCoder, or whatever your favorite OJ is). </blockquote> <blockquote> You check the list of upcoming contests, and you're in luck. "Nice," you think to yourself, "two rated contests back to back!" This is going to allow you to farm some rating! ...

Full text and comments »

CP Editor 3.2 : CP Editor meets Competitive Companion Check : https://cpeditor.github.io ================== Hi Guys ! You guys are truly amazing. I created CP Editor around 3 months ago just for fun and personal use, never wanted to make it public but anyways, I decided to make it public with [this blog](https://codeforces.me/blog/entry/71673). I got so much love and support that I could not hold myself back from improving it, in following weeks I released the second version in [this blog](https://codeforces.me/blog/entry/71907). Fixing a lot of issues and bringing new features. Let's get into what is new in this release of CP Editor. But first, #### Merry Christmas programmers!! Thanks to [user:ouuan,2019-12-25] for his wonderful contributions. Almost all new features were implemented by him. #### What's New - [**NEW**] Save and restore Input and Expected outputs. Highly requested by [user:IWanna_MightiestDisciple,2019-12-25] [user:ekalavya_k_k_p,2019-12-25] [user:smile_,2019-12-25] [user:Double_Helix,2019-12-25]) ...

Full text and comments »

CSES Range Queries section editorial **UPD:** some video editorials on range query data structures: [youtubePlaylist](https://www.youtube.com/playlist?list=PLb3g_Z8nEv1isaHPaXL1j-pSo60812JtY) Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.me/blog/entry/70018. Quoting [user:icecuber,2020-05-09] "I think [CSES](https://cses.fi/problemset/) is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES." So here I am writing an editorial for the range queries section. If you find any error or maybe have a better solution to some problem please do share. Range Sum Queries I =...

Full text and comments »

CP-31 Sheet by TLE Eliminators | Handpicked Problems from 800 to 1900 Rating Hi folks! I have created a list of 31 problems in each rating from 800 to 1900 with nice reusable concepts. Link to the sheet: https://www.tle-eliminators.com/cp-sheet #### Who Am I? <spoiler summary=""> - My name is Priyansh Agarwal. I have been in this space for 5+ years. I have solved 4k+ programming problems on online judges. I am an [ICPC World Finalist](https://x.com/Priyansh_31Dec/status/1782293445723488287) and have secured [Rank 6 in a Google Kick Start round](https://x.com/Priyansh_31Dec/status/1505416520595173377). - I have created a lot of CP tutorials on my [Youtube channel 70k+](https://www.youtube.com/@PriyanshAgarwal) and [TLE's Youtube channel 35k+](https://www.youtube.com/@TLE_Eliminators) where we have posted 300+ post contest discussions of contests from Codeforces, Codechef and Leetcode to help people upsolve contests. - I have been running a competitive programming training for beginners called TLE Eliminators for the last 4 years, where we've taught 1...

Full text and comments »

Codeforces Round #573 What do you do on Friday evening? Are you busy? Will you take part in our round? Hello, Codeforces! We are glad to invite you to take part in [contest:1190] and [contest:1191], which will be held on [contest_time:1190]. The round will be **rated** for all participants from both divisions.Participants in each division will be offered **6** problems and **2** hours (to be determined) to solve them. Both divisions will share 4 problems. The problems were written and prepared by [user:2014CAIS01,2019-05-16], [user:tender,2019-05-16], [user:teitoku,2019-05-16], [user:winterzz1,2019-05-16], [user:chenjb,2019-05-16], [user:Subconscious,2019-07-09], [user:Claris,2019-05-16], [user:quailty,2019-05-16], [user:skywalkert,2018-11-01] and me. Thank to: - [user:tender,2019-05-16] for providing stories for some problems. - [user:skywalkert,2018-11-01], [user:Claris,2019-05-16], [user:quailty,2019-05-16], [user:WhaleVomit,2019-07-12], [user:NIWIS,2019-07-12], [user:Intrincantatio...

Full text and comments »