Spring15
test server: http://speedyguy17.info/ucpccc-master/
Class 0: 1/7
Notes
Homework
- 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
Class 1: 1/14
Notes
- No class next week (MLK day)
Homework
- 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
Class 2: 1/28
Notes
- 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)
Homework
- 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)
Class 3: 2/2
Problems: http://cerc.tcs.uj.edu.pl/2014/data/cerc2014problems.pdf
Notes
- Covered Can't Stop Playing
- just like http://gabrielecirulli.github.io/2048/ but in 1 dimension
- can't get small numbers stuck between big numbers
- greedy solution should work, or smart brute force (try everything, but eliminate losing positions based on above point)
- since only one of each power of 2 on each side, and must go in order, can simply store in a bit field, and use "lowest ones bit"
- Covered Pork Barrel
- Seems like Minimum Spanning Tree but too much time to recompute for all the test cases
- How do we use data computed from previous test cases in newer test cases?
- Covered Wheels
- Have to figure out which wheels are connected to which...BFS!
Homework
- Solve Underground Cables Link: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=403&page=show_problem&problem=2873 (Kevin's Section)
- Derive an algorithm for Pork Barrel (Kevin's Section)
- HINT: read about Kruskal's algorithm: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm and Reverse-delete algorithm: http://en.wikipedia.org/wiki/Reverse-delete_algorithm
- Solve Wheels (owen's section)
- Ask for a wiki login and contribute for the problem you solved!
Class 4: 2/9
Problems: http://swerc.up.pt/2014/reports/problemset.pdf
Notes
- Covered GREAT + SWERC = PORTO
- Brute force with backtracking
- Can do recursion or iteration
- Covered Gathering
- Break into two problems: Finding the absolute minimum, and finding the range of valid points
- Minimum is found by breaking up into x and y coordinates and solving separately (always the median)
- Range of points is found by intersecting the bounds for point 1 with point 2, then that intersection with point 3...etc
- If the range for the two problems intersect, you're done, else finding the closest valid point to the minimum range from part 1, and that's the answer (will always be a corner)
- BONUS: solution will always share an x and y coordinate with an input point or corner of the box of valid points...just check all of those
Homework
- Solve Gathering (Kevin's Section)
- Solve GREAT + SWERC = PORTO (OLa's Section)
- Optional: Read about dijkstra's algorithm and try to solve FLowering Trails
Class 5: 2/16
CLASS CANCELLED DUE TO SNOW Scrimmage on Midatl 2008 during the class period. http://speedyguy17.info/ucpccc-master/index.php
Homework
Solve problems from midatl2008
Class 6: 2/23
CLASS CANCELLED DUE TO PLAGUE
Class 7: 3/2
Problems: http://speedyguy17.info/ucpccc-master/judge/data/midatl/2008/MidAtlantic2008.pdf Covered Trie, Trie Again (both sections)
Class 8: 3/16
CLASS CANCELLED
- Problems: http://speedyguy17.info/ucpccc-master/judge/data/ncna/2013/regional_2013_final.pdf
- Assigned problem A (easy) Bowling Score Assistant
- brute force is fast enough
- bowling score calculator
- arrange for loops wisely to get the first winning scores in lexicographical order
- problem C (hard) One Move from Towers of Hanoi
Future
Problems: http://neerc.ifmo.ru/regional/neerc-2014-statements.pdf Problems: http://acm.ro/problems.htm