Spring15: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 m 16 revisions imported |
imported>Kmk21 No edit summary |
||
| Line 12: | Line 12: | ||
* Solve one problem from [[nwerc2014]], submit it to http://icpc.egr.duke.edu, and contribute to the wiki page for the problem you solved | * 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_Constitution | DPCC]] | * Consider one of the officer positions in [[DPCC_Constitution | DPCC]] | ||
=Class 1: 1/14= | =Class 1: 1/14= | ||
==Notes== | ==Notes== | ||
Revision as of 19:08, 31 January 2015
test server: http://speedyguy17.info/ucpccc-master/
Class 0: 1/7
Notes
- Reading Input (also tips on eclipse debugging and submission instructions)
- Covered nwerc2014 Problem J
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)