Strategies

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

Up and Running with Code Jam Templates

Google Code Jam (link to the quick start guide) provides some nice templates for getting started with various languages, so you don't have to fuss with a template.

Hat tip from that page: redirect stdin to program, and redirect stdout to file, with the following command:

$ MY_PROGRAM < input_file.txt > output_file.txt 

A basic template for getting started with file I/O in Java:

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int t = in.nextInt();  // Scanner has functions to read ints, longs, strings, chars, etc.
    for (int i = 1; i <= t; ++i) {
      int n = in.nextInt();
      int m = in.nextInt();
      System.out.println("Case #" + i + ": " + (n + m) + " " + (n * m));
    }
  }
}

and in C++:

#include <iostream>  // includes cin to read from stdin and cout to write to stdout
using namespace std;  // since cin and cout are both in namespace std, this saves some text
int main() {
  int t, n, m;
  cin >> t;  // read t. cin knows that t is an int, so it reads it as such.
  for (int i = 1; i <= t; ++i) {
    cin >> n >> m;  // read n and then m.
    cout << "Case #" << i << ": " << (n + m) << " " << (n * m) << endl;
    // cout knows that n + m and n * m are ints, and prints them accordingly.
    // It also knows "Case #", ": ", and " " are strings and that endl ends the line.
  }

  return 0;
}

and in Python 2:

# raw_input() reads a string with a line of input, stripping the '\n' (newline) at the end.
# This is all you need for most Google Code Jam problems.
t = int(raw_input())  # read a line with a single integer
for i in xrange(1, t + 1):
  n, m = [int(s) for s in raw_input().split(" ")]  # read a list of integers, 2 in this case
  print "Case #{}: {} {}".format(i, n + m, n * m)
  # check out .format's specification for more formatting options

and in Python 3:

# input() reads a string with a line of input, stripping the '\n' (newline) at the end.
# This is all you need for most Google Code Jam problems.
t = int(input())  # read a line with a single integer
for i in range(1, t + 1):
  n, m = [int(s) for s in input().split(" ")]  # read a list of integers, 2 in this case
  print("Case #{}: {} {}".format(i, n + m, n * m))
  # check out .format's specification for more formatting options

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();
}

BufferedReader/BufferedWriter

• Allow reading and writing one (or a few) characters at a time

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);
			}
		}

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag