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

Vampires:

• 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

There are a lot of great tricks when you're working with grids like this 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

//define all 4 possible movements 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

   Point cur_location=vamp_location

   while(on_map(cur_location)&&not_blocked){

       point.x+=x_delta[i];

       point.y+=y_delta[i];

   }

   // Do something if we have hit a blocking character, whether mirror or person

}

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

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!

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

There are a few methods of solving this problem. The simplest way is to create a 2D grid where each point can be a wall, a vampire, a mortal, or a mirror. These 'points' can either be their own objects or can be mapped to a single integer. Then, we simply iterate through every vampire and go in each cardinal direction and see if any mirrors reflect back to it (ignoring all the irrelevant objects).

Code

Solution - Java

package Completed;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author Jiawei
 * Completed
 */
public class Vampires {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int counter = 0;
		while (sc.hasNext()) {
			counter++;
			int numVamp = sc.nextInt();
			int numOrd = sc.nextInt();
			int numMir = sc.nextInt();
			
			if (numVamp==0 && numOrd ==0 && numMir==0) {
				break;
			}
			
			boolean none = true;

			ArrayList<Integer> xVamp = new ArrayList<Integer>();
			ArrayList<Integer> yVamp = new ArrayList<Integer>();
			ArrayList<Integer> nVamp = new ArrayList<Integer>();
			for (int i = 0; i < numVamp; i++) {
				xVamp.add(sc.nextInt());
				yVamp.add(sc.nextInt());
				nVamp.add(i+1);
			}

			ArrayList<Integer> xOrd = new ArrayList<Integer>();
			ArrayList<Integer> yOrd = new ArrayList<Integer>();
			for (int i = 0; i < numOrd; i++) {
				xOrd.add(sc.nextInt());
				yOrd.add(sc.nextInt());
			}

			ArrayList<Integer> xMir = new ArrayList<Integer>();
			ArrayList<Integer> yMir = new ArrayList<Integer>();
			ArrayList<String> dMir = new ArrayList<String>();
			for (int i = 0; i < numMir; i++) {
				String direction = sc.next();
				int x1 = sc.nextInt();
				int y1 = sc.nextInt();
				int x2 = sc.nextInt();
				int y2 = sc.nextInt();
				int mirrorTiles = 0;
				if (x1 == x2) {
					// North-South wall or one tile
					mirrorTiles = Math.abs(y2 - y1) + 1;
					if (y2 >= y1) {
						for (int j = y1; j <= y2; j++) {
							xMir.add(x1);
							yMir.add(j);
							dMir.add(direction);
						}
					} else if (y2 < y1) {
						for (int j = y2; j <= y1; j++) {
							xMir.add(x1);
							yMir.add(j);
							dMir.add(direction);
						}
					}
				} else if (y1 == y2) {
					// East-West wall
					mirrorTiles = Math.abs(x2 - x1) + 1;
					if (x2 >= x1) {
						for (int j = x1; j <= x2; j++) {
							xMir.add(j);
							yMir.add(y1);
							dMir.add(direction);
						}
					} else if (x2 < x1) {
						for (int j = x2; j <= x1; j++) {
							xMir.add(j);
							yMir.add(y1);
							dMir.add(direction);
						}
					}
				}

			}

			// for each vampire, find closest mirror in each of four directions
			// facing toward it
			
			System.out.printf("Case %d:\n", counter);
			
			for (int i=0; i<xVamp.size(); i++) {
				boolean eastTrue = false;
				boolean southTrue = false;
				boolean northTrue = false;
				boolean westTrue = false;
				int[] all4 = findMirrors(xVamp.get(i),yVamp.get(i),xMir,yMir,dMir);
				int[] block4 = findBlocks(xVamp.get(i),yVamp.get(i),xMir,yMir,dMir,xOrd,yOrd);
				if (all4[0]!=Integer.MAX_VALUE && all4[0]<block4[0]) {
					northTrue = true;
				}
				if (all4[1]!=Integer.MAX_VALUE && all4[1]<block4[1]) {
					eastTrue = true;
				}
				if (all4[2]!=Integer.MAX_VALUE && all4[2]<block4[2]) {
					southTrue = true;
				}
				if (all4[3]!=Integer.MAX_VALUE && all4[3]<block4[3]) {
					westTrue = true;
				}
				
				
				if (westTrue || southTrue || eastTrue||northTrue) {
					none = false;
					System.out.printf("vampire %d",nVamp.get(i));
					if (eastTrue) {
						System.out.print(" east");
					}
					if (northTrue) {
						System.out.print(" north");
					}
					if (southTrue) {
						System.out.print(" south");
					}
					if (westTrue) {
						System.out.print(" west");
					}
					System.out.println();
				}
				//System.out.printf("Vamp: %d %d; North: %d; East: %d; South: %d; West: %d\n",xVamp.get(i), yVamp.get(i),all4[0],all4[1],all4[2],all4[3]);
			}
			if (none) {
				System.out.println("none");
			}
		}

	}

	public static int[] findMirrors(int vampX, int vampY,
			ArrayList<Integer> mirrorX, ArrayList<Integer> mirrorY,
			ArrayList<String> mirrorD) {
		int closestNorth = Integer.MAX_VALUE;
		int closestEast = Integer.MAX_VALUE;
		int closestSouth = Integer.MAX_VALUE;
		int closestWest = Integer.MAX_VALUE;
		int[] output = new int[4];

		ArrayList<Integer> mirrorsNS = indexOfAll(vampX, mirrorX);
		ArrayList<Integer> mirrorsEW = indexOfAll(vampY, mirrorY);

		// find all south-facing mirrors north of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (mirrorD.get(index).equals("S") && mirrorY.get(index)>vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestNorth) {
					closestNorth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}

		// find all north-facing mirrors south of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (mirrorD.get(index).equals("N") && mirrorY.get(index)<vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestSouth) {
					closestSouth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}

		// find all west-facing mirrors east of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (mirrorD.get(index).equals("W") && mirrorX.get(index)>vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestEast) {
					closestEast = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}

		// find all east-facing mirrors west of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (mirrorD.get(index).equals("E") && mirrorX.get(index)<vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestWest) {
					closestWest = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}
		output[0] = closestNorth;
		output[1] = closestEast;
		output[2] = closestSouth;
		output[3] = closestWest;
		return output;
	}
	
	public static int[] findBlocks(int vampX, int vampY,
			ArrayList<Integer> mirrorX, ArrayList<Integer> mirrorY,
			ArrayList<String> mirrorD, ArrayList<Integer> mortalX, ArrayList<Integer> mortalY) {
		int closestNorth = Integer.MAX_VALUE;
		int closestEast = Integer.MAX_VALUE;
		int closestSouth = Integer.MAX_VALUE;
		int closestWest = Integer.MAX_VALUE;
		int[] output = new int[4];

		ArrayList<Integer> mirrorsNS = indexOfAll(vampX, mirrorX);
		ArrayList<Integer> mirrorsEW = indexOfAll(vampY, mirrorY);
		ArrayList<Integer> mortalsNS = indexOfAll(vampX, mortalX);
		ArrayList<Integer> mortalsEW = indexOfAll(vampY, mortalY);

		// find all south-facing blocks north of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (!mirrorD.get(index).equals("S") && mirrorY.get(index)>vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestNorth) {
					closestNorth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}
		for (int i = 0; i < mortalsNS.size(); i++) {
			int index = mortalsNS.get(i);
			if (mortalY.get(index)>vampY) {
				if (Math.abs(mortalY.get(index) - vampY) < closestNorth) {
					closestNorth = Math.abs(mortalY.get(index) - vampY);
				}
			}
		}

		// find all north-facing mirrors south of vampire
		for (int i = 0; i < mirrorsNS.size(); i++) {
			int index = mirrorsNS.get(i);
			if (!mirrorD.get(index).equals("N") && mirrorY.get(index)<vampY) {
				if (Math.abs(mirrorY.get(index) - vampY) < closestSouth) {
					closestSouth = Math.abs(mirrorY.get(index) - vampY);
				}
			}
		}
		for (int i = 0; i < mortalsNS.size(); i++) {
			int index = mortalsNS.get(i);
			if (mortalY.get(index)<vampY) {
				if (Math.abs(mortalY.get(index) - vampY) < closestSouth) {
					closestSouth = Math.abs(mortalY.get(index) - vampY);
				}
			}
		}

		// find all west-facing mirrors east of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (!mirrorD.get(index).equals("W") && mirrorX.get(index)>vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestEast) {
					closestEast = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}
		for (int i = 0; i < mortalsEW.size(); i++) {
			int index = mortalsEW.get(i);
			if (mortalX.get(index)>vampX) {
				if (Math.abs(mortalX.get(index) - vampX) < closestEast) {
					closestEast = Math.abs(mortalX.get(index) - vampX);
				}
			}
		}

		// find all east-facing mirrors west of vampire
		for (int i = 0; i < mirrorsEW.size(); i++) {
			int index = mirrorsEW.get(i);
			if (!mirrorD.get(index).equals("E") && mirrorX.get(index)<vampX) {
				if (Math.abs(mirrorX.get(index) - vampX) < closestWest) {
					closestWest = Math.abs(mirrorX.get(index) - vampX);
				}
			}
		}
		for (int i = 0; i < mortalsEW.size(); i++) {
			int index = mortalsEW.get(i);
			if (mortalX.get(index)<vampX) {
				if (Math.abs(mortalX.get(index) - vampX) < closestWest) {
					closestWest = Math.abs(mortalX.get(index) - vampX);
				}
			}
		}
		
		output[0] = closestNorth;
		output[1] = closestEast;
		output[2] = closestSouth;
		output[3] = closestWest;
		return output;
	}

	public static ArrayList<Integer> indexOfAll(Object obj, ArrayList list) {
		// from stackoverflow
		ArrayList<Integer> indexList = new ArrayList<Integer>();
		for (int i = 0; i < list.size(); i++)
			if (obj.equals(list.get(i)))
				indexList.add(i);
		return indexList;
	}
}

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

This problem is quite easy; the idea is to write a function that checks the number of digits and the number, and then play the game. A more elegant way to check the number of digits is to convert it to a string and check the length.

Code

Solution - Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class digits {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int counter = 1;
		while (true) {
			int next = scan.nextInt();
			if (next == 0) {
				break;
			}
			scan.nextLine();
			// System.out.print("Case " + counter + ":");
			ArrayList<Integer> input = new ArrayList<Integer>();
			input.add(next);
			ArrayList<Integer> list = play(input);
			Iterator<Integer> iter = list.iterator();
			while (iter.hasNext()) {
				System.out.print(iter.next());
				if (iter.hasNext()) {
					System.out.print(" ");
				}
			}
			System.out.println();
			counter++;
		}
	}

	private static ArrayList<Integer> play(ArrayList<Integer> in) {
		int last = in.get(in.size() - 1);
		if (length(last) > 1) {
			int product = 1;
			for (int i = length(last); i > 0; i--) {
				// System.out.println((int) Math.pow(10, i - 1));
				int digit = last / ((int) Math.pow(10, i - 1));
				product *= digit;
				last -= digit * (((int) Math.pow(10, i - 1)));
			}
			in.add(product);
			return play(in);
		} else {
			return in;
		}
	}

	private static int length(int in) {
		if (in == 100000) {
			return 6;
		} else if (in >= 10000) {
			return 5;
		} else if (in >= 1000) {
			return 4;
		} else if (in >= 100) {
			return 3;
		} else if (in >= 10) {
			return 2;
		} else {
			return 1;
		}
	}
}

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/