I was doing USACO 2020 December Contest Bronze #2.

 http://www.usaco.org/index.php?page=viewproblem2&cpid=1060

I was trying to do a prefix sum approach of the problem, which is O(n^2). The program worked as intended for 7 out of 10 test cases, but was 1 off for 3 out of 10 test cases. For example one of the correct output is 1411 but I got 1412. So I checked the official answer, which is a O(n^3) brute force approach that just basically goes through every possibility. I was  hesitant to choose this approach because it may exceed the 4s runtime limit, but the official answer turned out to be just fine.

Under what data size is it generally safe to use inefficient "brute force"? I feel like whenever I see things abbreviated exponents of 10 there is always an easier solution than brute force, and when at 100 or 1000 it's same to do an O(n^2) or n^3 algorithm.

//my prefix sum solution

import java.util.*;

import java.io.*;

public class DaisyChain

{

    public static void main(String[] args)

    {

        int result = 0;

        Scanner in = new Scanner(System.in);

        int N = Integer.parseInt(in.nextLine());

        int[] daisy = new int[N];

        for(int i = 0; i < N; i++)

        {

            daisy[i] = in.nextInt();

        }

        int[] pre = new int[N];

        int sum = 0;

        for(int i = 0; i < N; i++)

        { 

           sum += daisy[i];

           pre[i] = sum;

        }

        for(int i = 0; i < N; i++)

        {

            for(int j = i + 1; j < N; j++)

            {

                 int petals = pre[j]-pre[i];

                 int flowers = j - i;

                 int p = 0;

                 if(petals % flowers == 0)

                 {

                     p = petals/flowers;

                 }

                 else

                 {

                     p = Integer.MIN_VALUE;

                 }

                 /*System.out.println("i:" + i);

                 System.out.println("j:" + j);

                 System.out.println("p:" + p);*/

                 for(int k = i; k <= j ; k++)

                 {

                   if(daisy[k] == p)

                   {

                       //System.out.println("added");

                       result++;

                       break;

                   }

                 }

            }

        }

        for(int j = 0; j < N; j++)

        {

            //System.out.println(pre[j] + "/" + (j+1));

            if(pre[j] % (j+1) == 0)

            {

                int p = (pre [j]  / (j+1));

                for(int k = 0; k <=j; k++)

                {

                    if (daisy[k] == p)

                    {

                        result++;

                        break;

                    }

                }

            }

        }

        System.out.println(result);

    } 

}

//Official solution

import java.io.*;

import java.util.*;

public class DaisyChainSolution {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    int n = Integer.parseInt(br.readLine());

    int[] petals = new int[n];

    StringTokenizer st = new StringTokenizer(br.readLine());

    for(int i = 0; i < n; i++) {

      petals[i] = Integer.parseInt(st.nextToken());

    }

    int photos = 0;

    for(int i = 0; i < n; i++) {

      for(int j = i; j < n; j++) {

        int totalPetals = 0;

        for(int k = i; k <= j; k++) {

          totalPetals += petals[k];

        }

        boolean present = false;

        for(int k = i; k <= j; k++) {

          if(petals[k] * (j-i+1) == totalPetals) {

            present = true;

          }

        }

        if(present) {

          photos++;

        }

      }

    }

    pw.println(photos);

    pw.close();

  }

}