Spring16

Roster Form: https://docs.google.com/forms/d/1xQN05Saj8lga8CtxxhtcO2_zeFwowlhX8OrJ_Ifwei0/viewform

test server intro: http://speedyguy17.info/spring2016i/ test server advanced: http://speedyguy17.info/spring2016a

Course Objectives

• Get better at solving programming problems than you were at the beginning of the semester by learning techniques, both algorithmic and implementation, that are necessary for solving such problems

Auxiliary Benefits

• A strong grasp on fundamental algorithms that arise in other courses and may be useful in your career
• A better command of whichever language you are solving problems in
• The ability to solve small programming puzzles, many of which arise in interview type situations

Class Structure

• Class will meet each Monday
• The class will be split into 2 self selecting sections
• Each section may talk about different problems and have different assignments
  • Students may move between sections freely
  • Students participating in both sections may complete parts of requirements for each section. Please talk to me if you are unsure!

Focus for the Semester: Intro Section

The Intro section is aimed at students who have not taken 309s before, or who have, but are still looking to become comfortable with the basics. The goal is to become comfortable solving some of the easier problems which come up as well as starting to become versed in the techniques which will be necessary for solving more difficult problems.

Class Requirements

• Attend Seminar and contribute. Missing class regularly will result in a lower grade. At times during class, everyone will be asked to contribute something to the discussion. Choosing not to contribute to these discussions will be impactful.
• Solve 18 problems over the course of the semester. This comes to just over 1 problem per week.
  • Problems should come from the assigned sets. This includes any problems from the sets as well as any problems done for a scrimmage or contest
  • At times, individual problems discussed in class may be assigned as required. If these problems are regularly left uncompleted the week they are assigned, final grade will be impacted
  • Problems should be solved throughout the semester. If you solve 12 problems the last two days before the end of the semester, it won't be fun for anybody. If you participate in the contests, this should not be a problem.
• Lead the discussion of a problem (selected by you) that you have solved. Add a description of your solution (with code) to this wiki.
  • The problem should be approved by Kevin before you choose it, and it need not come from the set of problems assigned from class
  • You should sign up for the date you'd like to present on the schedule below.
  • Sign up early for your choice of problem and date!
• Participate in 5 contests over the course of the semester.
  • Topcoder, Google Code Jam, Codeforces, and Waterloo are pre-approved. Please ask if you'd like another contest to count
  • Contests happen generally at least once a week. Do them early, as I do not want people saying at the end of the semester that the times of the remaining contests conflicted with things
  • Performance in contests does not affect grades, only participation

Focus for the Semester: Advanced Section

After a successful fall semester, which saw Duke teams solve a great many problems in the ICPC regional competition, the focus is several fold:

• Continue to maintain working knowledge of Fundamental Algorithms which was developed in the past semesters. I expect each student in the class to take individual initiative in identifying the algorithms they are not yet familiar with, attempting to understand them on their own, and finally approaching the class with help. This program will be successful if we maintain continual knowledge of these algorithms at a high level.
• Focus on problem quality over quantity. Everyone who attends this section has demonstrated that they can solve basic problems. The aim is to push students to solve problems that they could not solve before, and might not have thought of approaching. It is these problems that will make the difference between winning at the regional level and not.
• Increase the amount of time spent in actual competition environments. We have spent a lot of time solving problems and scrimmaging, but the more relaxed nature of a scrimmage may not force the same mentality that you get from an actual competition.

Class Requirements

• Attend Seminar and contribute. Missing class regularly will result in a lower grade. At times during class, everyone will be asked to contribute something to the discussion. Choosing not to contribute to these discussions will be impactful.
• Solve 8 problems over the course of the semester. This comes to 2 problems a month.
  • Problems should come from the assigned sets.
    • The sets will largely be derived from world finals problems, which are both more challenging algorithmically, and generally more difficult to code
    • Problems from contests will NOT count towards this 8 UNLESS it is the hardest problem in the set, which I consider equivalent to most world finals problems. This is a change over prior semesters and due to the focus on more challenging problems.
  • Problems should be solved throughout the semester. If you solve 8 problems the last two days before the end of the semester, it won't be fun for anybody.
• Teach the solution of a problem to the class.
  • This is a slight change of simply presenting a problem, as the goal is to teach everyone, rather than to just talk
  • I will review with you your strategy for teaching the class before hand
    • This will hopefully help to ensure everyone is engaged and understands
    • You will have to think and prepare your teaching strategy before hand
  • You should post your solution on the wiki as well
• Participate in 6 contests over the course of the semester.
  • Topcoder, Google Code Jam, Codeforces, and Waterloo are pre-approved. Please ask if you'd like another contest to count
  • Contests happen generally at least once a week. Do them early, as I do not want people saying at the end of the semester that the times of the remaining contests conflicted with things
  • Performance in contests does not affect grades, only participation. I will be paying attention to your ratings though, and you should strive to improve them!
  • This is more contests than the intro section, but you have fewer problems, and contests should be easy for the members of this section

Class 0: 1/13

http://codeforces.com/contest/612/problem/C

https://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf tile cutting and catering

Contests

Codeforces: 1/14 11:35 am Topcoder: 1/20 7:00 am

Class 1:1/25

http://codeforces.com/contest/616 https://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf DNA sequencing and asteroids

Class 2: 2/1

Kevin in San Jose

Class 3: 2/8

Presenters

Morton Mo (ym84)

Homework

Advanced: finals 2014 problems C and D

Class 4: 2/15

No Class: snow

Class 5: 2/22

Presenters

Jiawei Zhang - Load Balancer

Problem Statement: http://codeforces.com/problemset/problem/609/C

Solution and Explanation: http://speedyguy17.info/wiki/index.php/Load_Balancer

Homework

http://cs.baylor.edu/~hamerly/icpc/qualifier_2013/final_problem_statements.pdf erratic ants, or shot cube

Finals 2014 E and K

Class 6: 2/29

Presenters

Alan Guo - Bracket Sequence

Problem Statement: http://codeforces.com/contest/612/problem/C

Solution and Explanation: http://speedyguy17.info/wiki/index.php/Bracket_Sequence

Notes

intro: http://acmgnyr.org/year2007/h.pdf Notes on Domino packing:

Our goal is to count the total number of ways we can put all the dominoes in. So ultimately, we're going to use a sort of recursive backtracking to figure out all possibilities. Whenever we have some sort of recursive backtracking, we have to figure out what to put as parameters to our function call. It makes sense, since we have to fill up the WHOLE space, to put the dominoes in from one side to the other. So suppose we remember how many more rows of dominoes we have to put down (w) and which of the 4 slots are taken up in the row we're working on. We will encode the second part in binary, where 0-15 represent the 2^4 == 16 different ways we can have dominoes in the row (note that each of the 4 slots in that row either has part of a domino in it, or it doesn't...that's all we remember). After we fill out a full row of dominoes, we'll move on to the next row. We quickly find we have a problem, though, as how do we know which dominoes we put down in the previous row have already taken up spots in the next row (for horizontal dominoes)??? The answer to "how do we remember stuff" when doing a recursive backtracking problem is to just add another parameter!

So now our function has THREE parameters, w, the slots open in the current row, and the slots open in the next row. Now all we have left to do is figure out for a given amount of dominoes in this row and the next, what do we have to call? An easy way to do this is to just figure it out beforehand. Lets walk through a couple examples.

Starting with no dominoes: this row = 0, next row = 0 (we'll call this 0,0) Placing a horizontal domino in the first available spot means we will have the top spot filled in both this and the next row. Since the top spot is the 4th bit, we put an 8, so the call is (8,8). Placing a vertical domino fills the 8 and 4 slot in this row, so the call is (12,0)

Starting with just one domino reaching to the top of the first row, we have (8,0), so we will be filling in from the second highest spot (always fill the leftmost column first!). Placing a horizontal domino gives us 12 (8+4) in the first row, and just 4 in the second row, where the vertical domino gives us (14,0).

The rest of the possibilities are left to you (or to calculate in code!).

Lastly, we find that if we run this algorithm naively, it will take exponential time, since to add a measly 1 to the total, we have to recurse all the way do the end, and we know the result is exponential in W. To solve this, we realize, "Hey, each time I call (w,n,m) with the same values, it will always return the same result! Why don't I just save it?" We are exactly correct. Create a w x 16 x 16 array, and each time you call your function, first check if you have already solved this particular combination. If you have, just return the result from the array. Otherwise, perform the recursion we figured out above, and store the value in the array for next time.

Notes on Surveillance: We know that this is sort of like the set cover problem, which is NP complete, but we realize that the extra structure of the problem is that the sets that each camera covers are all consecutive. If the problem were cameras covering a line, it's easy to see that you select the left most line, and then greedily select lines which overlap the current line but reach as far to the right as possible. It turns out if we randomly select a segment on a circle and perform this algorithm until we've covered the circle, we have no guarantee that we've found the minimal solution, since there was no guarantee the first line we selected was part of the solution. To solve this, we realize that if we continue around the circle indefinitely (removing segments from the tail end, and adding them to the head, eventually we will reach a segment which we have already selected and since removed. At this point, we've converged to some minimum, and the segment we've found (and thus every segment we've found since we first traversed this segment) must be part of a solution. By that, we can simply take the count of segments in our current set as the minimum.

It is guaranteed that we will traverse each segment at most once (and one segment twice), meaning the traversal count is linear in terms of number of segments. So long as we use a fast structure like a tree set to perform the lookup of the next segment, we are doing at worst O(nlogn), which should be sufficient.

Class 7: 3/7

Presenters

Samadwara Reddy - Problem H - Qanat [ICPC 2015 World Finals]

Link to Original Problem: http://speedyguy17.info/data/finals/2015/icpc2015.pdf

Link to my Solution & Explanation: http://speedyguy17.info/wiki/index.php/Qanat

Class 8: 3/21

Presenters

Harrison Suh - Comparing Two Long Integers

Link to Original Problem: http://codeforces.com/contest/616/problem/A

Link to my Solution & Explanation: http://speedyguy17.info/wiki/index.php/Compare_Two_Integers

This problem cannot be solved simply using "parseInt" and compareTo to return the greater integer, because the numbers can be too big for Java to process using Integer. So I went about solving the problem with the simplest way I could think of, which would be to compare the length of the two integers. If one number is longer than another, it is automatically larger in value than the other one. If the two integers are the same length, I iterate through each digit and find the first point of difference. Because I start at the largest digit, the first point of difference will yield which integer is larger, without having to consider any subsequent digits (they are all smaller in value than the one currently being compared). Of course, this is all after the two integers are processed to remove any leading zeroes to make sure the test of checking their lengths works and does not take the leading zeroes as actual digit-values.

Notes

http://midatl.fireduck.com/archive/2003/problems/MidAtlantic-2003/MidAtlantic2003.pdf

Class 9: 3/28

Presenters

Alex Dao - Bear and Displayed Friends http://codeforces.com/problemset/problem/658/B Solution and explanation can be found on this wiki page: http://speedyguy17.info/wiki/index.php/Bear_and_Displayed_Friends#Solution_-_Java

Class 10: 4/4

Presenters

Xingyu Chen ACM 2015 Problem D http://speedyguy17.info/data/finals/2015/icpc2015.pdf

http://www.alexandjoy.com/index.php/2016/04/04/acm-world-final-problem-d/

Daniel McKee

Problem: z-sort

Description: http://codeforces.com/problemset/problem/652/B

Solution: http://speedyguy17.info/wiki/index.php/Z_Sort

Class 11: 4/11

Presenters

Philip Foo - Google Code Jam A: Counting Sheep https://code.google.com/codejam/contest/6254486/dashboard#s=p0

Link to Problem: https://code.google.com/codejam/contest/6254486/dashboard

Link to Solution: http://speedyguy17.info/wiki/index.php/Counting_Sheep

Danny Oh - Google Code Jam B: Revenge of the Pancakes http://solorab.net/blog/2016/04/10/gcj-2016-qual-b/

Class 12: 4/18

Presenters

Callie Mao - Bear and Forgotten Tree 3

Link to problem: http://codeforces.com/contest/658/problem/C

Link to solution: http://speedyguy17.info/wiki/index.php/Bear_and_Forgotten_Tree_3

Tony Qiao - Google Code Jam 1B Rank and File https://code.google.com/codejam/contest/4304486/dashboard#s=p1&a=1