Class 0: 1/7

Notes

Fill out the course information form https://docs.google.com/forms/d/1JFfFQhBfVy4dfTalXX0Xa6cYtvwTBVEvWz_TpdCm0xo/viewform
Solve one problem from nwerc2014, submit it to http://icpc.egr.duke.edu, and contribute to the wiki page for the problem you solved
Consider one of the officer positions in DPCC

Solve any two problems from nwerc2014 or rmrc2014. Contribute to the wiki page for the problem you solved
OLA's section solve problems A and B from rmrc2014
Kevin's section try to solve problems F and I from nwerc2014

Covered "finding lines
- very low tolerance, can use randomized algorithm
- 10^5 is too slow for n^2....break it into two (or more groups), solve for each group and then combine the solutions (divide and conquer!)
Indoorienteering
- NP complete, clear must be some brute force solution because n=14 (small)
- since must reach all points, fix one of them as the start point (14! => 13!)
- split it up into two halves, iterating over the midpoint (13 * (12 choose 6) * 6!*6!)
- store the results of one half in a hashmap, and then when doing the second half, simply check whether the proper distance exists in the hashmap (13 * (12 choose 6) * (6! + 6!))
- Divide and conquer (again)
Plane ticket pricing
- brute force too slow (and can have invalid solutions...because we only have so many seats)
- greedy doesn't work because we can make a selection now that can hurt us later
- above points SCREAM DP
- time almost always a dimension of the DP
- other things that can lead to invalid solutions (selling too many seats) also almost always a dimension
- value stored is almost always the thing we're trying to solve for (most amount of money)

Solve Preorder Traversals from ncna2014 (OLA's section)
Solve Finding Lines (if you haven't already) using either of the two discussed methods (or your own!) (Kevin's section)
Solve Plane ticket pricing (kevin's section)