As one can easily guess, this blog is about a mental model of thought. I chose to write about it since I feel that introspection about ways of thinking (and consequently what “thinking before doing something” means) is greatly lacking among people, and that it is critical to make better decisions (and realizing when there is no “better” decision). I won’t bore you with the philosophical details, so I’ll approach it from a probabilistic perspective, which is closer to what I personally choose to think in terms of....
This is a collection of my thoughts on AI and problem-solving, which have remained relatively constant over the past few years, and some comments on recent efforts in this direction. Recently, Deepmind claimed that they had made significant progress on the IMO Grand Challenge, and their automated systems called AlphaProof and the buffed version of their original AlphaGeometry, called AlphaGeometry 2 now perform at the IMO silver level. Having monitored this field in the past on-and-off, this set off some flags in my head, so I read through the whole post here, as well as the Zulip discussion on the same here....
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. As of May 2024, the bug has been fixed in GCC 14, but has not been ported to Codeforces yet. MikeMirzayanov added a new compiler in response to the bug mentioned here. However, it does not come without a catch. Namely, any pragma that is of the form #pragma GCC target(...) would NOT work with this new compiler....
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. 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....