Tutorial

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

I first got to know about the existence of RSS feeds back when I was in middle school, but didn’t figure out their appeal and promptly forgot about them. Fast-forward to around a year ago - I was starting to realize that I was reading way too many interesting tech blogs, so I set out to find a way to aggregate all these updates together. A quick search later, it seemed like RSS feeds were the perfect fit for the job....

This post was originally written on Codeforces; relevant discussion can be found here. TL;DR Use the following template (C++20) for efficient and near-optimal binary search (in terms of number of queries) on floating point numbers. Template template <std::size_t N_BITS> using int_least_t = std::conditional_t< N_BITS <= 8, std::uint8_t, std::conditional_t< N_BITS <= 16, std::uint16_t, std::conditional_t< N_BITS <= 32, std::uint32_t, std::conditional_t< N_BITS <= 64, std::uint64_t, std::conditional_t<N_BITS <= 128, __uint128_t, void>>>>>; // this should work for float and doubles, but for long doubles, std::bit_cast will fail on most systems due to being 80 bits wide....

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

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

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