Competitive-Programming

The other day I had a discussion with someone about how to implement FFT-based convolution/polynomial multiplication - they were having a hard time squeezing their library implementation into the time limit on this problem, and it soon turned into a discussion on how to optimize it as much as possible. It turned out that the bit-reversing part of their iterative implementation was taking a pretty large amount of time, so I suggested not using bit-reversal at all, as is done in a few libraries....

This post was originally written on Codeforces; relevant discussion can be found here. Someone asked me about my template that used a “cache wrapper” for lambdas, so I decided to write a post explaining how it works. For reference, here is a submission of mine from 2021 that uses that template. Here’s what you will find implementations for in this post: Generalized hashing (for tuple types, sequence types and basic types) Convenient aliases for policy based data structures Wrappers for recursive (or otherwise) lambdas that automatically do caching (memoization) for you....

This post was originally written on Codeforces; relevant discussion can be found here. Motivation On a computer science discord server, someone recently asked the following question: Is the master theorem applicable for the following recurrence? \(T(n) = 7T(\lfloor n / 20 \rfloor) + 2T(\lfloor n / 8 \rfloor) + n\) There was some discussion related to how \(T\) is monotonically increasing (which is hard to prove), and then someone claimed that there is a solution using induction for a better bound....

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. 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. 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....

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