Resources

To help you prepare (that means: see if you can figure out how the judges think), here are some actual problems from prior years of the Southern California Region's contest sets:

The Southern California Region policy regarding contest problems is that we do not publish the judges' data, nor do we publish a "solution set." For further reference, additional problem sets can be found at the ICPC "Preparing for the Competition" site and at various sites on the web using your favorite search engines.


Program Structure

A program is a Before the advent of GUIs, the time-honored structure of a program was
     while not end-of-file
       read some lines of input
       process the data
       if appropriate, print line(s) of output
     end
Because GUIs react principally to human interaction rather than input data, their structure is roughly
     initialize GUI
     do forever
       e=wait_for_event()
       process_event(e)
     end

The vast majority of problems in this region fall squarely within the 'while not end-of-file' category.

Single Language

A submission for judging is a single program, written in a single programming language.

Monolithic

A submission for judging is a single file that contains all classes, functions, definitions, etc. for the program. C, C++, and Java permit the specification of an entire program, even supporting code, as a single monolithic file. The Southern California Region requires a monolithic file so that we can track submissions by a single file.

C and C++ programmers form monolithic files often, but Java is usually taught as a one-file-per-class language. To make a monolithic source file in Java, one must avoid declaring classes as public. Furthermore, the Southern California Region requires that the class containing the main() method be called aout.

Source File

A source file is a text file that contains compilable code. You may use a text editor or integrated development environment (IDE) such as Eclipse to develop your code. Note that Eclipse wants to follow the Java one-file-per-class model and tries to make classes public. You should remove the reserved word "public" from each Java class declaration.

A Monolithic, Multiclass Java Source File

This is slightly contrived, but otherwise illustrative.

import java.io.*;

class Point {                          // note that the class is NOT public
   private double x;
   private double y;

   public Point(double x, double y) {  // however, the constructor method needs to be public
      this.x=x;
      this.y=y;
   }

   private double square(double x) {   // methods internal to a class may be private or protected
      return x*x;
   }

   public double GeometricMean() {     // this is a public method for use by instances of Point
      return Math.sqrt(square(x) + square(y));
   }
}

// aout is NOT public and contains the main() method

class aout {

   // standard declaration for the main() method

   public static void main (String [] args) throws IOException
   {
      Point          p;
      String         s;
      BufferedReader stdin;
      String []      token;
      double         x;
      double         y;

      stdin=new BufferedReader(new InputStreamReader(System.in));
      while ( (s=stdin.readLine()) != null) {
         token=s.split(" ");
         x=Double.parseDouble(token[0]);
         y=Double.parseDouble(token[1]);
         p=new Point(x,y);
         System.out.println("(" + x + "," + y + "), geometric mean=" + p.GeometricMean());
      }
      System.exit(0);
   }
}

Data Input and Output in the Southern California Region

In general, test input to programs is

Similarly, output expected from a program is generally

To prepare contestants for competition in the Southern California Region, we offer the following discussion and examples.

Line-oriented Text

During the 2007 and 2008 regional contests, the judges encountered contestants' questions and problem submissions indicating an incomplete understanding regarding what constitues a line of text. A line of text on a Unix-like host is

Producing the ASCII 0x0A (line feed) for output depends upon the programming language. See the solutions below for examples.

Standard Input and Standard Output

Decades ago, computer programs never directly interacted with humans. A human would load a stack of punch cards or paper tape containing the program and data for processing. The computer would then be started, and it would not stop working until the program finished or aborted with an error. There were no such things as file names—or operating systems, for that matter. The program didn't even have to open a file to read its data; it was assumed that programs took input, processed the input, then spewed output. This concept of unnamed input and output, ready for reading and writing, evolved into standard input and standard output.

Standard input is Standard output is

Reading from standard input and writing to standard output differ according to the programming language. See the solutions below for examples.

Unnamed standard input and standard output also make repeated program executions against different files possible without having to recompile the program or rename files. The judges make extensive use of this by producing multiple files with differing test cases.

Unix, DOS, Windows, and some other operating systems have added a powerful abstraction that can be used with programs that read from standard input and write to standard output. This abstraction views a program like an electric circuit, with standard input seen as an incoming signal and standard output as an output signal. Circuits can be cascaded, feeding the output signal of one circuit to the input signal of another—without needing to record any of the signals. Similarly, the output of one program can be fed to the input of another program without having to save intermediate files; this is commonly known as piping. Originally, this allowed complex sequential processing to consume small amounts of disk space. With symmetric multiprocessing, each program can potentially execute in a separate CPU, permitting pipeline parallel processing.

End-of-file

End-of-file is a testable condition. In this region, contestants are expected to know how to read a file until end-of-file, without attempting to read beyond end-of-file.


A Solved Programming Contest Problem, Exemplifying Data Input and Output

We offer an explanation in the form of examples. Below is the warmup problem from the 2002/2003 Southern California Regional contest. We solve it five times: in Python 3, C, C++ using a seed read, Java, and again in C using a seed read. The "seed read" technique is used in languages that cannot perform assignments within condition tests nor perform look-ahead input. The seed read technique often shows up in shell scripting languages.

Unary Numbers

What could be simpler than binary numbers? Unary numbers! A Unary number, n > 0, is coded as n-1 one bits followed by a zero bit. Thus the code for 5 is 11110. Here are some unary numbers.

Decimal Unary
1 0
2 10
3 110
4 1110
5 11110
6 111110
7 1111110

Input consists of decimal numbers, one per line, with no leading or trailing whitespace. Each number will be in the range 1–76. Input is terminated by end-of-file.

For each number, produce a single line of output consisting of the input decimal number, with no leading zeros or spaces, a single space, and the unary equivalent with no leading or trailing spaces.

Sample Input
76
37
5
28
14
8
1
Output for the Sample Input
76 1111111111111111111111111111111111111111111111111111111111111111111111111110
37 1111111111111111111111111111111111110
5 11110
28 1111111111111111111111111110
14 11111111111110
8 11111110
1 0

Python 3 Solution

For 2017, Southern California Regional support for Python solutions is considered fully supported. Regional judges will accept solutions coded in Python 3. Full support boils down to external library support and interpreter performance. Specifically,

(1) Python 3 supported at the Southern California regional contest will be the standard release of version 3.7.2 available from python.org. NO additional packages will be available in the judges' execution environment.

(2) The execution time limits set for each problem will NOT be scaled based upon the language. It is the contestants' responsibility to select the appropriate tool (language and algorithm) to produce correct output within the allotted time limits.

Standard input is identified by the class, sys.stdin. The print( ) function writes to standard output.

import sys

for line in sys.stdin:
    line=line.replace('\n','')  # remove end-of-line present in strings read from input
    n=int(line)
    print(n, end=' ')           # print number in decimal followed by one space
    for i in range(n - 1):
        print('1', end='')      # print '1' without any trailing characters
    print('0')                  # print '0' followed by newline

exit(0)                         # indicate normal program termination

C Solution

Standard input is identified by the stream variable, stdin. Standard output is identified by the stream variable, stdout.

#include <stdio.h>

int main()
{
   int  i;
   int  n;
   char s[4];  /* room for two decimal digits, newline, and a zero-byte to terminate the string */

   /* fgets() returns NULL at end-of-file */

   while(fgets(s,sizeof(s),stdin) != NULL) {  /* read an entire line into s */
      sscanf(s,"%d",&n);                  /* extract n from the input line */
      fprintf(stdout,"%d ",n);
      for (i=n - 1; i > 0; i--) {
         fputc('1',stdout);
      }
      fputs("0\n",stdout);                    /* the newline character, \n, emits an ASCII 0x0A */
   }
   return 0;                                  /* indicate normal program termination */
}

C++ Solution

#include <iostream>
using namespace std;

int main ()
{
   int n;

   cin >> n;            // seed read
   while(!cin.eof()) {  // eof() valid only after attempted read
      cout << n;
      cout << ' ';
      while (n > 1) {
         cout << '1';
         n--;
      }
      cout << "0\n";    // the newline character, \n, emits ASCII 0x0A
      cin >> n;
   }
   return 0;            // indicate normal program termination
}

Java Solution

Making use of standard output in Java is easy: simply use the methods in System.out. Performing meaningful line-oriented input from standard input requires wrapping a couple of classes around System.in.

Within the Southern California Region's judging environment, class defintions may not be public. Furthermore, the class containing method main() must be named aout. As a final quirk, the file containing class aout must NOT be named aout.java.

import java.io.*;

class aout {
   public static void main (String [] args) throws IOException
   {
      int            n;
      String         s;
      BufferedReader stdin;

      // wrap BufferedReader around InputStreamReader around System.in

      stdin=new BufferedReader(new InputStreamReader(System.in));

      // BufferedReader.readLine returns null at end-of-file

      while ( (s=stdin.readLine()) != null) {
         n=Integer.parseInt(s);
         System.out.print(n + " ");
         for (int i=n - 1; i > 0; i--) {
            System.out.print("1");
         }
         System.out.println("0");              // println() writes an ASCII 0x0A
      }
      System.exit(0);                          // indicate normal program termination
   }
}

C Solution using a Seed Read

Standard input is identified by the stream variable, stdin. Standard output is identified by the stream variable, stdout.

#include <stdio.h>

int main()
{
   int  i;
   int  n;
   char s[4];  /* room for two decimal digits, newline, and a zero-byte to terminate the string */

/*
 * Attempt to read an entire line into s.  The fgets() preceding the while loop is the seed read.
 */
   fgets(s,sizeof(s),stdin);                  /* attempt to read an entire line into s */
   while( !feof(stdin) ) {                    /* while not end-of-file ... */
      sscanf(s,"%d",&n);                      /* extract n from the input line */
      fprintf(stdout,"%d ",n);
      for (i=n - 1; i > 0; i--) {
         fputc('1',stdout);
      }
      fputs("0\n",stdout);                    /* the newline character, \n, emits an ASCII 0x0A */
      fgets(s,sizeof(s),stdin);               /* attempt to read an entire line into s */
   }
   return 0;                                  /* indicate normal program termination */
}

Books

Programming Challenges, Steven S. Skiena and Miguel Revilla, 2003. This book is targeted at contestants in programming competitions and can be used for practice with the web-accessible automated judging system maintained by one of the authors.

Articles

  1. "Teamwork in Programming Contests: 3 * 1 = 4," ACM Crossroads