Online Course Discussion Forum

USACO: under what size of data is it generally safe to use "brute force" solutions?

 
 
WangJialin的头像
USACO: under what size of data is it generally safe to use "brute force" solutions?
WangJialin - 2023年02月13日 Monday 23:35
 

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();

  }

}





 
WangDr. Kevin的头像
Re: USACO: under what size of data is it generally safe to use "brute force" solutions?
WangDr. Kevin - 2023年02月15日 Wednesday 18:37
 

On the Bronze level, when the data size is $N=100$, there is no significant difference between $O(N^2)$ and $O(N^3)$.  It's like 0.01 second and 1 second, you notice the difference in speed, but it won't be that much.  When $N=10^5$ or something like that, it will be quite different.

To find the bug in your program, print out some more intermediate results to debug (or use the debugger in your IDE).