Tutorial

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. Of course, even though we will treat these approaches separately (though not so much for the last two approaches), in many problems, you might need to use multiple approaches at the same time and maybe even something completely new. Usually, you’d use these ideas in conjunction with something like greedy/DP after you realize the underlying setup. ...

This post was originally written on Codeforces; relevant discussion can be found here. Disclaimer: This is not an introduction to greedy algorithms. Rather, it is only a way to formalize and internalize certain patterns that crop up while solving problems that can be solved using a greedy algorithm. Note for beginners: If you’re uncomfortable with proving the correctness of greedy algorithms, I would refer you to this tutorial that describes two common ways of proving correctness — “greedy stays ahead” and “exchange arguments”. For examples of such arguments, I would recommend trying to prove the correctness of standard greedy algorithms (such as choosing events to maximize number of non-overlapping events, Kruskal’s algorithm, binary representation of an integer) using these methods, and using your favourite search engine to look up more examples. ...

This post was originally written on Codeforces; relevant discussion can be found here. Recently someone asked me to explain how to solve a couple of problems which went like this: “Find the expected time before XYZ happens”. Note that here the time to completion is a random variable, and in probability theory, such random variables are called “stopping times” for obvious reasons. It turned out that these problems were solvable using something called martingales which are random processes with nice invariants and a ton of properties. ...

This post was originally written on Codeforces; relevant discussion can be found here. Introduction A while ago ToxicPie9 and I made and posted this meme: To my surprise, many people are quite confused about it. In fact, I realized there are a lot of misconceptions about pragmas. Most C++ users on Codeforces put a few lines of pragmas at the start of every submission. However, I believe many of them don’t fully understand what they’re doing or how pragmas work; the only thing people seem to think is that “add pragmas -> code go brr”. ...