USACO - Clocks

This was a rather tricky problem listed here that would not run quickly for a standard BFS. So the name of the game was "OPTIMIZE', especially given the time constraint of 1 sec and for some solutions having no. of moves greater than 20.

The crucial thing to realize is that iterating 9 decisions(1 for each key) will not work for large depths, so we need to prove keys that are repeated more than 3 times, since using a key for 4 will bring the clock back to the same position.

After this, to represent a state of 9 clocks, we can use just 2 bits for each clock, for a total of 18 bits(which can be fit in a java int). But how can I fit in 12 0 clock in 2 bits (won't it take 4 bits)? Actually you can't but that's not a problem since the clock can only be in 4 states so representing 00 as 12'0clock, 01 as 3'0clock and so on will work. This will make your final state be 0 since all clocks are then at 12 o'clock.  After this you need some bit mask magic to change the state for a clock. (This is a bit non-trivial since we're changing 2 bits, but is still pretty very doable). If you're unfamiliar with bitmasks, check out bmerry's article at topcoder here.

We also need to add memoization to our BFS to make sure repeated states are not processed. Again, we can use an int to to represent a state of clocks similar to what we just saw.
I also discovered that using an ArrayDeque instead of a LinkedList for my Queue implementation speeded up things by about 20%, even though both are supposed to work in O(1). I believe this is because ArrayDeque does not resize it's elements as often as LinkedList, but I haven't confirmed this. Everything else is just straightforward BFS.  Here's the code:

	import java.io.*;
	import java.util.*;
	class Node
	{
	int state;//current state of clocks
	byte[] moves;//past moves done
	public Node(int state, byte[] oldMoves, Byte lastMove)
	{
	this.state = state;
	moves = oldMoves == null ? new byte[0] :
	Arrays.copyOf(oldMoves, oldMoves.length+1);
	if(lastMove!=null)
	moves[oldMoves.length] = lastMove;
	}
	}
	public class clocks {
	static boolean[] vis = new boolean[1 << 18];
	static String[] chars = {"ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI"};
	static char[][] moves;
	//given clock state and key, get new clock state
	private static int doChange(int state, int m)
	{
	m--;
	int n = moves[m].length;
	for(int i = 0; i < n; ++i)
	{
	int maskPos = ((moves[m][i] - 'A')<<1);
	//get the two bits that are masked into least significant bits and increment
	int newstate = ((state >> maskPos) + 1) & 3;
	//reset the 2 bits in old state
	state &= ~(3 << maskPos);
	//add the two bits */
	state |= (newstate << maskPos);
	}
	return state;
	}
	private static byte[] go(int arr)
	{
	Queue<Node> q = new ArrayDeque<Node>();
	vis[arr] = true;
	q.add(new Node(arr, null, null));
	while(!q.isEmpty())
	{
	Node s = q.poll();
	if(s.state == 0)//finish
	return s.moves;
	byte[] cnt = new byte[10];
	for(byte m : s.moves)
	++cnt[m];
	for(byte i = 1; i <= 9; ++i)
	{
	if(cnt[i] >= 3)continue;
	int changed = doChange(s.state, i);
	if(vis[changed])
	continue;
	Node ns =new Node(changed, s.moves, i);
	vis[ns.state] = true;
	q.add(ns);
	}
	}
	return null;
	}
	public static void main(String[] args) throws Exception {
	long startTime = System.currentTimeMillis();
	String taskname = "clocks";
	Scanner scr = new Scanner(new BufferedReader(new FileReader(taskname + ".in")));
	/*
	* Use 2 bits to represent clocks. 12'0 by 0, 3'0clock by 01, 6'0 clock by 10 and 9'0 by 11
	*/
	moves = new char[chars.length][];
	for(int i = 0;i < chars.length; ++i)
	moves[i] = chars[i].toCharArray();
	int state = 0;
	int i = 0;
	while(i < 9)
	{
	//12'0 represented as 0, 3 o clock as 1 and so on
	int val = (scr.nextInt()/3)%4;
	//top left clock in last two bits...bottom right in left two bits
	int maskPos = (i<<1);
	state |= ((3&val) << maskPos);
	i++;
	}
	scr.close();
	//Call main
	byte[] res = go(state);
	//OUTPUT
	PrintWriter pout = new PrintWriter(new BufferedWriter(new FileWriter(taskname + ".out")));
	String line = "";
	if(res.length != 0)
	line += res[0];
	int nres = res.length;
	System.out.println(nres);
	for(i = 1;i < nres; ++i)
	{
	line += " " + res[i];
	}
	pout.println(line);
	System.out.println(line);
	System.out.println(System.currentTimeMillis()-startTime);
	pout.close();
	}
	}

view raw clocks.java hosted with ❤ by GitHub