# Help understanding USACO Bronze 'Shell Game' (solution)

Hi! I’ve just started competitive programming, and I’m having some trouble understanding the solution to ‘Shell Game.’ Any help would be greatly appreciated.

Solution code (from usaco guide):

``````import java.io.*;
import java.util.*;

public class Shell {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio("shell");

int n = io.nextInt();

// shellAtPos[i] stores the label of the shell located at position i
int[] shellAtPos = new int[3];

// Arbitrarily place the shells down
for (int i = 0; i < 3; i++) { shellAtPos[i] = i; }

// counter[i] stores the number of times the shell with label i was
// picked
int[] counter = new int[3];

for (int i = 0; i < n; i++) {
// Zero indexing: offset all positions by 1
int a = io.nextInt() - 1;
int b = io.nextInt() - 1;
int g = io.nextInt() - 1;

// Perform Bessie's swapping operation
int temp = shellAtPos[b];
shellAtPos[b] = shellAtPos[a];
shellAtPos[a] = temp;

// Count the number of times Elsie guesses each particular shell
counter[shellAtPos[g]]++;
}

io.println(Math.max(counter[0], Math.max(counter[1], counter[2])));
io.close();
}

//BeginCodeSnip{Kattio}
static class Kattio extends PrintWriter {
private StringTokenizer st;
// standard input
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(problemName + ".out");
r = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
//EndCodeSnip
}
``````

What I don’t understand about this solution is the ‘arbitrary’ ordering of the shells. When I read the problem, I understood that the order of the shells was unknown, and that you had to permute through all the possible orderings (012, 021, 102, 120, et cetera.) This solution stores the initial positions of the shells as 0, 1, and 2 (1, 2, and 3 with non-array indices.)
Wouldn’t this return an incorrect answer if you’re supposed to permute through ALL of the orderings?
Thank you!

Yes, the initial location of the pebble is unknown. The code puts “labels” on each of the shells and checks how many times each label is picked.

As for permutations, I’m not exactly sure what you mean by that. Could you clarify your question?

What I mean by permutations is all of the possible orderings of the shells before Bessie starts swapping them. For example, if the shells are labeled 0, 1, and 2, before Bessie starts swapping them they could be in any order (012, 021, 102, etc.) However, the program only accounts for the first permutation of the shells - 012.
However, I can understand why this solution works if the problem assumes that the order of the shells is in some arbitrary order x, rather than some random order.

It doesn’t matter what initial labels we give the shells. We don’t care what we call a shell- it could be named 0, 1, or even 1234. We just care how many times Elsie picks that shell.

Okay, thanks!