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

By -is-this-fft-, history, 2 years 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

 » 2 years 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
•  » » 2 years ago, # ^ |   0 Can you prove even that this solution produces maximal length, without using ideas from real solution?
 » 2 years ago, # |   -16 1073D - Berland Fair brute force solution is correct because given cost reduces very fast on every iteration.
 » 2 years 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.
•  » » 2 years ago, # ^ |   0 For example this one: https://codeforces.com/problemset/problem/559/D
 » 15 months ago, # |   -29 Intersting. For example any div2A problem.
 » 15 months ago, # | ← Rev. 2 →   0 https://www.codechef.com/GW19MOS/problems/MEANPROBThis is from a ICPC regional. The bruteforce algorithm works
 » 15 months ago, # |   +15 Problems about merging small sets to large sets Tree DP in $O(nk)$ time by iterating only until $min(subtreeSize[v], k)$. $O(3^{n/3})$ clique: It looks like a simple branch-and-bound heuristic at first glance. Problems with randomization: link. You can use similar tricks for smallest enclosing circles and Voronoi diagram.
 » 15 months ago, # |   +6 Maybe just for me but I came up with the solution of 1361F in half a minute.PS: my real color is orange
 » 15 months ago, # | ← Rev. 3 →   -10 Because the problem setter is also stupid sometime.