In this solution: http://www.usaco.org/current/data/sol_cowpatibility_gold_dec18.html, how many cases should the “optimized brute-force” solution pass? I still only passed the sample when I coded the optimized brute force solution. (I know this is not the intended solution, but I just want to go through all the steps before reaching the final solution).
Below is my code, can someone tell me if this is what the editorial meant by optimized brute force.
import java.io.*;
import java.util.*;
public class cowpatibility {
public static void main(String[] args) throws IOException{
//BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
BufferedReader file = new BufferedReader(new FileReader("cowpatibility.in"));
PrintWriter outfile = new PrintWriter (new BufferedWriter(new FileWriter("cowpatibility.out")));
int n = Integer.parseInt(file.readLine());
HashSet<Integer>[] arr = new HashSet[n];
HashSet<Integer>[] a2 = new HashSet[1000001];
for (int i=0; i<n; i++){
arr[i] = new HashSet<>();
}
for (int i=0; i<1000001; i++){
a2[i] = new HashSet<>();
}
HashSet<Integer> all = new HashSet<>();
for (int i=0; i<n; i++){
StringTokenizer st = new StringTokenizer(file.readLine());
for (int j=0; j<5; j++){
int id = Integer.parseInt(st.nextToken());
arr[i].add(id);
a2[id].add(i);
if (a2[id].size() == 2){
all.addAll(a2[id]);
}else if (a2[id].size() > 2){
all.add(i);
}
}
}
int ans = 0;
List<Integer> list = new ArrayList<>(all);
for (int i=0; i<list.size(); i++){
for (int j=i+1; j<list.size(); j++){
for (int id : arr[list.get(i)]){
if (arr[list.get(j)].contains(id)){
ans++;
break;
}
}
}
}
outfile.println((n*(n1))/2-ans);
outfile.close();
}
}