Codeburners

Pigeon Hole Principle On account that I have been seeing a lot of pigeon hole lately (not only in competitive), I’m making this to explain some techniques that you can use to deal with pigeon hole. Now pigeon hole does not come up super often, but it is a concept that anyone should be familiar with. It’s also necessary in some harder probability problems.

Dynamic programming (DP) is an absolutely necessary skill to have in competitive programming. Pretty much every ICPC contest that I've participated in has at least one problem needing DP, though most of the time there are multiple. A lot of you probably have heard of it, but aren't completely sure how to use it to solve problems. I'll be explaining what exactly DP is and how you can implement it.

I'd like to say that I didn't write this blog on my own. Topcoder's  similar post  served as an inspiration and  the handbook  showed me some really interesting ways to implement binary search. Hopefully this gives you more insight into how to apply binary search to problems as well as how to know if binary search is applicable.