This post was originally written on Codeforces; relevant discussion can be found here. This post is not about the binary GCD algorithm, but rather about exploring theoretical guarantees for an optimization on top of the standard Euclidean algorithm. The STL version is faster than both these algorithms, because it uses the binary GCD algorithm, but these algorithms are of interest from theoretical considerations. In particular, my conjecture is that the second algorithm takes at most as many iterations as the first one, and if true, it’d be a pretty surprising claim, given how hard it is to bound Euclidean algorithm runtimes....

This post was originally written on Codeforces; some relevant discussion can be found here. Note: for those who don’t like using the post-increment operator (i++), hopefully this post convinces you that it is not just a convention that C programmers coaxed the world into following out of tradition. Also, all of the following discusses the increment operators in C++, and not C, where the semantics are slightly different. Disclaimer: I use ++i much more often in code....

This post was originally written as a feature request for Codeforces; some relevant discussion can be found here. 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....

This post was originally written on Codeforces; relevant discussion can be found here. 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)....

This post was originally written on Codeforces; relevant discussion can be found here. 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....

This post was originally written on Codeforces; relevant discussion can be found here. 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....

This post was originally written on Codeforces; relevant discussion can be found here. 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....

This post was originally written on Codeforces; relevant discussion can be found here. 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....

This post was originally written on Codeforces; relevant discussion can be found here. 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 was originally written on Codeforces; relevant discussion can be found here. 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....