Strategies

Random assorted notes from competitive programming problems - various strategies, etc.

Data Structures

Utilize ALL THE DATA STRUCTURES

PriorityQueue - queue in which things are put into their natural order

• Useful to implement with your own custom class, and extend Comparable

Arrays and Strings

Hash tables

• Using a HashSet or HashMap in Java is a fast, O(1) way to look things up
• Use hash tables when you need to keep track of how many of X different things you have seen
• Internally, hash tables can use binary trees to stay balanced, and use less space

Array lists

• Internally resized array with O(1) access
• When array runs out of space, needs to double, which takes O(N)
• Doubling in size should happen infrequently, so ends up taking O(1) on average

StringBuffer

• Avoids the expensive/costly construction of a new string in a loop
• StringBuffer internally stores an array of Strings, does not concatenate them until it needs to return the result (when toString() method called)

public string joinWords(String[] words) {
  StringBuffer sentence = new StringBuffer();
  for(String w : words) { 
    sentence.append(w + " ");
  }
  return sentence.toString();
}

Mazes

Problems involving mazes - particularly, mazes with tricky constraints, like directional mazes - can easily trip you up. Remember to keep it simple.

If you're initializing a maze and it's character based, load it into a two-dimensional array, like this:

		Scanner scan = new Scanner(System.in);
		int r = scan.nextInt();
		int c = scan.nextInt();
		char[][] grid = new char[r][c];
		for(int i = 0; i < r; i++) {
			String s = scan.next();
			for(int j = 0; j < c; j++) {
				grid[i][j] = s.charAt(j);
			}
		}
		String ops = scan.next();
		int[][][] dp = new int[r][c][ops.length()+1];
		PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				Arrays.fill(dp[i][j], 1 << 25);
				if(grid[i][j] == 'R') {
					dp[i][j][0] = 0;
					q.add(new Vertex(i, j, 0, 0));
				}
			}
		}