Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### -is-this-fft-'s blog

By -is-this-fft-, history, 8 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?

• +54

 » 8 months ago, # | ← Rev. 4 →   0 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
•  » » 8 months ago, # ^ |   0 Can you prove even that this solution produces maximal length, without using ideas from real solution?
 » 8 months ago, # |   -16 1073D - Berland Fair brute force solution is correct because given cost reduces very fast on every iteration.
 » 8 months ago, # |   +34 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.
•  » » 8 months ago, # ^ |   0 For example this one: https://codeforces.com/problemset/problem/559/D