Math

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