Strategies

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

Up and Running with Code Jam

Google Code Jam: link to the quick start guide

Some tips 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