Posts

This post was originally written on Codeforces; relevant discussion can be found here. Introduction A lot of people shy away from solving (mathematical) recurrences just because the theory is not very clear/approachable due to not having an advanced background in math. As a consequence, the usual ways of solving recurrences tend to be: Find the first few terms on OEIS. Guess terms from the rate of growth of the recurrence (exponential rate of growth means you can sometimes estimate the exponential terms going from largest to smallest — though this fails in cases where there is a double-root of the characteristic equation) Use some theorem whose validity you can’t prove (the so-called characteristic equation method) Overkill using generating functions But this doesn’t have to be the case, because there is a nice method you can apply to solve equations reliably. I independently came up with this method back when I was in middle school, and surprisingly a lot of people have no idea that you can solve recurrences like this. ...

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. However, these ad hoc solutions often require some guessing and the Master theorem is not directly applicable. ...

This post was originally written on Codeforces; relevant discussion can be found here. Disclaimer: This post (and all of my other posts, unless specified otherwise) is 100% ChatGPT-free — there has been no use of any AI/ML-based application while coming up with the content of this post. The reason and an appeal There is a lot of AI-generated content out there these days that sounds plausible and useful but is absolute garbage and contributes nothing beyond a list of superficial sentences — even if it has content that is true (which is a big IF, by the way), it generates content that you could have just looked up on your favorite search engine. The reason why such current AI-generated content is like this is multi-fold, but I won’t get into it because I need to write the content of this post, too, and I don’t see copy-pasting this kind of content as anything but a stupid maneuver that wastes everyone’s time. ...

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. So, it would be really cool if someone could prove this property. ...

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. But i++ has its own place, and I use it — and the generalization I mention — quite frequently wherever it is a sane choice. ...

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). On some compilers, passing -Wl,--stack=268435456 to the compiler options should give you a 256MB stack. ...

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

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