Many problems require us to deal to dense graphs. I’ll discuss a general technique on how to solve such problems in sub-quadratic time. While this isn’t anything mind-boggling, I find this technique to be extremely useful and surprisingly less-known among competitive programmers.

A few months ago, Mamnoon and I started writing a book on Dynamic Programming. We decided that our book will be super-comprehensive: it will cover everything from Fibonacci numbers to generating functions to dp optimizations.

I found this at CSPrep from Tao Genna. At first glance, this looks like a typical constructive algorithm problem.: we have to provide the construction of a set from some information given about it. Here is the abridged problem statement.

I solved this problem on POI a while back, and I felt the ideas used in this problem are quite versatile. I was so intrigued by this problem that I decided to write a short summary of my intuitions and motivations in the solving process. A little bit of knowledge on linear transformations and matrices will be necassary.

Hi, I am Tasmeem Reza. You may know me as Bruteforceman, which is the alias I use in most programming contests. I have been doing competitive programming for more than five years.