Strategies

From charlesreid1

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

Writing Sorting Functions, Fast

One particularly time-consuming operation can be implementing an array or container of custom-defined objects, and then sorting the list based on some custom criteria. To keep this really fast, you can define a sort Comparator (sort function) in-place.

Suppose we have a simple Point class defined: 

class Point {
    long x, y;
    public Point(long x, long y) {
        this.x = x; this.y = y;
    }
}

Then if we define an array of Point objects, we can call the Arrays.sort() method. One version of this method (see java 8 api documentation) takes an array and a Comparator.

Defining an Inline/Lambda Comparator

Now define a Comparator in-place (NOTE: ONLY WORKS WITH JAVA 8) using lambda function syntax like this: 

(a,b)-> Long.compare( a, b)

In this case, we actually want to make it a bit more complicated, because we are dealing with both x and y values of the point. So if we want to say, compare x-values, and if they are tied, use the y-values as a tie-breaker, we can say: 

(p1, p2)-> if( Long.compare( p1.x, p2.x) != 0 ) { 
    Long.compare( p1.x, p2.x ); 
} else { 
    Long.compare( p1.y, p2.y ); 
}

Or, to make it a one-liner and replace the if/else syntax with some shorthand, we can say: 

(p1, p2) -> Long.compare(p1.x, p2.x) != 0 ? Long.compare(p1.x, p2.x) : Long.compare(p1.y, p2.y));

Using the Inline/Lambda Comparator with Arrays sort

Now that we have a lambda function that replaces our Comparator object, we can pass this to the version of Arrays.sort that expects a comparator as one of the arguments: 

Arrays.sort(p, (p1, p2) -> Long.compare(p1.x, p2.x) != 0 ? Long.compare(p1.x, p2.x) : Long.compare(p1.y, p2.y));

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:

Lists:

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:

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



CSFlag.jpg
Computer Science
notes on computer science topics on the wiki, for educational and learning purposes

Computer Science Notes

Part of the 2017 CS Study Plan.


Language Notes

Python

Python/Exceptions  · Python/Assertions  · Python/Decorators

Python/Os (os module)  · Python/Strings

Python/Splat  · Python/Iterators  · Python/Generators

Python/Comparators  · Python/Lambdas


Java

Builtin features of Java: Java/Exceptions  · Java/Assertions  · Java/Memory  · Java/Interfaces

Java/Generics  · Java/Decorators  · Java/Diamond Notation

Java/Iterators  · Java/Iterable  · Iterators vs Iterable

Java/Comparators  · Java/Comparable  · Comparators vs Comparable

Java/Methods  · Java/Lambas

Java/HashCodes

Java/Numeric  · Java/TypeChecking  · Java/Testing  · Java/Timing  · Java/Profiling

Java/Datetime

Documentation: Javadocs  · Java/Documentation

Tools and functionality: Java/URLs  · Java/CSV

External libraries: Guava  · Fastutil  · Eclipse Collections

OOP: OOP Checklist  · Java/Abstract Class  · Java/Encapsulation  · Java/Generics


Flags  · Template:CSFlag  · e



See also:

Retrieved from "https://charlesreid1.com/w/index.php?title=Strategies&oldid=17349"