# Bovine Shuffle using a queue (USACO Dec 2017 Silver)

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:

1. Find every spot that is not directly mentioned
2. Check to see if these spots are the only way to get to a position. If so, add them to the queue.
3. 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 {
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("shuffle.out")));

int n = Integer.parseInt(st.nextToken());
ArrayList<Integer> data = new ArrayList<Integer>();
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();

int nextTok;
int i;
for (i = 1; i <= n; i++) {
nextTok = Integer.parseInt(st2.nextToken());

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)
}
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++) {
}


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:

• Thanks for the feedback. I will edit my answer to reflect these. Jun 11, 2018 at 4:41
• dont do !data.contains(i), thats O(n), making you end up with a O(N^2) solution. You need a O(n log n), use a map or a set Jun 11, 2018 at 5:19
• @CannotCode Just out of curiosity: do you have some more test cases than the one that you mentioned?
– mtj
Jun 11, 2018 at 10:46
• @mtj I do, and I will add them to the problem for clarity Jun 11, 2018 at 21:33
• you have the same problem as before, you are now using unused.remove() which is O(n) ending up with a O(n^2) complexity. Stop using linked list and use a map or a set Jun 12, 2018 at 1:39

First of all, thanks for sharing this quite intriguing problem with us. Was some fun in the lunch break for me :-)

Regarding your problematic second loop: you can simply utilize the builtin functions of the collections framework to cut the time to roughly 30% of the original runtime by simply calling:

unused.removeAll(data);


Nevertheless, the algorithmic idea seems to be inferior to a simple iterative solution. My lunch-break-attempt solves problem 7 in 420 ms as compared to 60 s with your original code or 18 s using removeAll as shown above.

Basic algorithmic idea:

use a BitSet currentState to hold the current state of places used
use a set of known states to hold every state we have seen so far

init currentState to all ones

//try to find a loop in the application of the shuffle function

repeat
currentStateNew := performShuffle(currentState)
if knownStates contains currentStateNew:
break the loop
currentState := currentStateNew