The Online Math Club Blog

 Dynamic Programming is one of the most popular techniques in competitive programming and a powerful algorithm design technique. This handout aims to give a brief introduction to Dynamic Programming. Optimization Algorithms An algorithm is a set of steps to perform a certain procedure and reach a certain end goal. In particular, the problems we are going to be looking at in this handout are going to be optimization problems - problems that aim at minimising or maximising something, finding a shortest path, or trying to find the best way to do something. Greedy Algorithms Greedy algorithms are used to solve optimisation problems which try to maximise short term goals by making decisions that seem to be optimal in the current scenario but may not be ideal in the long run.  Example 1( Activity Selection Problem) :  On a certain day, there are $n$ events that you would like to attend. Each of these events has a start time $s_i$ and a finish time $f_i$. Some of these eve...

Hi all! I'm Kelin, a rising 11th grade student from the US. I've been studying Olympiad math for more than 2 years now, and although I'm mostly retired, I still find Olympiad problems beautiful and I'm always down to share my favorite concepts with other math enthusiasts. In my spare time, I'm getting acquainted with competitive programming and higher math. Combinatorics is my favorite math contest subject since it's easy to get started with. It requires no heavy theory, and difficult combinatorics problems usually embody brilliant ideas. I will began my post with a folklore problem: On a 1-meter stick, 1000 ants start at different positions, each moving at 1 meter per second and towards the left or the right. Every time two ants collide, they each reverse their orientations. What's the longest that any ant can remain on the stick? If you've never seen this one before, please try it out for a few moments before proceeding, even if you are a beginner. It...

Recurrence Relation : A recurrence relation is a formula or rule by which each term of a sequence can be determined using one or more of the earlier terms. Problem 1:  For each of the following sequences find a recurrence pattern. a. $1,10,100,\dots $ b. $1,3,6,10,\dots $ c. $1,2,6,24,120,\dots $ d. $1,1,2,3,5,8,13,\dots$ e. $0,1,9,44, 265, \dots $ Solution:  a. $$a_n=10\cdot a_{n-1}$$ b. $$a_n=a_{n-1}+n$$ c. $$a_n=n\cdot a_{n-1}$$ d. This is the  Fibonacci sequence . We have $$F_0=1,F_1=1, F_2=2,\dots F_n=F_{n-1}+F_{n-2}$$ e. This is the  derangement number . We have $$ D_n= n \cdot D_{n-1}+(-1)^n.$$ We also have $$D_n=(n-1)(D_{n-1}+D_{n-2})$$ The Stamp problem:   Suppose we have $1,2,5$ stamps. The problem is to find the number of ways these can be arranged in a row so that they can add up to a given value $n.$ Solution:  Let $a_n$ be the number of ways the stamp can add up to $n.$ Then we have three cases considering the value of the last stamp.  Ca...

This blog can be divided into two parts: In the first part, I would be talking about some basic but useful $\log n$-ish algorithms, and later I would be discussing some construction-based problems whose solution exploits the binary representation of numbers. Both parts can be read independently too. Let's get started... For completeness, I define what is an algorithm: A finite sequence of well-defined mathematical or logical steps that when followed would yield an answer to a class of similar problems or a computation. Iteration and Recursion lie at the core of any algorithm. The time complexity of an algorithm is an estimate of how the number of steps in the algorithm grows as the input increases. So we say an algorithm is $O(n)$ if the number of steps in it is bounded above by $cn$ for some $c$.And similarly, you understand $O(\log n)$,$O(n^2)$,etc. The main purpose of an algorithm is to shorten the number of steps or the memory used in the otherwise brute-force or naive approa...