Spring15

Roster: https://docs.google.com/spreadsheets/d/1CEfNGq704EN6WhBqrFYFrkYb4wDWU4zV9wznkt5TxOU/edit#gid=200319886

test server: http://speedyguy17.info/ucpccc-master/

Class 0: 1/7

Notes

• Input and Output
• Testing
• Debugging
• Covered Judging Troubles

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

Class 10: 3/30

• scrimmage
• Problems: http://speedyguy17.info/ucpccc-master/judge/data/midatl/2009/MidAtlantic2009.pdf

Class 11: 4/6

CLASS CANCELLED and WE WON THE CHAMPIONSHIP!

Class 12: 4/13

• Problems: google code jam qualification round
  • problem A_ standing ovation:
    • index indicates 'level of shyness'
    • greedy (left to right, if sum of pre digits + result >= current digits' index, keep going, otherwise add the difference to result)
  • problem B_ infinite house of pancakes:

Future

Problems: http://neerc.ifmo.ru/regional/neerc-2014-statements.pdf Problems: http://acm.ro/problems.htm