Online Course Discussion Forum
USACO: under what size of data is it generally safe to use "brute force" solutions?
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();
}
}
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).
社交网络