-is-this-fft-'s blog

By -is-this-fft-, history, 5 weeks ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • +54
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

problem Ehab and Expected XOR Problem

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you prove even that this solution produces maximal length, without using ideas from real solution?

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

1073D - Берляндская ярмарка brute force solution is correct because given cost reduces very fast on every iteration.

»
4 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

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.