-is-this-fft-'s blog

By -is-this-fft-, history, 4 months ago, , Sometimes we see problems where a seemingly naive algorithm — for example simple brute force — is actually the correct solution. Mostly, I mean problems where, due to some clever observations, the complexity of the brute force algorithm is greatly reduced.

For example, in a recent contest we had 1168B - Good Triple. You can notice that any string of length at least 9 contains a "good triple", which means a brute force is sufficient here and runs in $O(n)$.

Or 1028F - Make Symmetrical where you can notice that on any given circle, there are not too many lattice points.

Randomized input is also a good source of these. In 896C - Willem, Chtholly and Seniorious you can observe that after a bit of time, most adjacent elements of the array are equal and write something seemingly naive based on that.

What are some other examples of problems where a stupid brute force is actually the correct solution? Comments (5)
 » 4 months ago, # | ← Rev. 4 →   my code complexity was $O(2^{2n})$ which passed fast because it finds next number with low number of iterations so actual runtime of the code wasn't slow
•  » » Can you prove even that this solution produces maximal length, without using ideas from real solution?
 » 1073D - Берляндская ярмарка brute force solution is correct because given cost reduces very fast on every iteration.
 » It often happens in problems where you need to print the answer with some precision. If something is unlikely to happen, don't compute it.
•  » » For example this one: https://codeforces.com/problemset/problem/559/D