Fall15: Difference between revisions

From programming_contest
Jump to navigation Jump to search
← Older edit
imported>Jz134
No edit summary
No edit summary
 
(23 intermediate revisions by 9 users not shown)
Line 36: Line 36:


==Notes==
==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:
Photo Taking:
Line 85: Line 54:
==Vampire Notes==
==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).
[[Vampires]]
 
===Code===
==== Solution - Java ====
<syntaxhighlight line lang="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;
}
}
 
</syntaxhighlight>


==Homework==
==Homework==
Line 410: Line 75:
David Zhou - AJ (Digit Solitaire)
David Zhou - AJ (Digit Solitaire)
==Notes==
==Notes==
 
http://speedyguy17.info/wiki/index.php/Digit_Solitaire
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 ====
<syntaxhighlight line lang="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;
}
}
}
</syntaxhighlight>


==Homework==
==Homework==
Line 501: Line 94:
Michael Ogez does the faculty dividing powers!
Michael Ogez does the faculty dividing powers!


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


Line 535: Line 127:
=ICPC Midatlantic Region 11/7=
=ICPC Midatlantic Region 11/7=
http://radford.edu/~acm/midatl/
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:2015]]
Line 547: Line 205:
[[category:gcpc2011]]
[[category:gcpc2011]]
[[category:gcpc2015]]
[[category:gcpc2015]]
[[category:icpcq2015]]
[[category:naq2015]]
[[category:midatl2015]]
[[category:midatl2015]]

Latest revision as of 02:51, 14 February 2023

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

Notes

Homework

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

Notes

Homework

Class 3: 9/14

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

Presenters

Notes

Homework

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

Homework

Class 5: 9/28

????

Presenters

Alex Dao - Problem AR - Mad Scientist!

Notes

Homework

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!

Homework

Class 6: 10/12

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

Presenters

Notes

Homework

Class 7: 10/19

Triviality Day

Notes

Homework

Saturday Scrimmage: 10/24

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

Class 8: 10/26

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

Presenters

Notes

Homework

Class 9: 11/2

No New Problems. Final Preparations for Contest

Presenters

Mario Oliver

Notes

Homework

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.

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