Judging the Southeast Region

Here are the statements of the NAIPC 2014 Problems.

And, here is the data and judges’ reference solutions:

Here’s the judge data for the 2014 NAIPC. It’s password-protected.

data

Here it is – the 2013 Southeast USA Regional Division 1 problem set. You can download the text from here.

Note: For security reasons, the blog won’t upload files with a “.py” extension. The Python programs have extension “.txt”, which will need to be changed to “.py”

Here it is – the 2013 Southeast USA Regional Division 2 problem set. You can download the text from here.

Note: For security reasons, the blog won’t upload files with a “.py” extension. The Python programs have extension “.txt”, which will need to be changed to “.py”

Here it is – the 2013 UChicago Invitational problem set. You can download the text from here.

A Russian contest is going to use this problem set in about a week, so we can’t post the data to the public just yet. I’ll post the usual problem breakdown in about a week, but for now, here’s the problem set & data for the UChicago 2013 Invitational contest. The data is encrypted and password protected, so that only participants can see it.

Problem set: UChicago Invitational 2012 Problem Set

Data: data

Here it is – the 2012 Division II problem set. You can download the text from here.

Here it is – the 2012 Division I problem set. You can download the text from here.

Here it is – the problem set. You can download the text from here.

Here is a video of a webcast of the Chief Judge (me) discussing each of the problems in the 2011 problem set. The original lecture was given at Georgia Tech on Thursday, 11 November. The video is about 90 minutes long. The real content starts at about the 2 minute mark.

[flv:http://vanb.org/ser2011/vanb_ser2011_lecture.flv X 640 480]

In the problem statement for Vive la Difference, we make the claim that if all four numbers are less than 2^n, then it will converge in no more than 3n steps. This PowerPoint presentation outlines a proof.

Here it is – the 2011 problem set. You can download the text from here.

sundaydrive.java

Here’s the Call for Problems that was recently sent out to all SER coaches and Problem Selection Committee members:

Summer is upon us, World Finals is over, so it’s time to start thinking, just a little bit, about the Southeast USA Regional Programming Contest. It’ll be a little bit earlier this year, on Saturday, 29 October. So, spend your summer dreaming up programming problems! Also, we’re looking for people to serve on the Problem Selection Committee. Putting together the problem set for SER is an intense, rewarding process. If you’re interested, send me an e-mail (at vanb@biltmorecomm.com).

As usual, the Problem Selection Committee will be responsible for putting the problem set together. The PSC will also be responsible for judging, so problem providers won’t have to judge. Because of this, you can provide a problem, and also coach your team, and attend the contest with them at your chosen site. Anyone can submit a problem for consideration – however, although a problem submitter can also act as a coach, they cannot be a contestant, whether or not their problem is chosen for the set. In other words, if a student submits a problem, they are ineligible to compete.

Candidate problems should be e-mailed to me (at vanb@biltmorecomm.com). A statement of the problem is all that’s necessary, either in text or in MS Word format (right in the e-mail is fine). If you wish to include a solving program and/or test data, that’s very, very helpful, but not necessary. If you have a rough idea and want to talk about it, feel free to e-mail it to me, and I’ll be happy to work with you.

Problems should be sent by Friday, 9 September to be eligible for consideration. That’s the Friday after Labor Day. I’ll remind you again, but I’m sending out the call for problems early, to get you thinking!

Below you will find an excerpt from the Call for Problems issued from World Finals this year. It’s a good set of guidelines for candidate problems. If you are thinking of submitting a candidate problem for Southeast Regionals, you should read through it. I will add a couple of constraints of my own:

1. The problem should be original. It should not be a restatement of a problem that has been used previously in the Southeast USA, or any other ICPC regional, World Finals, or other contest environment such as TopCoder or Google CodeJam. It also should not come from a book, such as “Programming Challenges.” If it has its own Wikipedia page, then it’s too well-known.
2. The output for any given input should be unique. Try to add constraints to your problem so that there is exactly one answer for each input case.

Don’t forget about the blog to talk about judging at our contest. It’s at:

http://serjudging.vanb.org

Feel free to drop by and give suggestions – however, do NOT post candidate problems on this site. It is open to everyone, including students. Any problem posted on the site cannot be used in the contest.

————- Some excerpts from the World Finals call for problems: ————-

Problem Statements

1. Each problem must be unambiguously described in English.
2. All problems must require input.
3. Unless the core of the problem is input/output related, the formats chosen for input data and the displayed results should be relatively simple. Still, the format of the input data and the appearance of the expected displayed results must be described in suitable detail.
4. Multiple data sets testing different cases are appropriate; make the problem statement include iterative data sets as input to avoid using separate input files.
5. Anticipate questions about special cases. Where appropriate, explicitly state that certain special cases will not appear in the input data. It is not necessary to specifically identify the special cases that will appear.
6. Indicate the precision that is required for real results.
7. Contestants must write solutions for problems in a short time. While very simple problems are not appropriate, neither are problems that require a great deal of code; a few hundred lines of Java or C should be an upper limit on what can be expected in a solution.
8. The program and chosen test data should not require excessive execution time. Contestants’ solutions may be less efficient than yours and so a generous margin is allowed for execution. If your test data requires the program to execute for a long time, then incorrect student solutions (e.g., those with infinite loops) will take an excessively long time to judge. We would like to avoid those situations.
9. The problem description (excluding sample input/output) should generally require at most one page.

Submission of Problems, Solutions, and Test Data

1. Use electronic mail and send all files as either MS Word document, or flat ASCII.
2. Do not put your name in documents, or the body of e-mails, containing the problem statement, solution, or test data. This will simplify the transformation from your form to the one used for ranking.
3. Be discreet about problem statements and solutions. It is not appropriate to discuss problems with people not involved with the contest.

Here it is – the 2010 problem set. You can download the text from here.

The Southeast USA Regional Programming Contest will be held on Saturday 6 November this year, and I will once again be Chief Judge.

As usual, the Problem Selection Committee will be responsible for putting the problem set together. The PSC will also be responsible for judging, so problem providers won’t have to judge. Because of this, you can provide a problem, and also coach your team, and attend the contest with them at your chosen site. Anyone can submit a problem for consideration – however, although a problem submitter can also act as a coach, they cannot be a contestant, whether or not their problem is chosen for the set. In other words, if a student submits a problem, they are ineligible to compete.

Candidate problems should be e-mailed to me (at vanb@vanb.org). A statement of the problem is all that’s necessary, either in text or in MS Word format (right in the e-mail is fine). If you wish to include a solving program and/or test data, that’s very, very helpful, but not necessary. If you have a rough idea and want to talk about it, feel free to e-mail it to me, and I’ll be happy to work with you.

Problems should be sent by 13 September to be eligible for consideration. I’ll remind you again, but I’m sending out the call for problems early, to get you thinking!

Below you will find an excerpt from the Call for Problems issued from World Finals this year. It’s a good set of guidelines for candidate problems. If you are thinking of submitting a candidate problem for Southeast Regionals, you should read through it. I will add a couple of constraints of my own:

1. The problem should be original. It should not be a restatement of a problem that has been used previously in the Southeast USA, or any other ICPC regional, World Finals, or other contest environment such as TopCoder or Google CodeJam. It also should not come from a book, such as “Programming Challenges.” If it has its own Wikipedia page, then it’s too well-known.
2. The output for any given input should be unique. Try to add constraints to your problem so that there is exactly one answer for each input case.

Based on suggestions from last year’s regional contest, I have started a blog to talk about judging at our contest. It’s at:

http://serjudging.vanb.org

Feel free to drop by and give suggestions – however, do NOT post candidate problems on this site. It is open to everyone, including students. Any problem posted on the site cannot be used in the contest.

————- Some excerpts from the World Finals call for problems: ————-

Problem Statements

1. Each problem must be unambiguously described in English.
2. All problems must require input.
3. Unless the core of the problem is input/output related, the formats chosen for input data and the displayed results should be relatively simple. Still, the format of the input data and the appearance of the expected displayed results must be described in suitable detail.
4. Multiple data sets testing different cases are appropriate; make the problem statement include iterative data sets as input to avoid using separate input files.
5. Anticipate questions about special cases. Where appropriate, explicitly state that certain special cases will not appear in the input data. It is not necessary to specifically identify the special cases that will appear.
6. Indicate the precision that is required for real results.
7. Contestants must write solutions for problems in a short time. While very simple problems are not appropriate, neither are problems that require a great deal of code; a few hundred lines of Java or C should be an upper
   limit on what can be expected in a solution.
8. The program and chosen test data should not require excessive execution time. Contestants’ solutions may be less efficient than yours and so a generous margin is allowed for execution. If your test data requires the program to execute for a long time, then incorrect student solutions (e.g., those with infinite loops) will take an excessively long time to judge. We would like to avoid those situations.
9. The problem description (excluding sample input/output) should generally require at most one page.

Submission of Problems, Solutions, and Test Data

1. Use electronic mail and send all files as either MS Word documents, or flat ASCII.
2. Do not put your name in documents, or the body of e-mails, containing the problem statement, solution, or test data. This will simplify the transformation from your form to the one used for ranking.
3. Be discreet about problem statements and solutions. It is not appropriate to discuss problems with people not involved with the contest.

We considered this problem an E/F, World-Finals level of difficulty. There were 3 correct solutions – on only 7 submissions, and the first came only 65 minutes into the contest. It had the highest solution percentage of any problem outside of the two A/Bs (Knitting and Minesweeper). That means that few teams knew how to solve it, and few tried, but those who knew it, knew it well, and got it quickly and accurately.

Take a look at the Judge Input, the Judge Output, the main Solving Program, and another java solution.

A solution is in the spoiler.

[spoiler]
The key to understanding this solution is to see a column of the mosaic as a bitmap – with the bit set (=1) if there’s a tile there, and unset (=0) if not. Since there are at most 10 rows, that gives us 1024 possible bitmaps, which is manageable.

Try to build a Mosaic, column by column. Since the pieces are 2×2, you can’t fill a column without leaving some residue in the next column. So, you need to figure out, for any bitmap j representing a residue from the last column, how many ways can we fill this column and leave a residue of bitmap k in the next column? The following picture illustrates one way of filling 1001101001 (617) and ending up with 1111011110 (990).

Here’s an interesting thing – that depends only on the number of rows. So, you can compute all of that a priori, before you start reading the data, rather than doing it over and over for each data set. A recursive algorithm will do the trick.

Once you’ve got that computed, then for each input, you need to fill the columns so that you start with a bitmap of 0 (on the edge, no residue), go through m columns, and end up with a bitmap of 0 (no residue – nothing hanging off the edge of the mosaic)

     
// Assume n rows and m columns.
// Let p be the number of bitmaps if there are n rows.
// So, p = 2^n, or 1<<n
int p = 1<<n;
       
// Let next[k] be the number of ways of achieving bitmap k
// on the next column
int next[] = new int[p];

// We'll start at the very beginning (a very good place to start)
// with one bitmap of 0, and no others.
next[0] = 1;

// Go through all of the columns
for( int i=0; i<m; i++ )
{
    // Swap current and next - last iterations' next[]
    // is this iteration's current[]
    int temp[] = current;
    current = next;
    next = temp;
            	
    // Start afresh
    Arrays.fill( next, 0 );
            	
    // Go through all possible bitmaps.
    for( int j=0; j<p; j++ ) if( current[j]>0 ) for( int k=0; k<p; k++  )
    {
        // Assume that ways[n][j][k] is the number of ways of getting from 
        // bitmap j to bitmap k if there are n rows. (In the actual code, a linked list 
        // is used for efficiency, since this matrix will be sparse.)
        //
        // If there are current[j] ways of getting to bitmap j on the current column,
        // and ways[n][j][k] ways of getting from there to bitmap k, then we've
        // just found current[j]*ways[n][j][k] more ways of getting to bitmap k
        // on the next column. So, add them in.
        next[k] += current[j] * ways[n][j][k];

        // Mod to keep the numbers manageable.
        next[k] %= 1000000;
    }
}

// We're done! How many ways were there of achieving bitmap 0
// on the last iteration - that is, we nicely filled in the mosaic with
// nothing hanging over?
System.out.println( next[0] );

[/spoiler]

We had wanted this problem to be a Dynamic Programming problem, and early versions of it had large input limits that would force DP. However, other constraints caused us to put limits on it, making it solvable by other means. It was in our “second wave” of problems. The “first wave” was Knitting and Minesweeper – every team that solved one or two problems solved one (or both) of those two. This problem and “Euclid” made up the second wave – every team that solved 3 or 4 solved both problems in the first wave, and then one or two from the second wave. Every team that solved more than 4 solved both problems in the first wave, and both problems in the second wave.

OK, here’s the Judge Input, the Judge Output, the main Solving Program, another java solution, one in C++, another in C++, and one using a different technique.

Look in the spoiler for not one, but two solution ideas!

[spoiler]
The original intent was for this problem to require Dynamic Programming. Create an array best[], where best[i] is the best you can do from here to the end if you stop at target point i. Clearly, best[i] can be computed pretty simply from best[i+1], best[i+2], and so on (best[i] = Minimum over k of [1+(the cost of skipping targets between i and i+k) + (the Euclidean distance between i and i+k) + best[i+k]]. ). So, start at the end, work back to the beginning, and best[0] is your answer.

The numbers were small enough, however, that a simple, best-first-search shortest path (aka Dijkstra’s Algorithm) would work. Define the “Distance” between two targets as 1 + (the Euclidean distance) + (the cost of skipping targets in between). Then, just run Dijkstra’s Algorithm and voila.

Note: in both cases, the “1+” is for the one second that the robot must stop on a target point.
[/spoiler]

Pool Table was one of our tougher, E/F problems. There were two parts to the problem – figuring out that distance, and making sure you didn’t hit the target ball too soon.

Here’s the Judge Input, the Judge Output, the main Solving Program, another java solution, and one in C++.

Take a look in the Spoiler for solution ideas.

[spoiler]
For the first part, finding the distance, it’s easier to not try to compute reflections, but rather to set up a coordinate system of reflected pool tables. Let dx and dy be a number of pool tables over, and up. If n is the desired number of bounces, then look at all reflections where |dx|+|dy|=n.

For example, if n=2 bounces, instead of this:

See it as this:

Then, look at all reflections where |dx|+|dy|=n (for our example of n=2, they’re the lightest colored ones in the example above), and just calculate the straight linear distance between the cue ball and the reflection of the target ball. Be careful about the position of the target ball in the reflection!

Then, the second part of the problem is to make sure that there are no reflections of the target ball that get in the way – that is, no chance of hitting the target ball too soon. You’ve got to check that no reflection of the target ball (including the original!) is collinear with the cue ball and the reflection you’re trying to hit AND between them.

Here’s a case that caught a few teams: consider a large table, with the cue at (1,1) and the target at (2,2), with n=2 bounces. The correct answer is to shoot at the corner at (0,0), and have the cue bounce straight back to the target. Several teams failed this particular test. It’s because, in checking to see if an earlier version of the target blocked the shot, they only checked collinearity, not betweenness. Here, the original target ball is collinear with the cue and the reflected target, but it is not between them!
[/spoiler]

This problem turned out to be harder than we expected. We rated it a C/D, yet only 2 teams managed to solve it, the first coming about three and a half hours into the contest. It’s really not a difficult algorithm, but it’s off the beaten path, and requires some thinking and some care.

Check out the Judge Input, the Judge Output, the main Solving Program, another java solution, and one in C++.

Look in the spoiler for a description of a solution.
[spoiler]
Use a Greedy algorithm. First, assume that the trees are laid out right next to each other, as tightly as possible. Then, find the positions of the smallest and largest trees – let’s say s and t – and then try to stretch the gap between s and s+1 as far as possible, then the gap between s+1 and s+2, then s+2 and s+3, all the way up to t-1 and t. Look at all pairs of trees that are adjacent height-wise (that the Ninjas would jump between) that span each of those gaps, to see how far the gaps can be stretched.

The only way the Greedy algorithm can fail is if stretching an early gap limits your options of stretching a later gap. I’m not going to go through a convoluted argument, but it’s true. It’s left as an exercise to the reader to confirm!
[/spoiler]

It’s just Minesweeper. Everyone knows Minesweeper. This problem was solved by more teams than any other.

Check out the Judge Input, the Judge Output, the main Solving Program, another solution, and another. There are also C++ solutions here and here.

[spoiler]
The algorithm is obvious – just do what the problem says. For every non-mine cell, look at the (up to) 8 cells around, and count the number of mines. So, the key to solving this problem is just to be careful about certain things.

• Don’t go off the edge of the board when you’re checking edge cells and corner cells
• For some, correctly convert an integer to a char (others just printed the int directly). In both C++ and Java, this will work: ch = (char)(x+’0′)
• Make sure your output spacing is correct.

[/spoiler]