Once upon a time, years before I joined the platform, I came across this problem:

Problem: What is the fewest number of marks that one needs to inscribe on a ruler so that any distance from $1,2,\ldots,n$ can be measured?

Since $m$ marks can only measure $\binom{m}{2}$ distinct distances, we clearly need at least $O(\sqrt{n})$ marks to measure all distances from $1$ to $n$. Now if $b=\lceil{\sqrt{n}\rceil}$ and we mark the ruler at locations

then all the distances up until $b^2+b-1 > n$ are represented, using only $2b = O(\sqrt{n})$ marks.

Therefore, the answer to this problem is asymptotically $O(\sqrt{n})$. And this is how I learned about Square Root Decomposition, the first topic I'd ever encounter in the vast world of programming contests.

A related concept are the golomb rulers, the smallest rulers for which all $\binom m2$ distances between marks are different. Though they don't necessarily need to cover all distances $1,2,\ldots,n$, the best rulers will have most of these small distances. For instance, marking a length-$11$ ruler at $0$, $2$, $7$, $8$, and $11$ gives us the pairwise distinct distances of $1,2,\ldots,9$ and $11$, which is optimal.

So, in early April 2024, I registered as "golomb," and so far, it has been a blast.