Bovine Shuffle using a queue (USACO Dec 2017 Silver)

Question

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 {
      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:

6 - https://pastebin.com/i79tiFZ1

7 - https://pastebin.com/i1Djb7fH

Answer 1

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
add currentState to knownStates

//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
    add currentState to knownStates

now, to extract the solution, init another BitSet "solution" to all ones
for each state out of knownStates
    for each "false"-bit
        set solution's position to false, too

count remaining bits in solution