I am working on the "Bovine Shuffle" problem from the December 2017 USA Computing Olympiad, and have got it to work for every test case beside two. When I run these two cases on my own computer, they return the correct answer, but not within the time limit.
The "Bovine Shuffle" consists of [Farmer John's] \$N\$ cows (\$1≤N≤100,000\$) lining up in a row in some order, then performing successive "shuffles", each of which potentially re-orders the cows. To make it easier for his cows to locate themselves, Farmer John marks the locations for his line of cows with positions \$1, \ldots, N\$, so the first cow in the lineup will be in position 1, the next in position 2, and so on, up to position \$N\$.
A shuffle is described with \$N\$ numbers, \$a_1, \ldots, a_N\$, where a cow in position \$i\$ moves to position \$a_i\$ during the shuffle (and so, each \$a_i\$ is in the range \$1, \ldots, N\$). Every cow moves to its new location during the shuffle. Unfortunately, all the \$a_i\$ are not necessarily distinct, so multiple cows might try to move to the same position during a shuffle, after which they will move together for all remaining shuffles.
Farmer John notices that some positions in his lineup contain cows in them no matter how many shuffles take place. Please help him count the number of such positions.
For example, given the shuffle 3 3 2 4 1, it is clear that no cow will ever go to position 5. Since position 5 is the only way to get to position 1, no cow will ever stay at position 1. There are multiple ways to get to position 3, so no cows on 1 will not make a difference. Thus, 3 spots will always have cows.
What my code does is:
- Find every spot that is not directly mentioned
- Check to see if these spots are the only way to get to a position. If so, add them to the queue.
- Remove the first item from the queue from the data.
My code is as follows:
import java.io.*;
import java.util.*;
public class TheBovineShuffleSilver {
public static void main (String [] args) throws IOException {
BufferedReader f = new BufferedReader(new FileReader("shuffle.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("shuffle.out")));
StringTokenizer st = new StringTokenizer(f.readLine());
int n = Integer.parseInt(st.nextToken());
ArrayList<Integer> data = new ArrayList<Integer>();
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
StringTokenizer st2 = new StringTokenizer(f.readLine());
LinkedList<Integer> unused = new LinkedList<Integer>();
int nextTok;
int i;
for (i = 1; i <= n; i++) {
nextTok = Integer.parseInt(st2.nextToken());
data.add(nextTok);
unused.add(i);
if (!freq.containsKey(nextTok))
freq.put(nextTok, 1);
else
freq.put(nextTok, freq.get(nextTok) + 1);
}
System.out.println("After first for loop:" + System.currentTimeMillis());
for (i = 0; i < n; i++) {
unused.remove(data.get(i));
}
System.out.println("After second for loop:" + System.currentTimeMillis());
int c = n;
int nextPoint;
while (!unused.isEmpty()) {
c--;
nextPoint = data.get(unused.poll() - 1);
freq.put(nextPoint, freq.get(nextPoint) - 1);
if (freq.get(nextPoint) == 0)
unused.add(nextPoint);
}
System.out.println("After while loop:" + System.currentTimeMillis());
System.out.println(c);
out.close();
}
}
Using these print outs, I have found that the point of error is the second for loop. I have tried to optimize it, as earlier the loop looked like this
for (i = 1; i <= n; i++) {
if (!data.contains(i)) unused.add(i);
}
This helped reduce the time and allowed me to complete test cases 8, 9 and, 10 within the time limit, but 6 and 7 still fail.
Any help with optimizing this program would be deeply appreciated.
[EDIT] The test cases that fail are as follows: