Fall15

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

Why I want to take the course for credit form: https://docs.google.com/forms/d/1ekziTDxa8xpXQp6m6DfsbXlL0m8dTFZdi9Fo-0zW68M/viewform?usp=send_form

test server: http://speedyguy17.info/fall15/

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 scrimmages as well as solve the required problems as they are assigned, this should not be an issue
  • Solving Borg^3 problems can be used, but will not be full credit, as some are very simple or very similar to others. Please ask me if you want to use any of these for credit.
• Participate in the ICPC regional contest on 11/7. Details found on the website linked below
  • Others not taking the class for credit are highly encouraged to participate in this contest as well, but must participate regularly in the class, and must participate in the qualification contest on 10/3
• Participate in the ICIC qualification contest on 10/3
• 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!

Class 0: 8/24

http://acm-ecna.ysu.edu/ProblemSet/ecna2014.pdf

Homework

• Fill out the course information form https://docs.google.com/forms/d/1pTPCUuD4qD_NyTjTdSdhzI1hk4rIcW0yvL8bRbsy52M/viewform
• ECNA 2014 problem h: Time Warp (by end of semester)

Class 1:8/31

http://acm.ashland.edu/2010/problem-set.html

Presenters

Jiawei Zhang - Problem P - Vampires!

Notes

Photo Taking:

• whenever we have a relatively small number of points in a problem space (the locations of the people in the whole area), we can often use them to optimize our search. I call the technique "interesting points". In this case we know that in some optimal solution, we can structure the photos such that a human is always on the edge of the photo, limiting our search to only pictures with humans on the edge, rather than all possible picture angles.

• When you can avoid it, don't use slopes. slopes have the "infinity problem" use angles. If you have to translate to slopes, do it as late as possible, and make sure you deal with infinite slopes. Otherwise just use atan2 and get the absolute angle.

Vote Getting:

• Any time you have to optimize multiple functions that have diminishing returns, it's likely going to be some sort of greedy algorithm. In this case, each subsequent dollar we put towards a district got us diminishing returns, so for each dollar, simply evaluate each district and find the one that gets us the best return

• The best way to do this is with a heap type structure. Java has a treeset or priority queue, and c++ has a priority queue as well. I recommend the treeset in java because while you must have distinct elements (your custom comparator MUST break ties or the set will only store the item once), it has the advantage of having log(n) removal, while the priority queue has linear removal. In any case the following applies: it is good practice to break ties when you write your comparator (you only return 0 if the comparison is between two items that are actually the same item), and you should remove an item from the queue before updating it (and presumably reinserting). Further, your comparator should be commutative ( compare(a,b) = -1*compare(b,a)).

• It was suggested we take all possible divisions of the money (called the "integer partitions") and assign the largest partition to the district with the largest delta*n (and so on), and take the partition which gets us the most votes overall. This solution ("smart" brute force) is correct, but the question is whether it will run fast enough. It turns out there are 190,569,292 unique integer partitions of 100. For each of these 100 partitions we have to do 100 work, doing the calculations for every district. Combined with the cost of calculating subsequent partitions, I would say this probably won't run fast enough, but if you'd like to try, please feel free to code it up! There are some problems to which integer partitions are the answer.

Vampire Notes

Vampires

Homework

Problem P - Vampires

Class 2: 9/7

Scrimmage 1: http://acm.ashland.edu/2009/Problem-Set/Problems/2009.pdf

Class 3: 9/14

http://mcicpc.cs.atu.edu/archives/2014/mcpc2014/browse.html

Class 4: 9/21

http://mcicpc.cs.atu.edu/archives/2013/mcpc2013/missing/missing.html

Presenters

David Zhou - AJ (Digit Solitaire)

Notes

http://speedyguy17.info/wiki/index.php/Digit_Solitaire

Class 5: 9/28

????

Presenters

Alex Dao - Problem AR - Mad Scientist!

ICPC Qualification Contest 10/3

http://cs.ecs.baylor.edu/~hamerly/icpc/qualifier_2015/

Class 5: 10/5

http://mcicpc.cs.atu.edu/archives/2012/mcpc2012/browse.html

Presenters

Michael Ogez does the faculty dividing powers!

Class 6: 10/12

http://mcicpc.cs.atu.edu/archives/2010/mcpc2010/browse.html

Class 7: 10/19

Triviality Day

Saturday Scrimmage: 10/24

http://gcpc.nwerc.eu/problemset_2015.pdf

Class 8: 10/26

http://gcpc.nwerc.eu/problemset_2011.pdf

Class 9: 11/2

No New Problems. Final Preparations for Contest

Presenters

Mario Oliver

ICPC Midatlantic Region 11/7

http://radford.edu/~acm/midatl/

Class 11/16

Presenters

Fred Zhang (hz115) : Missing_Pages

Class 11/23

Presenters

Christine Zhou: Word Cloud

Will Weiyao Wang: Reverse Robot

Class 11/30

Presenters

Haoyang Gu: Mirror, Mirror on the wall
Tyler Webner: Quine

Notes

This is a pretty simple problem, just using a map to store all the characters that has symmetry and then run through the string to check whether each of the character has symmetry. If all of the characters have symmetries, then print out all of the map value; and if not, just print out "Invalid". And here is my code written in c++:

/*

• /

1. include <iostream>
2. include <cstring>
3. include <map>

using namespace std;

int main(){

   map<char,char> ma;
   ma.clear();
   ma['b']='d';
   ma['d']='b';
   ma['p']='q';
   ma['q']='p';
   ma['i']='i';
   ma['o']='o';
   ma['v']='v';
   ma['w']='w';
   ma['x']='x';
   string x;
   while(cin>>x){
       if(x=="#")
           break;
       int fail=0;
       //check whether satisfy
       for(int i=0;i<x.length();i++){
           if(!ma.count(x[i])){
               fail=1;
               break;
           }
       }
       
       if(fail)
           cout << "INVALID" << endl;
       else{
           string tmp="";
           for(int i=x.length()-1;i>=0;i--){
               tmp=tmp+ma[x[i]];
           }
           cout << tmp << endl;
       }
           
   }
   return 0;

}

Run time: We basically scan through the string. If the string is invalid, then we will run through the string once, and if it is valid, we will scan through the string twice. Thus, the running time is linear.