The $\texttt{lower_bound}$ function finds the first position where a value could be inserted in without breaking sorter order. Its time complexity is $\texttt{O(log n)}$. For example: $\texttt{it}$ refers to the address of the value. $\texttt{*it}$ refers to the value, and to get the index, use $\texttt{it-v.begin()}$.
Chase
Lemma Inequality For The Sum of Cubes of Two Terms
Lemma. If $a, b \geq 0$, then $a^3 +b^3 \geq a^2 b + a b ^ 2$. Proof. Since $a,b\geq 0$, $a+b\geq 0$. Also, by the trivial inequality, $(a-b)^2 \geq 0$. Thus, $(a-b)^2 (a+b)\geq 0$. Expanding, $a^3 + b^3 – a^2 b – a b^2 \geq 0$. So, $a^3 +…
Math Formulas
$(a-b)^3=a^3-3a^2 b+3a b^2-b^3$ (remember the 3’s) $(a+b)^3=a^3+3a^2 b+3a b^2+b^3$ (remember the 3’s) $1^2 + 2^2 + … + n^2 = \frac{n(n+1)(2n+1)}{6}$ $1^3 + 2^3 + … + n^3 = \frac{n^2 (n+1)^2}{4}$ $\sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6}$ For an $m \times n$ grid of numbers satisfying: let $a_{i,j}$ = the entry in…
Arithmetic Sequence Problem
If $p, q$ are distinct natural numbers, and in an arithmetic sequence {${a_n}$}, $S_p = S_q$, where $S_k$ denotes the sum of the first $k$ terms of the sequence {${a_n}$}. Prove that $S_{p+q}=0$. The formula for an arithmetic series is $S_n = n a_1 + \frac{n(n-1)}{2}d$. So, $S_p = p a_1+ \frac{p(p-1)}{2}d$ and $S_q = q a_1+ \frac{q(q-1)}{2}d$. Since $S_p…
CMOQR 2026 P3
Problem: Let point $P$ be outside circle $\Gamma$. The tangents from $P$ to $\Gamma$ hit $\Gamma$ at $A$ and $B$. A third line through $P$ hits $\Gamma$ at $C$ and $D$, such that $C$ is between $P$ and $D$. Point $Q$ is on chord $CD$ such that $\angle DAQ$ =…
Diameter And Radius Of A Tree
In Graph Theory, the diameter of a tree is the largest distance between any two points. The radius is the minimum distance of the maximum distance of any node on the of the diameter to one of the two diameter endpoints. Take the following graph as an example. In this…
Dijkstra Code
Dijkstra’s algorithm is a method to calculate the shortest path from one node to another with weighted edges. It does not work for negative edge weights, however. Fun fact: it is a main algorithm used in Google Maps. It starts off by setting all the distances of each node to…