CS 198/CS 98 Spring 2008 "Programming for Blood"

Problem Sets

General Directions for Problem Sets

To set up your account, execute

    source ~ctest/bin/setup
in all shells that you are using. (This is for those of you using csh-like shells. Those using {\tt bash} should instead type
    source ~ctest/bin/setup.bash
Others will have to examine this file and do the equivalent for their shells.)

New Feature: I am beta-releasing a new web interface for submitting problems and seeing your results. Try it (you can still use "submit" as usual if it doesn't work). Warning: so far, this does not pretest your submission.

Put each complete C solution into a file N.c, each complete C++ solution into a file N.cc, each complete Java program into a file N.java, and each complete Python program into a file N.py, where N is the number of the problem. Each program must reside entirely in a single file. In Java, the class containing the main program for problem N must be named PN (yes, it is OK to have a Java source file whose base name consists of a number, even though it doesn't match the name of the class). Do not make class PN public, or the Java compiler will complain. Each C/C++ file should start with the line

    #include "contest.h"
and must contain no other #include directives, except as indicated below. Upon completion, each program must terminate by calling exit(0) (or System.exit(0) in Java).

When you have a solution to problem number N that you wish to submit, use the command

   submit N
from the directory containing the source program. Before actually submitting your program, submit will first compile it and run it on one sample input file.

All tests (for any language) will use the compilation command

    contest-gcc N
followed by one or more execution tests of the form (Bourne shell):
    ./N <  TEST-INPUT-FILE > TEST-OUTPUT-FILE 2> JUNK-FILE
which sends normal output to TEST-OUTPUT-FILE and error output to JUNK-FILE. The output from running each input file is then compared with a standard output file, or tested by a program in cases where the output is not unique. In this comparison, leading and trailing blanks are ignored and sequences of blanks are compressed to single blanks. Otherwise, the comparison is literal; be sure to follow the output formats exactly. It will do no good to argue about how trivially your program's output differs from what is expected; you'd be arguing with a program. Make sure that the last line of output ends with a newline. Your program must not send any output to stderr; that is, the temporary file JUNK-FILE must be empty at the end of execution. Each test is subject to a time limit of about 45~seconds. You will be advised by mail whether your submissions pass.

In the actual ACM contests, you will not be given nearly as much information about errors in your submissions as you receive here. Indeed, it may occur to you to simply take the results you get back from our automated judge and rewrite your program to print them out verbatim when your program receives the corresponding input. Don't do that.

All input will be placed in the standard input. You may assume that the input conforms to any restrictions in the problem statement; you need not check the input for correctness. Consequently, you C/C++ programmers are free to use scanf to read in numbers and strings and gets to read in lines.

Terminology. The terms free format and free-format input indicate that input numbers, words, or tokens are separated from each other by arbitrary whitespace characters. By standard C/UNIX convention, a whitespace character is a space, tab, return, newline, formfeed, or vertical tab character. A word or token, accordingly, is a sequence of non-whitespace characters delimited on each side by either whitespace or the beginning or end of the input file.

Scoring. Scoring will be according to the ACM Contest Rules. You will be ranked by the number of problems solved. Where two or more contestants complete the same number of problems, they will be ranked by the total time required for the problems solved. The total time is defined as the sum of the time consumed for each of the problems solved. The time consumed on a problem is the time elapsed between the start of the contest and successful submission, plus 20 minutes for each unsuccessful submission, and minus the time spent judging your entries. Unsuccessful submissions of problems that are not solved do not count. As a matter of strategy, you can derive from these rules that it is best to work on the problems in order of increasing expected completion time.