What are some examples of problems where "naive" solution is actually correct?

Revision en1, by -is-this-fft-, 2019-06-16 02:53:32

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 - Хорошая тройка. 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 - Сделай симметричным 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 - Уильям, Ктолли и Сениориус 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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English -is-this-fft- 2019-06-16 02:53:32 959 Initial revision (published)