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

Know and utilize all the data structures

In Java:

• Arrays
• ArrayLists
• LinkedLists
• Maps (TreeMap, HashMap)
• Sets (TreeSet, HashSet)
• Stacks
• Queues
• Deques

Note the Java documentation is a complete mess with respect to organizing information. Link roll:

• "Trails" with some summary information: https://docs.oracle.com/javase/tutorial/collections/interfaces/index.html

• Interfaces:
  • Collections interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html
  • Queue interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html
  • Deque interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/deque.html
  • List interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html
  • Map interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html
  • SortedMap interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/sorted-map.html
  • Set interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/set.html
  • SortedSet interface: https://docs.oracle.com/javase/tutorial/collections/interfaces/sorted-set.html

Lists:

• Interface documentation:
  • List interface: https://docs.oracle.com/javase/7/docs/api/java/util/List.html
• Class documentation:
  • Vector class: https://docs.oracle.com/javase/7/docs/api/java/util/Vector.html
  • Stack class: https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
  • LinkedList class: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
  • ArrayList class: https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html

Lists summary:

• LinkedLists much faster (O(1)) to add/remove items (e.g., 1 million element list and adding something to the very beginning of the list)
• ArrayLists utilize resizable array, much faster to access random items (O(1) access instead of O(N) access)
• Vector is thread-safe, synchronized version of ArrayList

Sets:

• Interface documentation:
  • Set interface: https://docs.oracle.com/javase/7/docs/api/java/util/Set.html
  • SortedSet interface: https://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html
  • NavigableSet interface: https://docs.oracle.com/javase/7/docs/api/java/util/NavigableSet.html
• Class documentation:
  • HashSet class: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
  • TreeSet class: https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html
  • LinkedHashSet class: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html

Sets summary:

• HashSet is faster, no ordering provided; TreeSet is slower, elements maintained in natural sorted order
• LinkedHashSet inherits from HashSet; utilizes a doubly-linked list structure to preserve order in which elements were added; iterator iterates through items in order in which they were added, but does not incur extra overhead of TreeSet

Maps:

Maps summary:

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