Spring16: Difference between revisions

From programming_contest
Jump to navigation Jump to search
← Older edit
imported>Kmk21
No edit summary
imported>Kmk21
No edit summary
 
(54 intermediate revisions by 13 users not shown)
Line 1: Line 1:
Roster Form: ???
Roster Form: https://docs.google.com/forms/d/1xQN05Saj8lga8CtxxhtcO2_zeFwowlhX8OrJ_Ifwei0/viewform


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


=Class Requirements=
=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.
* 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.
* 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
** 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
** 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
** 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.
** 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 [[#ICPC Midatlantic Region 11/7|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.
* 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
** 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.
** 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!
** 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


=Class 0: 8/24=
https://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf tile cutting and catering
http://acm-ecna.ysu.edu/ProblemSet/ecna2014.pdf
==Notes==
==Notes==
==Homework==
==Homework==
* Fill out the course information form https://docs.google.com/forms/d/1pTPCUuD4qD_NyTjTdSdhzI1hk4rIcW0yvL8bRbsy52M/viewform
==Contests==
* ECNA 2014 problem h: [[Time Warp]] (by end of semester)
Codeforces: 1/14 11:35 am
Topcoder: 1/20 7:00 am


=Class 1:8/31=
=Class 1:1/25=
http://acm.ashland.edu/2010/problem-set.html
http://codeforces.com/contest/616
https://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf DNA sequencing and asteroids
==Presenters==
==Presenters==
==Notes==
==Homework==


Jiawei Zhang - Problem P - Vampires!
=Class 2: 2/1=
Kevin in San Jose
==Presenters==
==Notes==
==Homework==
 
=Class 3: 2/8=
==Presenters==
Morton Mo (ym84)


==Notes==
==Notes==
Vampires:
==Homework==
Advanced: finals 2014 problems C and D


* doing it with individual points is a great way to do it, and so is putting the points in a 2d array representing the maps and iterating through it. either should be fast enough
=Class 4: 2/15=
No Class: snow
==Presenters==
==Notes==
==Homework==


There are a lot of great tricks when you're working with grids like this
=Class 5: 2/22=
1) you can encode movement in an array like this. You can also do this moving in any combination of directions based on how you specify x and y delta
==Presenters==


//define all 4 possible movements
'''Jiawei Zhang''' - Load Balancer
int x_delta={1,-1,0,0};
int y_delta={0,0,1,-1};


for(int i=0;i<4;i++){//iterate over all 4 possible movements
'''Problem Statement:''' http://codeforces.com/problemset/problem/609/C


    Point cur_location=vamp_location
'''Solution and Explanation:''' http://speedyguy17.info/wiki/index.php/Load_Balancer


    while(on_map(cur_location)&&not_blocked){
==Notes==
==Homework==
http://cs.baylor.edu/~hamerly/icpc/qualifier_2013/final_problem_statements.pdf erratic ants, or shot cube


        point.x+=x_delta[i];
Finals 2014 E and K


        point.y+=y_delta[i];
=Class 6: 2/29=
==Presenters==


    }
'''Alan Guo''' - Bracket Sequence


    // Do something if we have hit a blocking character, whether mirror or person
'''Problem Statement:''' http://codeforces.com/contest/612/problem/C


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


2) when you know up front the size of something (in this case, number of vampires and humans) it's a lot easier to allocate the correct size of the array up front rather than an array list. It's less typing and a lot faster executing
==Notes==
intro: http://acmgnyr.org/year2007/h.pdf
Notes on Domino packing:


3) Java has a convenient structure for storing x/y pairs called a Point (import java.awt.point). Sometimes I use it, sometimes i use 2 arrays, one for x and one for y, sometimes i use a 2d array which contains both x and y for each point. Just different options!
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!


Photo Taking:
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.


* 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.
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)


* 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.
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!).


Vote Getting:
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.


* 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
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.


* 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 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.


* 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.
==Homework==


==Vampire Notes==
=Class 7: 3/7=
==Presenters==
Samadwara Reddy - Problem H - Qanat [ICPC 2015 World Finals]


[[Vampires]]
'''Link to Original Problem:'''
http://speedyguy17.info/data/finals/2015/icpc2015.pdf


==Homework==
'''Link to my Solution & Explanation:'''
Problem P - Vampires
http://speedyguy17.info/wiki/index.php/Qanat


=Class 2: 9/7=
Scrimmage 1: http://acm.ashland.edu/2009/Problem-Set/Problems/2009.pdf
==Notes==
==Notes==
==Homework==
==Homework==


=Class 3: 9/14=
=Class 8: 3/21=
http://mcicpc.cs.atu.edu/archives/2014/mcpc2014/browse.html
==Presenters==
==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==
==Notes==
http://midatl.fireduck.com/archive/2003/problems/MidAtlantic-2003/MidAtlantic2003.pdf
==Homework==
==Homework==


=Class 4: 9/21=
=Class 9: 3/28=
http://mcicpc.cs.atu.edu/archives/2013/mcpc2013/missing/missing.html
==Presenters==
==Presenters==
David Zhou - AJ (Digit Solitaire)
Alex Dao - Bear and Displayed Friends http://codeforces.com/problemset/problem/658/B
==Notes==
Solution and explanation can be found on this wiki page: http://speedyguy17.info/wiki/index.php/Bear_and_Displayed_Friends#Solution_-_Java
http://speedyguy17.info/wiki/index.php/Digit_Solitaire
 
==Homework==


=Class 5: 9/28=
????
==Presenters==
Alex Dao - Problem AR - Mad Scientist!
==Notes==
==Notes==
==Homework==
==Homework==


=ICPC Qualification Contest 10/3=
=Class 10: 4/4=
http://cs.ecs.baylor.edu/~hamerly/icpc/qualifier_2015/
 
=Class 5: 10/5=
http://mcicpc.cs.atu.edu/archives/2012/mcpc2012/browse.html
==Presenters==
==Presenters==
Michael Ogez does the faculty dividing powers!
Xingyu Chen
ACM 2015 Problem D
http://speedyguy17.info/data/finals/2015/icpc2015.pdf


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


Given two positive integers $n$ and $k$, find the biggest integer $i$ such that $k^{i}$ divides $n!$. Note that we are given the following bounds: $(2 ≤ n ≤ 10^{18}, 2 ≤ k ≤ 10^{12})$.


==Solutions==
'''Daniel McKee'''
===Idea===


The main idea is to take advantage of unique prime factorization to write $k=p_{1}^{\alpha_{1}} ... p_{n}^{\alpha_{n}}$. After explicitly computing this factorization, the task is just to find the $p_{j}^{\alpha_{j}}$ which appears in $n!$ the least number of times $i$, and this $i$ will be the answer. To do this, it clearly suffices to compute the number of times $p_{i}$ appears in $n!$. To do this, we can just be careful about how we count. In other words, we do not have to explicitly compute $n!$ or its prime factorization. The rest of this section will deal with this counting.\\
Problem: z-sort


Let $S$ be the number of times a given prime $p$ appears in $n!$, and let $l$ be the largest $l$ such that $p^{l}\le n$. Then I claim that
Description: http://codeforces.com/problemset/problem/652/B
\[
S = \sum_{i=1}^{l} \lfloor \frac{n}{p^{i}} \rfloor
\]
To see this, let $n_{i}$ be the number of integers $m \le n$ such that $i$ is the highest power of $p$ dividing $m$. Then
\[
S = \sum_{i=1}^{l}in_{i} = n_{1} + n_{2} + n_{2} + \dots + n_{l} + \dots + n_{l} = \sum_{i=1}^{l}\sum_{k=i}^{l}n_{k} = \sum_{i=1}^{l}\lfloor \frac{n}{p^{i}} \rfloor
\]


Now that we know how to compute $S_{j}$ for each prime $p_{j}$, it is easy to compute $i$ by taking
Solution: http://speedyguy17.info/wiki/index.php/Z_Sort
\[
i = \min_{j} \lfloor \frac{S_{j}}{\alpha_{j}} \rfloor
\]


===Runtime===
==Notes==
Prime factorization can be done in $\sqrt{k}$, and computing $S$ takes $log_{p_{j}} n$ time for each $p_{j}$. An extremely rough upper bound on $j$ is $\sqrt{k}$, so that the overall runtime is bounded roughly by $\sqrt{k} log n$.
==Homework==


===Code===
=Class 11: 4/11=
==== Solution - Java ====
==Presenters==
<syntaxhighlight line lang="java">
'''Philip Foo''' - Google Code Jam A: Counting Sheep https://code.google.com/codejam/contest/6254486/dashboard#s=p0
import java.util.ArrayList;
import java.util.Scanner;


public class DividingPowers {
'''Link to Problem''': https://code.google.com/codejam/contest/6254486/dashboard
static Scanner in = new Scanner(System.in);


public static void main(String[] args) {
'''Link to Solution:''' http://speedyguy17.info/wiki/index.php/Counting_Sheep
long caseNum=1;
long a = in.nextLong();
for(long i = 0; i<a; i++){
long n = in.nextLong();
long k = in.nextLong();
long ans = largestPower(n,k);
System.out.printf("%d\n", ans);
caseNum++;
}
}
public static long largestPower(long n, long k){
ArrayList<Long> primes = primeFactorization(k);
long minAppearance = Long.MAX_VALUE;
for(int i = 0; i <(primes.size()+1)/2; i++){
long p = primes.get(i*2);
long temp = numAppearances(n,p);
if(minAppearance> temp/primes.get(i*2+1)){
minAppearance = temp/primes.get(i*2+1);
}
}
return minAppearance;
}
private static long numAppearances(long n, Long p) {
long numAppear=0;
int i = 0;
while(Math.pow(p, i)<=n){
i++;
}
i--;
for(int j = 1; j<=i; j++){
numAppear+=n/((long)Math.pow(p, j));
}
return numAppear;
}
private static ArrayList<Long> primeFactorization(long k) {
ArrayList<Long> primes = new ArrayList<Long>();
for(long i = 2; i<=Math.sqrt(k); i++){
long j = 0;
while(k%((long)Math.pow(i, j))==0){
j++;
}
if(j>1){
primes.add(i);
primes.add(j-1);
ArrayList<Long> restPrimes = primeFactorization((long)(k/(Math.pow(i, j-1))));
i=k;
for(Long a : restPrimes){
primes.add(a);
}
}
}
if(primes.size()==0&&k!=1){
primes.add(k);
primes.add((long) 1);
}
return primes;
}


}


</syntaxhighlight>
Danny Oh - Google Code Jam B: Revenge of the Pancakes http://solorab.net/blog/2016/04/10/gcj-2016-qual-b/
 
[[Category:ICPC Problems]]
[[Category:Algorithm Easy]]
[[Category:Implementation Easy]]


==Notes==
==Homework==
==Homework==


=Class 6: 10/12=
=Class 12: 4/18=
http://mcicpc.cs.atu.edu/archives/2010/mcpc2010/browse.html
==Presenters==
==Presenters==
==Notes==
Callie Mao - Bear and Forgotten Tree 3
==Homework==


=Class 7: 10/19=
'''Link to problem:''' http://codeforces.com/contest/658/problem/C
Triviality Day
==Notes==
==Homework==


=Saturday Scrimmage: 10/24=
'''Link to solution:''' http://speedyguy17.info/wiki/index.php/Bear_and_Forgotten_Tree_3
http://gcpc.nwerc.eu/problemset_2015.pdf


=Class 8: 10/26=
Tony Qiao - Google Code Jam 1B Rank and File https://code.google.com/codejam/contest/4304486/dashboard#s=p1&a=1
http://gcpc.nwerc.eu/problemset_2011.pdf
==Presenters==


==Notes==
==Notes==
==Homework==
==Homework==


=Class 9: 11/2=
=Class 13: 4/25=
No New Problems. Final Preparations for Contest
==Presenters==
==Presenters==
Mario Oliver
==Notes==
==Notes==
==Homework==
==Homework==


=ICPC Midatlantic Region 11/7=
[[Category:2016]]
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 <br />
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++:
 
/*
*/
#include <iostream>
#include <cstring>
#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.
 
[[Category:2015]]
[[Category:CS309s]]
[[Category:CS309s]]
[[Category:ecna2014]]
[[Category:Finals2015]]
[[Category:ecna2010]]
[[Category:Finals2014]]
[[Category:ecna2009]]
[[Category:mcpc2014]]
[[Category:mcpc2013]]
[[Category:mcpc2012]]
[[category:mcpc2010]]
[[category:gcpc2011]]
[[category:gcpc2015]]
[[category:icpcq2015]]
[[category:midatl2015]]

Latest revision as of 05:52, 25 August 2016

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

Notes

Homework

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

Presenters

Notes

Homework

Class 2: 2/1

Kevin in San Jose

Presenters

Notes

Homework

Class 3: 2/8

Presenters

Morton Mo (ym84)

Notes

Homework

Advanced: finals 2014 problems C and D

Class 4: 2/15

No Class: snow

Presenters

Notes

Homework

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

Notes

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.

Homework

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

Notes

Homework

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

Homework

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

Notes

Homework

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

Notes

Homework

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/

Notes

Homework

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

Notes

Homework

Class 13: 4/25

Presenters

Notes

Homework

Retrieved from "https://wiki.speedyguy17.info/index.php?title=Spring16&oldid=648"