Strategies - Revision history

Admin: /* Writing Sorting Functions, Fast */

2017-05-25T04:00:23Z

Writing Sorting Functions, Fast

← Older revision		Revision as of 04:00, 25 May 2017
Line 14:		Line 14:
	}		}
	}		}
	</~~math~~>		</pre>

	Then if we define an array of Point objects, we can call the Arrays.sort() method. One version of this method (see [https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-java.util.Comparator- java 8 api documentation]) takes an array and a Comparator.		Then if we define an array of Point objects, we can call the Arrays.sort() method. One version of this method (see [https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-java.util.Comparator- java 8 api documentation]) takes an array and a Comparator.
Line 49:		Line 49:
	Arrays.sort(p, (p1, p2) -> Long.compare(p1.x, p2.x) != 0 ? Long.compare(p1.x, p2.x) : Long.compare(p1.y, p2.y));		Arrays.sort(p, (p1, p2) -> Long.compare(p1.x, p2.x) != 0 ? Long.compare(p1.x, p2.x) : Long.compare(p1.y, p2.y));
	</pre>		</pre>


	==Up and Running with Code Jam Templates==		==Up and Running with Code Jam Templates==

Admin: /* Up and Running with Code Jam Templates */

2017-05-25T04:00:13Z

Up and Running with Code Jam Templates

← Older revision		Revision as of 04:00, 25 May 2017
Line 1:		Line 1:
	Random assorted notes from competitive programming problems - various strategies, etc.		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:

			<pre>
			class Point {
			long x, y;
			public Point(long x, long y) {
			this.x = x; this.y = y;
			}
			}
			</math>

			Then if we define an array of Point objects, we can call the Arrays.sort() method. One version of this method (see [https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-java.util.Comparator- 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:

			<pre>
			(a,b)-> Long.compare( a, b)
			</pre>

			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:

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

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

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

			===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:

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


	==Up and Running with Code Jam Templates==		==Up and Running with Code Jam Templates==

Admin: /* Data Structures */

2017-05-24T22:24:29Z

Data Structures

← Older revision		Revision as of 22:24, 24 May 2017
Line 73:		Line 73:

	==Data Structures==		==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		Utilize ALL THE DATA STRUCTURES

Admin: /* Up and Running with Code Jam */

2017-05-24T21:31:37Z

Up and Running with Code Jam

← Older revision		Revision as of 21:31, 24 May 2017
Line 1:		Line 1:
	Random assorted notes from competitive programming problems - various strategies, etc.		Random assorted notes from competitive programming problems - various strategies, etc.

	==Up and Running with Code Jam==		==Up and Running with Code Jam Templates==

	Google Code Jam: link to the [https://code.google.com/codejam/resources/quickstart-guide quick start guide]		Google Code Jam (link to the [https://code.google.com/codejam/resources/quickstart-guide quick start guide]) provides some nice templates for getting started with various languages, so you don't have to fuss with a template.

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

	<pre>		<pre>

Admin: /* Up and Running with Code Jam */

2017-05-24T21:30:53Z

Up and Running with Code Jam

← Older revision		Revision as of 21:30, 24 May 2017
Line 5:		Line 5:
	Google Code Jam: link to the [https://code.google.com/codejam/resources/quickstart-guide quick start guide]		Google Code Jam: link to the [https://code.google.com/codejam/resources/quickstart-guide quick start guide]

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

			<pre>
			$ MY_PROGRAM < input_file.txt > output_file.txt
			</pre>

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

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

			and in C++:

			<pre>
			#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;
			}
			</pre>

			and in Python 2:

			<pre>
			# 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
			</pre>

			and in Python 3:

			<pre>
			# 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
			</pre>

	==Data Structures==		==Data Structures==

Admin at 21:29, 24 May 2017

2017-05-24T21:29:06Z

← Older revision		Revision as of 21:29, 24 May 2017
Line 1:		Line 1:
	Random assorted notes from competitive programming problems - various strategies, etc.		Random assorted notes from competitive programming problems - various strategies, etc.

			==Up and Running with Code Jam==

			Google Code Jam: link to the [https://code.google.com/codejam/resources/quickstart-guide quick start guide]



	==Data Structures==		==Data Structures==

Admin: /* Mazes */

2017-05-24T21:27:44Z

Mazes

← Older revision		Revision as of 21:27, 24 May 2017
Line 61:		Line 61:


	~~[[Category:Competitive Programming]]~~		{{CPFlag}}

Admin: /* Arrays and Strings */

2017-05-22T22:39:01Z

Arrays and Strings

← Older revision		Revision as of 22:39, 22 May 2017
Line 33:		Line 33:
	}		}
	</pre>		</pre>

			BufferedReader/BufferedWriter
			* Allow reading and writing one (or a few) characters at a time

	==Mazes==		==Mazes==

Admin: /* Mazes */

2017-05-22T22:36:57Z

Mazes

@@ Line 49: / Line 49: @@
 			for(int j = 0; j < c; j++) {
 				grid[i][j] = s.charAt(j);
+			}
+		}

Admin at 22:24, 22 May 2017

2017-05-22T22:24:19Z

@@ Line 1: / Line 1: @@
 Random assorted notes from competitive programming problems - various strategies, etc.
 ==Data Structures==
@@ Line 65: / Line 34: @@
 </pre>