Basic strategy and preparation

ACM Programming Team

Introduction

There is a lot of information below.  If you have not yet done your first practice, it may be a complete overload.  Do not worry.  Actually doing things in practice will reinforce the basic setup.  On the other hand, going into the first pratice totally clueless will mean you might spend a lot of time on the administrative setup that could be spent on problems and teamwork.  Take what you can the first time from the information below, and return to compare notes with what you did after practices.

Competition/practice overview

In the contest (and practices!), you get to bring any book/paper references you like.  I was really impressed by the student that brought his favorite book with physical tabs added to locate the most important parts.  Your team of three people is presented with one computer and 6-8 problems on paper.  Each problem generally has 1-2 page specifications, showing sample input and output data, and requiring 10-120 line of code beyond the standard I/O setup (if you are concise – which is not exactly necessary).  Some are very easy, and a good team will bang out such a problem first in 10-20 minutes.  Others take much longer, figuring out an appropriate algorithm, and covering and coding all the special cases.  Problems are non-interactive and follow the simple pattern:  read data from the input file, process data, output data to standard output (new in 2006).  Input data will always have a count at the beginning or a sentinel at the end, making it easy to construct a main loop without worrying about end-of-file conditions.

In all problems exact input and output formats are specified.  The judge’s input data is generally much more thorough than the sample input data you are given.  Your program is run with the secret judge’s input data.  It should produce the exact right output to the screen, or your submission is wrong.  Little information is given back to you if you make an error – one of 5 categories is checked off.  Unfortunately this complicates finding and correcting bugs for another submission.  File naming conventions must be followed exactly.  there is a base name for a given problem, say “juggler” for instance.  Then the input file must be “juggler.in”.  Debugging info needs to go  to the standard error stream, not standard output.  The source file name is “juggler” with the appropriate language extension (juggler.cpp, juggler.java).  The base name is generally all lowercase.  If you write in Java, this makes you break the usual Java class naming convention:  the source file name and main class name are all lower case.

The scoring is based first on the number of problems eventually submitted totally correct.  In some competitions, some teams get all the problems (from 100 or so total teams among all local sites).  In some competitions no one team gets all the problems.  Among teams solving the same number of problems, time and incorrect submission penalties determine who is ahead.  For each problem, time is measured from the beginning of the competition to the time of correct submission.  Each incorrect submission for a problem that is ultimately submitted correctly adds a 20 minute penalty to your correct submission time.  Problems that never get a correct submission, no matter how many incorrect submissions, are ignored in scoring.  Note that time is measured on each problem from the beginning of the competition, not the time of the last correct solution.  This means that it is strategic to do the simplest problems first.  Fifteen minutes for one problem solution, followed by 50 more minutes for a second solution would give you 15 + (15+50) = 80 minutes for the two problems. Fifty minutes solving the first problem, followed by 15 more minutes for the second problem would give you 50 + (50+15) = 115 minutes for the two problems – much worse.  If the 15 minute problem was submitted correctly the first time, and the 50 minute problem had two incorrect submissions before the correct submission, the total minutes recorded would be 2*20 = 40 minute more, (120 or 155).

Because of the two very different attributes of scoring, there are different strategies.  Different team members may have different skills, encouraging splitting the problems up and basically working alone.  Pn problems where one team member has a clear idea or is the only one clued in, working alone saves the time of coordinating, and possibly leads to having time to solve an extra problem, which is the most important thing in scoring.  The secondary scoring critieria, time until solutions, encourages working together.  As a simplicication, ignore the time to type into the computer:  If three problems each take 30 minutes for one individual, but can be modularized into three 10 minute portions for each team member, then working together, problems can be submitted after 10, 20, and 30 minutes for a score of 60, but if everyone works separately (and then types instantly) the times would be 30, 30, and 30, for a score of 90.  The overhead of time to communicate plans detracts from the cooperative solving approach.

The most important thing that encourages working together is running out of time.  It is a common point of frustration to have 2-3 problems 90% complete at the end, and then they all count for nothing.  If several are working on problems that require some thinking time and they do not have time to finish, then switch approach:  Agree on one of them that can be split in pieces among several people thinking about distinct pieces, or brainstorming together, and get it done in time!

You get to submit written questions to the judges if anything seems ambiguous to you, and you get a written response back.  Sometimes the questions and answers from other teams are posted for all to see. 

For input in Java use java.util.Scanner. Note that the file names specified are generally in lower case.  For a java source file, that means the main class name needs to be the same lowercase name.  For sample problems with statements see the sample problems.  Note the solutions to Addition for a simple illustration of the basic I/O and naming format.

Favorite topics/algorithms for problems:

Be sure to read the excellent, extensive description of language and algorithmic skills desired is at the Mid-Central site http://mcpc.cigas.net/contestants.html.


Recommended Text:

Programming Challenges, The Programming Contest Training Manual, by Skiena and Revilla, Springer.

This is a fair algorithms book in general and great for contest prep in particular.

Materials and preparation:

Have all your favorite references handy – book, notes, handouts.  You might have some of the most useful stuff xeroxed and organized so you can find it without digging through a bunch of books.  For the basic algorithms, maybe have sample code.  Have the basic file IO code written down.

Know how the basic libraries in your language work for containers (lists, sets, Hashtables), strings, sorting (classes Arrays and Collections in Java), formatting

Basic timing strategy hints

Code standards

It is useful to follow good programming practice in using names for most constants, particularly maximum sizes:  In may be inconvenient to design data or see what is happening in the debugger with a 20x20 array, but you may be able to test the same logic and generate data much easier if you use a 3x3 array size as the maximum.
The paragraph above has standard programming style hints, but not everything you learned in OOP applies here!  Generally have a global (or Java static) set of variables for the data read in.  For these 30-80 line programs, objects rarely help (except sometimes as records to avoid parallel arrays).  Procedural programming using the global data that you input is usually the fastest and most efficient route.

On most problems execution time is NOT an issue – go for an algorithm that is simple to write and understand, even if it means thousands of extra calculations.  (DO watch out for BILLIONS of extra calculations.)  Generally maximum sizes are given, so everything can be done with fixed sized arrays, though you can use the collection API’s in Java and C++ to advantage -- learn them.

All I/O will be from a single specified input file to standard output.  You are free to send any debugging information you want to stderr (or System.err).  Make sure debugging changes (other than extra data to the error stream) come out of your code before the final version.  Check EXACT names before turning in your solution.  Reread the problem one more time – did you miss something?  

There are lots of problems on the web, but their formats generally vary from our region's problems:  The answer may not be unique.  You may need to worry able end-of-line and end-of-file.  You may use stdin and stdout for I/O.  The problems may be harder or easier.

With online grading, allowing Java and C++:
   http://acmicpc-live-archive.uva.es/nuevoportal/

Do NOT look at the MidCentral region's problems -- we use those for regular practices:
      
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  

Java and C++ I/O sketetons


// basic java skeleton with file IO 
import java.io.*;

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

  public static void main(String[] args) throws Exception {
    //  standard I/O setup follows
    String file = "filebase.in";  // change filebase for each problem
    if (args.length > 0)
        file = args[0]; // optional lines for debugging with different files
    Scanner in = new Scanner(new File(file)); 
    // read all data sets from in and write System.out 
 // ??? = in.nextInt();

//  System.out.println("???");

  } 
}

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

// basic C++ skeleton with file IO for file filebase.cpp
// replace filebase with the appropriate string for the problem

#include <iostream> 
#include <fstream> 
#include <stdlib.h> 
using namespace std;

// data typically into global variables here

int main () { 
  ifstream in("filebase.in"); 
  if (!in) { 
   cerr << "Can't open filebase.in" << endl; exit(2); 
  } 
  // read all input from in, write to cout 
  // in >> ... 
  // cout << ...

  return 0; 
}