-is-this-fft-'s blog

What are some examples of problems where "naive" solution is actually correct?
By -is-this-fft-, history, 5 years 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

Comments Comments (9)
| Write comment?
»
5 years 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

→ Reply
  • »
    »
    5 years 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?

    → Reply
»
5 years ago, # |
  Vote: I like it -16 Vote: I do not like it

1073D - Berland Fair brute force solution is correct because given cost reduces very fast on every iteration.

→ Reply
»
5 years 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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/GW19MOS/problems/MEANPROB

This is from a ICPC regional. The bruteforce algorithm works

→ Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it
  • 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.
→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Maybe just for me but I came up with the solution of 1361F in half a minute.

PS: my real color is orange

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

Because the problem setter is also stupid sometime.

→ Reply