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

Recently, I retired from competitive programming completely, and I found myself wondering about what I’ll do with all the competitive-programming-specific knowledge I have gained over the years. For quite some time, I’ve been thinking of giving back to the community by writing about some obscure topics that not a lot of people know about but are super interesting. However, every time I ended up with ideas that are either too obscure to be feasibly used in a competitive programming problem, too technical to ever be seen in a contest, or having too many good posts/articles about them anyway. ...

This post was initially meant to request updates to the C compiler on Codeforces (given the large number of posts complaining about “mysterious” issues in their submissions in C). While writing it, I realized that the chances of the said updates would be higher if I mentioned a few reasons why people would like to code in C instead of C++ (some of the reasons are not completely serious, as should be evident from the context). ...

Since someone recently asked me about my competitive programming setup, and I like tinkering with my setup to make it as useful and minimal as possible, I thought I should share my setup that I’ve used for the past few years and a modified version that I’ve used at onsite ICPC contests. I’ve also talked to a few people who went to IOI and had a similar setup, and I’m fairly confident that at least some people will be able to successfully use this without having to worry too much about the details, like I did. This is definitely NOT the only way to set up a basic environment, but it was the way that worked for me for quite a long time. ...

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 was written jointly by errorgorn and me and published on errorgorn’s blog, and the original post is here. You can also check out his personal blog here. Hi everyone! Today nor sir and I would like to talk about generating uniform bracket sequences. Over the past few years when preparing test cases, I have had to generate a uniform bracket sequence a few times. Unfortunately I could not figure out how, so I would like to write a post about this now. Hopefully this post would be useful to future problem setters :) Scroll down to the end of the post to copy our generators. ...

We ended up making a meme contest, here’s the editorial for the contest. The original editorial is here. Thank you for participating in this round! We hope you found the problems interesting and/or funny. Special thanks to dorijanlendvaj for helping with Polygon related issues. Preparing good tests for certain problems was in fact a good problem in itself (in fact, sometimes they were hard enough for usual CF rounds), and we will mention these problems for the interested reader. ...

We ended up making a meme contest, here’s the announcement for the contest; the original announcement is here. Hi Codeforces! We are pleased to invite you to [contest:383377], which will take place on [contest_time:383377]. You will be given 9 problems and 2 hours to solve them. Please follow this link in order to register for the contest. Note that this contest is not an official Codeforces round. The round will be unrated for all participants. It will be held according to modified ICPC rules. ...

This post will be more about developing ideas about certain structures rather than actually coding up stuff. The ideas we’ll be developing here have many applications, some of which involve: Number Theoretic Möbius Inversion Principle of Inclusion-Exclusion Directed Acylic Graphs Subset Sum Convolution Finite Difference Calculus (and prefix sums) Note that some of the terminology used below might be non-standard. Also, some parts of the post make a reference to abstract algebra without much explanation; such parts are just for people who know some algebra, and can safely be skipped by those who don’t know those concepts at all. ...

As a certain legendary grandmaster once said (paraphrased), if you know obscure techniques and are not red yet, go and learn binary search. The main aim of this tutorial is to collect and explain some ideas that are related to binary search, and collect some great tutorials/blogs/comments that explain related things. I haven’t found a comprehensive tutorial for binary search that also explains some intuition about how to get your own implementation right with invariants, as well as some language features for binary search, so I felt like I should write something that covers most of what I know about binary search. ...