3
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the feedback. I will edit my answer to reflect these. \$\endgroup\$ – CannotCode Jun 11 '18 at 4:41
  • \$\begingroup\$ 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 \$\endgroup\$ – juvian Jun 11 '18 at 5:19
  • \$\begingroup\$ @CannotCode Just out of curiosity: do you have some more test cases than the one that you mentioned? \$\endgroup\$ – mtj Jun 11 '18 at 10:46
  • \$\begingroup\$ @mtj I do, and I will add them to the problem for clarity \$\endgroup\$ – CannotCode Jun 11 '18 at 21:33
  • \$\begingroup\$ 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 \$\endgroup\$ – juvian Jun 12 '18 at 1:39
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ What I find is interesting, is that for some reason unused.removeAll(data) causes cases 9 and 10 to timeout. Do you have any idea why this may be true? I believe 10 would be a worst case scenario as every element is mentioned \$\endgroup\$ – CannotCode Jun 14 '18 at 21:51
  • \$\begingroup\$ @CannotCode No immediate idea. Could you post the other test cases as well? (I am not registered at that site, so my tests are only based on the cases 6 and 7 that you posted earlier.) \$\endgroup\$ – mtj Jun 15 '18 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.