I believe that adding the Boost library on Codeforces would be a great addition for C++ competitive programmers. AtCoder already supports it (alongside GMP and Eigen, but Boost has replacements/wrappers for those: Boost.Multiprecision and Boost.uBLAS). CodeChef supports it too (or at least used to support it at some point, not sure now). I’ve seen at least 3 posts by people trying to use Boost on Codeforces and failing, and on thinking about it, I couldn’t really come up with a good reason (in my opinion) that Boost should not be supported on Codeforces. ...

Disclaimer: Please verify that whichever of the following solutions you choose to use indeed increases the stack limit for the execution of the solution, since different OSes/versions can behave differently. On Linux (and probably MacOS), running ulimit -s unlimited in every instance of the shell you use to execute your program will work just fine (assuming you don’t have a hard limit). On some compilers, passing -Wl,--stack=268435456 to the compiler options should give you a 256MB stack. ...

TL;DR The Floyd-Warshall algorithm is a special case of the more general case of aggregation over paths in a graph — in this post, we look at a few examples and point to some references for further study. The algebraic path problem constitutes a family of problems that can be solved using similar techniques. This and this paper develop the theory of semirings in this context, and this treats some computational aspects of it. Kleene algebras are what end up being used in most of the examples given here, but semirings are more general structures. While not discussed in the post, the idea of a valuation algebra is a further generalization that shows connections to more problems of various types. Introduction Most people doing competitive programming who learn about the Floyd-Warshall algorithm learn it in the context of computing the lengths of the shortest paths between all pairs of vertices in a graph on \(n\) vertices in \(O(n^3)\), which is better than naively running Dijkstra or other kinds of shortest-path algorithms (other than Johnson’s algorithm for the sparse case), and can also identify negative cycles. ...

It’s been about 5 years since the round took place, and since there was no editorial all this time, I decided to write one myself. Thanks to tfg for discussing problem F with me and coming up with the permutation interpretation that makes it much easier to reason about the problem. The idea in F was also inspired by other submissions. 1060A Hints/intuition Think about two cases: when there are very few 8s, and when there are a lot of 8s. ...

There were a few instances on CF according to which it seems that quite a few people aren’t very comfortable with floor and ceiling functions (and inequalities in general) — for instance, here and here. This inspired me to write a hopefully short post on how to systematically work with these topics. Note that I will not define what a real number is, or do anything that seems too non-elementary. Also, for the foundational stuff, I will rely on some correct intuition rather than rigour to build basic ideas, and the systematic logically correct way of reasoning will be used later. The idea behind this post is to just help you understand how to reason about the topics we’ll cover. ...

As was noted in this post, Google decided to discontinue its programming contests (Code Jam, Kick Start and Hash Code). It seems they will take down all relevant servers (and hence the problems and the submission system) for all these contests. While there are some initiatives to archive past Code Jam and Kick Start problems (for example, here — also have a look at this comment), there seems to be nothing similar for Hash Code. ...

Disclaimer: I am not an expert in the field of the psychology of learning and problem-solving, so take the following with a grain of salt. There is not much “scientific” evidence for this post, and the following is validated by personal experience and the experiences of people I know (who fall everywhere on the “success” spectrum — from greys to reds in competitive programming, from beginners in math to IMO gold medalists, and from people with zero research experience to people with monumental publications for their own fields). This post only covers one possible way of thinking about knowledge organization and retrieval that I have been using for the past decade or so, but there definitely will be other models that might work even better. Even though I just have a few courses worth of formal psychology experience, I still think the content of this post should be relevant to people involved with problem-solving. ...

Firstly, the CF Catalog is a great feature that makes it much easier to learn topics by having a lot of educational content in the same place, so thanks MikeMirzayanov! I was originally going to post this as a comment under the catalog announcement post, but it became too large for a single comment, and it will probably need some more discussion. I want to suggest the following improvements for the catalog (and initiate a discussion on how best to tackle these issues with the current version): ...

People often say C++ is much more cumbersome to write than any sane language should be, but I think that is mainly due to lack of knowledge about how to write modern C++ code. Here’s how you can write code more smartly and succinctly in C++(20): Negative indexing with end Have you ever found yourself using a vector like a stack just because you have to also access the last few positions, or writing a sliding window code using a deque (where the size might be variable, but you want to access an element at some offset from the end)? ...

This post is intended to be an introduction to permutations for beginners, as there seem to be no resources other than cryptic (for beginners) editorials that talk about some cycles/composition, and people unfamiliar with permutations are left wondering what those things are. We’ll break the post into three major parts based on how we most commonly look at permutations. Of course, even though we will treat these approaches separately (though not so much for the last two approaches), in many problems, you might need to use multiple approaches at the same time and maybe even something completely new. Usually, you’d use these ideas in conjunction with something like greedy/DP after you realize the underlying setup. ...