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.