Programming Contest 2011

--D. Thiebaut 15:41, 24 March 2011 (EDT)

---

The TEAM

• Julia Burch, '11
• Janet Guo, '12
• Yang Li, '11
• Millie Walsh (alternate)
• (chauffeur: Dominique Thiebaut)

Contest Web Page

• The contest takes place at WNEC, in Springfield, MA, this year.
• http://www.ccscne.org/2011/contest.php

Date

• April 15th 9am - Noon. The contest is held concurrently with the conference workshops and before the paper sessions.
  • Detailed Timeline
    • 7:45 - 8:45 a.m.Breakfast and Registration of Teams and Team MembersRegistration Area
    • 7:45 - 8:45 a.m.Computers available for practiceTBA
    • 8:45 - 9:00 a.m.Initial Meeting and Presentation of the ProblemsTBA
    • 9:00 a.m. - NoonContestTBA
    • Noon - 12:45 p.m.Luncheon for Programming TeamsTBA
    • 7:00 - 9:00 p.m.Dinner / Announcement of Contest WinnersTBA

Details

• The programming languages for the contest are Java and C/C++.
• Rules for the contest are similar to the ACM Programming Contest.
• The winners of the contest will be announced at the Conference Banquet.
• A trial website will be made available a month before the contest so teams can familiarize themselves with the contest shell.

Rules

These are the ACM Programming Contest Rules. The rules from the CCSCNE contest differ in a few ways, notably the length of time: 3 hours instead of 5. The text below is taken from http://en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest

The ICPC is a team competition. Current rules stipulate that each team consist of three students. Participants must be university students, who have had less than five years of university education before the contest. Students who have previously competed in two World Finals or five regional competitions are ineligible to compete again.[1][2]

During contest, the teams are given 5 hours (3 for the CCSCNE contest) to solve between 8 and 12 programming problems (with 8 typical for regionals and 10 for finals). They must submit solutions as programs in C, C++, or Java. Programs are then run on test data. If a program fails to give a correct answer, the team is notified about that and they can submit another program.

The winner is the team which correctly solves most problems. If necessary to rank teams for medals or prizes among tying teams, the placement of teams is determined by the sum of the elapsed times at each point that they submitted correct solutions plus 20 minutes for each rejected submission of a problem ultimately solved.

For example, consider a situation when two teams, Red and Blue, tie by solving two problems each. The team Red submitted their solutions to A and B at 1:00 and 2:45 after the beginning of the contest. They had a rejected run on C, but it was ignored since they didn't solve C. The team Blue submitted solutions to problems A and C at 1:20 and 2:00 after the beginning. They had one rejected run on C. Then, the total time is 1:00+2:45=3:45 for team Red and 1:20+2:00+0:20=3:40 for team Blue. The tie is broken in favor of Team Blue.

Compared to other programming contests (for example, International Olympiad in Informatics), the ICPC is characterized by a large number of problems (8 or more problems in just 5 hours). Another feature is that each team can use only one computer, although teams have three students. This makes the time pressure even greater. Good teamwork and ability to withstand pressure is needed to win.

Assignments

For next week April 1st (no jokes!)

• • practice writing simple I/O programs that follow the general rules: the problem name is the class name (with a lowercase first letter) and reads its information from an input file with the same name and an extension .in
  • use emacs and the command line in Linux
  • learn how to do the same thing in Windows (and send me your discoveries)
  • Select several sample problems and write an input/output program that will read the information and spit it out nicely formatted, and where you show the name of the data with the numbers.
  • Pick one sample problem that you think is easy, try to solve it, and bring your solution, or your sketch of the solution for next time.

Resources

Practicing

• Ed's Programming Contest Problem Archive (fairly old problems)
• the official ACM archive at Baylor University.
• Taken from the Algorithmist
  • http://uva.onlinejudge.org/ - The Valladolid University Online Judge. Over N problems, for a reasonable value of N. The problems are culled from old contests, and online contests.
  • http://acmicpc-live-archive.uva.es/nuevoportal/ - The 2000's ACM-ICPC Live Archive Around the World. Contains actual problems from regionals and finals from 2000 on.
  • http://www.topcoder.com - Weekly programming competitions from algorithms to components to marathons.
  • http://mathschallenge.net/index.php?section=project - Project Euler consists challenging mathematical or computer science problems.
  • http://spoj.sphere.pl - One of the earliest judges with many support for many different languages.

I/O In Java

• A Java class for doing simple I/O
• A good overview of Java I/O
• text input/output in Java. Read about the ability to rewind the input with the mark and reset functions.

Basic Strategies

• Basic Strategy from Loyola University (Good read!)
• Programming challenges: the programming contest training manual, a book on Google.books.

Learn by Heart!

Input from the keyboard, output to screen

• Java code

// basic java skeleton with Kbd and Screen IO 

import java.util.Scanner;

class SampleIOkbd { //throws Exception {  
    // change filebase appropriately for the problem 
    // often have static (global) variables for a central data structure

    static int age;
static int weight;
    static double salary;
    static String name;

    public static void main(String[] args) throws Exception {

// declare input scanner
Scanner in = new Scanner( System.in ); 

// get data 
System.out.print( "name: " );
name = in.nextLine();

System.out.print( "salary: " );
salary = in.nextDouble();
  
System.out.print( "age and weight: " );
age = in.nextInt();
        weight = in.nextInt();

// print all
System.out.printf( "%s has a salaray of $%1.2f, is %d years old and weights %d lbs.\n\n",
                      name, salary, age, weight );

    } 
}

• Sample execution

javac SampleIOkbd.java

java SampleIOkbd
name: Lea
salary: 100.11
age and weight: 20
160
Lea has a salaray of $100.11, is 20 years old and weights 160 lbs.

• Sample execution using redirection

cat > data.in
Leo
99.76
21
178
^D                   (that's control-D)

java SampleIOkbd < data.in
name: salary: age and weight: Leo has a salaray of $99.76, is 21 years old and weights 178 lbs.

Multi-line input from Keyboard (use redirection!)

• Java source

import java.util.ArrayList;
import java.util.Scanner;


public class SampleIOFile {

static ArrayList<String> lines = new ArrayList<String>();

    public static void main(String[] args) throws Exception {
Scanner in = new Scanner( System.in );
System.out.println( "Enter lines now!" );
while ( in.hasNext() ) {
String line = in.next();
lines.add( line );
}

System.out.printf( "You have entered %d lines:\n", lines.size() );
for ( int i=0; i<lines.size(); i++ ) {
          System.out.println( lines.get(i) );
          }
    }
    
}

• Sample output

javac SampleIOFile.java 

java SampleIOFile

Enter lines now!
Elizabeth Taylor
Barry Bonds
American Idol
Jobless claims
Portugal
Mobile and Wireless
Nuclear power
Gaza
Nintendo 3DS
Jeremy Morlock
^D
You have entered 11 lines:
Elizabeth Taylor
Barry Bonds
American Idol
Jobless claims
Portugal
Mobile and Wireless
Nuclear power
Gaza
Nintendo 3DS
Jeremy Morlock

Input from a File

• Java code

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SampleIOFile2 {

/**
 * @param args
  * @throws FileNotFoundException
   */
   public static void main(String[] args) throws Exception {

   String file = "data.in";  
   if (args.length > 0)
   file = args[0];  
   
   Scanner in = new Scanner(new File(file));
   int wCount = 0;
   //--- read one word at a time ---
   while (in.hasNext()) {
   String word = in.next();
   System.out.printf("%3d: %s\n", ++wCount, word);
   }
   in.close();
   
   //--- reopen in scanner ---
                //--- read one line at a time ---
                in = new Scanner(new File(file));
                int lCount = 0;
                while ( in.hasNext() ) {
                String line = in.nextLine();
                System.out.printf( "%3d: %s\n", ++lCount, line );
                }

                }

}

Output to File

import java.io.BufferedWriter;
import java.io.FileWriter;

public class SampleIOFile3 {

public static void main(String[] args) throws Exception {

try {
// Create file
FileWriter fstream = new FileWriter("data.out");
BufferedWriter out = new BufferedWriter(fstream);
out.write("Hello World");

out.close();
} catch (Exception e) {// Catch exception if any
System.err.println("Error: " + e.getMessage() );
}
}
}

Sample Problems

Below are a few problems taken from The Competitive Learning Institute (CLI), where you can find more problems.

4900 - Cut It Out!

Television's Toddler Time's topic taught to toddler Tommy Tiwilliger today was triangles (and the letter T)! Tommy became so enamored by triangles that immediately after the show ended, he grabbed his safety scissors and the nearest sheets of paper he could find and started cutting out his own triangles. After about 15 minutes each paper had one triangular shaped hole cut out of it. But Tommy wasn't finished yet. He noticed he could divide each of the original triangles into two triangles with a single cut starting from one corner. He spent another 15 minutes doing just that. Things would have gone along swimmingly, except that Tommy's mother eventually came into the room and noticed that the original sheets of paper were part of a very important document for a legal case she was working on (involving a lover's triangle). After carefully removing Tommy from the room and counting slowly to 10 (a triangular number), she went about trying to reconstruct the pages after gathering together the now randomly scattered triangles. Your job is to help her by writing a little program to determine which triangles go where (and try to get it done before tomorrow's episode of Toddler Time on papier- mâchè).

Input

Each test case will start with an integer n 20 indicating the number of holes cut out, followed by the coordinates of the holes, one hole per line. These holes are assumed to be numbered 1, 2,..., n. Following this will be the coordinates of the 2n triangles resulting from the bisections, one triangle per line. These triangles are assumed to be numbered 1, 2,..., 2n and are listed in no particular order. The specification of any hole or triangle will have the form x

1
y
1
x
2
y
2
x
3
y
3

where each xi and yi will be to the nearest thousandth and | xi|,|yi| 200.

No two holes will be congruent and no two triangles will be congruent. A value of n = 0 will terminate input.

Output

For each test case, you should output the case number and then n lines as follows:

Hole 1: t1a, t1b 
Hole 2: t2a, t2b
...
Hole n: tna, tnb

where t1a, t1b are the two triangles which fill hole 1, t2a, t2b are the two triangles which fill hole 2, etc. Always print the lower of the two numbers first on any line. Triangles should not be flipped over when filling a hole. Each test case will have a unique solution. Separate the output for each test case with a blank line. Note: when processing the triangles and checking for equality of lengths, angles or trigonometric values, you may assume that two items are equal if they differ by less than 0.01.

Sample Input

1 
18.691 6.103 21.668 13.709 21.332 25.894 
59.388 30.873 55.299 36.186 61.45 22.97 
4900 - Cut It Out! 1/267.828 85.496 60.751 72.752 59.2 67.49 
3 
18.73 4.012 6.662 7.557 14.035 7.478 
14.869 32.398 32.341 31.772 7.522 29.674 
25.272 6.868 4.572 2.014 10.487 16.121 
26.135 53.073 44.18 50.723 40.31 42.91 
86.601 29.95 70.542 17.088 66.77 14.88 
90.344 89.528 92.179 88.665 87.99 82.54 
39.327 62.11 35.033 57.127 18.14 63.89 
37.13 80.202 36.308 75.111 34.28 75.11 
14.043 68.482 15.22 55.423 10.42 75.43 
0

Sample Output

Case 1:  
Hole 1: 1, 2 
Case 2:  
Hole 1: 3, 5
Hole 2: 2, 6
Hole 3: 1, 4

Hints

Here is a good reference for computing the area of a triangle.

Flip It!

Assume you have a set of cards laid out in an n by m grid. The cards are numbered and some are face up and others are face down. We can collapse the grid into a single pile by using a series of flips, each of which is one of the four following types:

Top Flip :

Here the cards in the top row are flipped over onto the corresponding cards on the row beneath them. Note that if a card is face up in the top row, it becomes face down after the flip, and vice versa. If the top row contains one or more piles of cards, each entire pile is flipped over like a stack of pancakes as it is moved to the lower row.

Bottom Flip :

Same as the Top Flip, but now the bottom row is flipped onto the next-to-bottom row.

Left Flip :

Flip the cards in the left-most column onto the next-to-leftmost column.

Right Flip :

Flip the cards in the rightmost column onto the next-to-rightmost column. After a series of n + m - 2 flips, the cards will be in a single pile, some cards face up and some face down. Your job is to determine the order of the face up cards in this final pile.

Input

Each test case will start with a line containing two positive integers n m indicating the number of rows and columns in the grid. After this will come n rows of m integers indicating each card's number and its orientation. (The first row is the top row and the first value in each row is the leftmost card.) If a value is a positive integer k that means card k is at the location face up; if a value is a negative integer - k that means card k is at the location face down. (k will never be zero.) After these n rows there will be one more line containing n + m - 2 characters indicating the order of flips to apply to the grid. Each character will be either T, B, L or R corresponding to a top, bottom, left or right flip. All flip sequences will be legal, i.e., you won't be asked to do more than n - 1 top and bottom flips or m - 1 left and right flips. The maximum value for n and m is 20. A line containing two zeros will terminate input.

Output

For each test case, output the case number followed by a list of the numbers of all of the face up cards in the final deck, starting from the bottom of the deck. Follow the format used in the examples.

Sample Input

2 3 
4 -17 -8 
6 23 -5 
LRB 
1 1 
-3 

1 1 
3 

0 0

Sample Output

Case 1: 8 6 
Case 2: 
Case 3: 3

Maze

We are all familiar with conventional mazes laid out on a 2-D grid. A 3-D maze can be constructed as follows: Consider a hollowed out cube aligned along the x, y and z axes with one corner at (0,0,0) and the opposite corner at (n - 1, n - 1, n - 1). On each face of the cube is a 2-D maze made by removing a subset of 1 x 1 x 1 cubes from the face (no edge cubes are removed). The object of the maze is to move a marker located inside the cube from an initial location of (1,1,1) to the final destination of (n - 2, n - 2, n - 2). However, attached to this marker are 6 rods, each protruding through one face of the cube. The movement of these rods is constrained by the 2-D mazes on the faces. The picture below gives an example of a 7 x 7 x 7 maze. Note that this maze is not physically realizable since some faces (e.g., the front face containing the letter ``A") have cubes that are disconnected from the edges of the face. Such mazes are allowed in this problem.

The black regions indicate open spaces where the rods can move. The figure to the right specifies the possible directions that the rods can move (Forward, Back, Left, Right, Up, Down) and also defines the labels for the six sides of the cube. In the maze above, the rods are shown in their initial position centered at (1,1,1). From here they can not move Forward, Backward, Right, Left or Down, but they can move Up (assuming there are open spaces for the two back rods to move to).

To specify a cube, a description of each face must be given. For this problem, the order and orientations of each face are given in the diagram below.

The first square represents the Forward face oriented so that the shared edge with the Up face is on top and the shared edge with the Right face is on the right, the second square represents the Right face oriented with the shared edge with the Up face on top and the shared edge with the Back face on the right, and so on. Your job is to solve such mazes in the minimum number of moves.

Input

Each test case will start with a single line containing the value of n, where n lies between 4 and 30, inclusive. Next will come descriptions of each face in the order and orientation shown above. The description of each face will consist of n lines each containing one string of length n. The characters in the string will be either a blank or `X', indicating either an empty or full square, respectively. The last test case will be followed by a line containing 0.

Output

Output will consist of one line for each test case. Each line will contain a description of a minimum-move solution that moves the marker from cell (1,1,1) to cell (n - 2, n - 2, n - 2). Moves are either F, B, L, R, U or D. In case of a tie, choose the sequence of moves which is lexicographically first, where we consider F < B < L < R < U < D. All mazes will have solutions.

Sample Input

7 
XXXXXXX 
X     X 
X XXX X 
X     X 
X XXX X 
X XXX X 
XXXXXXX 
XXXXXXX 
X     X 
X X X X 
X X X X 
X X X X 
X X X X 
XXXXXXX 
XXXXXXX 
X     X 
X     X 
X     X 
X     X
X     X 
XXXXXXX 
XXXXXXX 
X     X 
X X X X 
X     X 
X X X X 
X     X 
XXXXXXX 
XXXXXXX 
X XXX X 
X XXX X 
X XXX X 
X XXX X 
X     X 
XXXXXXX 
XXXXXXX 
X     X 
X XXX X 
X XXX X 
X XXX X 
X     X 
XXXXXXX 
0

Sample Output

UULLLLUUBBBB

Honeycomb

Problem A

Bee Breeding

Input

bees.in

Professor B. Heif is conducting experiments with a species of South American bees that he found during an expedition to the Brazilian rain forest. The honey produced by these bees is of superior quality compared to the honey from European and North American honey bees. Unfortunately, the bees do not breed well in captivity. Professor Heif thinks the reason is that the placement of the different maggots (for workers, queens, etc.) within the honeycomb depends on environmental conditions, which are different in his laboratory and the rain forest.

As a first step to validate his theory, Professor Heif wants to quantify the difference in maggot placement. For this he measures the distance between the cells of the comb into which the maggots are placed. To this end, the professor has labeled the cells by marking an arbitrary cell as number 1, and then labeling the remaining cells in a clockwise fashion, as shown in the following figure.

      __    __    __    __       
     __\  /__\  /__\  /__\  /__    
 __/  \__/  \__/53\__/  \__/  \__
/  \__/  \__/52\__/54\__/  \__/  \
\__/  \__/51\__/31\__/55\__/  \__/
/  \__/50\__/30\__/32\__/56\__/  \
\__/49\__/29\__/15\__/33\__/57\__/
/  \__/28\__/14\__/16\__/34\__/  \
\__/48\__/13\__/ 5\__/17\__/58\__/
/..\__/27\__/ 4\__/ 6\__/35\__/  \
\__/47\__/12\__/ 1\__/18\__/59\__/
/..\__/26\__/ 3\__/ 7\__/36\__/  \
\__/46\__/11\__/ 2\__/19\__/60\__/
/..\__/25\__/10\__/ 8\__/37\__/  \
\__/45\__/24\__/ 9\__/20\__/61\__/
/..\__/44\__/23\__/21\__/38\__/  \
\__/70\__/43\__/22\__/39\__/62\__/
/  \__/69\__/42\__/40\__/63\__/  \
\__/  \__/68\__/41\__/64\__/  \__/
/  \__/  \__/67\__/65\__/  \__/  \
\__/  \__/  \__/66\__/  \__/  \__/
/__\  /__\  /__\  /__\  /__\   
/__\  /__\  /__\  /__\

For example, two maggots in cells 19 and 30 are 5 cells apart. One of the shortest paths connecting the two cells is via the cells 19 - 7 - 6 - 5 - 15 - 30, so you must move five times to adjacent cells to get from 19 to 30. Professor Heif needs your help to write a program that computes the distance, defined as the number of cells in a shortest path, between any pair of cells.

The input consists of several lines, each containing two integers D and E (D,E ≤ 10000), denoting numbers of cells. The integers are always positive, except in the last line where D=E=0 holds. This last line terminates the input and should not be processed.

For each pair of numbers (D,E) in the input file, output the distance between the cells labeled D and E. The distance is the minimum number of moves to get from D to E.

19 30 0 0

The distance between cells 19 and 30 is 5.

A Python Solution

# solution program for the honey-comb problem
# generated by Yang, Julia, Janet, and DT.
#


# the honeycomb array and its dimension
N = 20     
hc = []

# init the array to - 
for i in range( N ):
    hc.append( [] )
    for j in range( N ):
        hc[i].append( '-' )

# i, j define the coordinate of the c


def main():
    #--- coordinates of where we start labeling cells.  Start with 1
    i = N/2
    j = N/2
    num = 1
    hc[i][j] = num
    num += 1

    #--- the directions we need to move around the honeycomb to store
    #--- magots around the first cell 
    directions1 = ['S', 'NW', 'N', 'NE', 'SE', 'S' ]
    print "%3d:"% 1,  '-'.join( directions1 )
    i,j, num = fillArray( hc, i, j, directions1, num )

    #--- the directions we need to move around the honeycomb to store
    #--- the magots around the first generation       
    directions2 = ['S', 'W', 'NW', 'N', 'N', 'NE', 'E', 'SE','S', 'S' ]
    print "%3d:"% 1,  '-'.join( directions2 )
    i, j, num = fillArray( hc, i, j, directions2, num )

    #--- now go around for round 3, 4, 5, 6, 7 and 8 ---
    for row in  range( 3, 9 ):

        #--- compute the direction from directions2 ---
        newdirections = []
        for n, dir in enumerate( directions2 ):
            if n in [ 1, 3, 6, 8 ]:
                newdirections += [dir] * (row-1) 
            else:
                newdirections.append( dir )
        #print "%3d:"%row,  '-'.join( newdirections )

        #--- fill the array following the new directions found ---
        i, j, num = fillArray( hc, i, j, newdirections, num )

    #--- now that the array if filled, display it ---
    displayArray( hc )

    #--- ask user for 2 numbers and report the distance between them ---
    while True:
        line = raw_input( "Enter 2 integers: " )
        if len( line ) <= 1: return
        i1 = int( line.split( )[0] )
        i2 = int( line.split( )[1] )
        i1, j1 = search( hc, i1 )
        i2, j2 = search( hc, i2 )
        diag   = min( abs(i1-i2), abs(j1-j2) )
        straight = max( abs(i1-i2), abs(j1-j2) )-diag
        print "distance = ", diag + straight/2


# search( hc, n ) returns the coordinates of magot with number n in
# honeycomb hc.
def search( hc, n ):
    global N
    for i in range( N ):
        for j in range( N ):
            if hc[i][j]==n:
                return i, j
    return None, None

# fillArray( hc, i, j, directions, num )
# fills the array following the directions and moving the i, and
# j coordinates around.  num is the number we need to start numbering
# with.
def fillArray( hc, i, j, directions, num ):
    for dir in directions:
        if dir=='S': i += 2
        if dir=='N': i -= 2
        if dir=='W': j -= 2
        if dir=='E': j += 2
        if dir=='NW':
            j -=1
            i -=1
        if dir=='NE':
            j +=1
            i -=1
        if dir=='SE':
            j +=1
            i +=1
        if dir=='SW':
            j -=1
            i +=1
        hc[i][j] = num
        num += 1
    return j, i, num

# displayArray( hc )
# displays the 2D honeycomb.
def displayArray( hc ):
    global N
    for i in range( N ):
        for j in range( N ):
            print "%3s" % str( hc[i][j] ),
        print
    print
    

main()