Math

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

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

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

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

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