Strategies and mechanics for writing competitive programs

Competition programming is difficult!

You would be surprised to find out how many teams of smart students never solve a single problem correctly in a competition. At SRU, we go out of our way to give a problem that anyone should be able to solve, yet many teams don't solve even that problem.

Know the basics before you come to the competition!

You wouldn't go to play a serious baseball game if you didn't know how to catch and hit. Here are some basics you must be able to do to compete in a programming competition:

Know how to read from standard input and write to standard output. This means knowing the usual statements for reading from the keyboard and writing to the monitor in a command-line or console environment. See the table below for examples.

Programming Language	Statement for Reading from Standard Input	Statement for Writing to Standard Output
BASIC	INPUT	PRINT
C	scanf(), getchar(), getline(), etc.	printf(), putchar(), puts(), etc.
C++	cin	cout
FORTRAN	read *, read(5,...	print *, write(6,...
Java	*	*
Pascal	Read(), ReadLn()	Write(), WriteLn()
Python	input(), raw_input()	print

*It's trickier for Java. Here are two approaches from Mr. David Kosbie, who coaches Sewickley Academy's teams, that can do the trick.

Know I/O redirection (explained below). Do not open files for reading or writing in a competition program, at least not in SRU's competitions.
Know how to detect the end-of-file in your programming language. Some problems tell you how many data lines there are. Many don't. Make sure you know how to read all data lines, even when you don't know how many to expect.
Cheat. It's legal. Research the standard math formulas, and bring copies of them with you. Solve problems from older competitions. Bring the listings with you. Find a programming text that you are comfortable with, and bring it with you. These things may be cheating in a programming course, but they are techniques used by programming professionals and they are encouraged at programming competitions.

Input/Output Redirection

I/O redirection is a feature of the Unix, MS-DOS, and Windows Command Prompt environments that makes it possible to set the name of the input file and/or output file of a program in the command that runs the program. Programmers do not have to code a filename, or a prompt for a filename, into programs. This is also important for judges: programs can be tested with files with different names than those with which the contestants test their programs.

Filters

To allow for redirection, write your program as a filter. A filter is a program that reads only from standard input (if the program uses input) and writes only to standard output. In most programming languages, this means to read from the keyboard (not from a file or a GUI object), and write to the screen (not to a file or a GUI object). If you are using a Windows integrated development environment, such as Borland C++, C++ Builder, or Visual C++, set it to generate a console application.

I/O Redirection Symbols

Symbol	Purpose
<	Redirect input from a file
>	Redirect output to a file
>>	Append output onto a file
\|	Pipe output to another program's input

Examples

Command	Interpretation
myprog	Run program myprog. Read data from keyboard and write output to monitor.
myprog < test.dat	Run program myprog. Read data from file test.dat. Write output to monitor.
myprog > test.out	Run program myprog. Read input from keyboard. Write output to file test.out.
myprog >> moredata.out	Run program myprog. Read input from keyboard. Append output onto the end of file moredata.out.
prog1 \| prog2	Run programs prog1 and prog2. Use the output from prog1 as input for program prog2. We say that we pipe the output of prog1 into prog2, and the command is called a pipeline. (Pipelining will not be useful in the programming competition.)
myprog < test.dat > test.out	Run program myprog. Read data from file test.dat and write output to file test.out.

More Examples

When you are programming with an interpreted language, such as BASIC, Python, or (usually) Java, sometimes you need to indicate the language processor on the command line:

Command	Interpretation
python myprog.py	Run program myprog.py. Read data from keyboard and write output to monitor.
bwbasic myprog.bas < test.dat	Run program myprog.bas. Read data from file test.dat. Write output to monitor.
python myprog.py > test.out	Run program myprog.py. Read input from keyboard. Write output to file test.out.
bwbasic myprog.bas >> moredata.out	Run program myprog.bas. Read input from keyboard. Append output onto the end of file moredata.out.
python myprog.py < test.dat > test.out	Run program myprog.py. Read data from file test.dat and write output to file test.out.

Note that if your operating system recognizes the language of your program, it may automatically invoke the appropriate interpreter (e.g., python, or bwbasic, without need to specify it on the command line as in the second set of examples above.

With Unix, the normal way to make this happen is to put a special type of comment in the very first line of the program. The comment indicates the full path to the language processor. For Python, the line might look like this:
#!/usr/bin/python
With Windows, you can set an association between the file extension (.py, .bas, etc.) and the interpreter that should be invoked for files with that extension.

What kind of problems should I expect?

First of all, all problems involve text input and text output. Don't spend time learning the intricacies of graphical user interfaces, at least not for computer programming competitions.

Certain kinds of problems tend to appear often. These include

High-precision math. Learn how to do arithmetic with 100-digit integers. Hint: use arrays.
Encryption and decryption problems, and other problems involving ciphers.
Geometry problems, often involving figures in 3-space. Knowledge of arcane formulas, such as the law of cosines or Hero's formula is often useful. It is not necessary to memorize such formulas; just bring books or crib sheets with them written down.
Number theory problems. These involve prime and composite numbers. Be sure you know how to compute whether a number is prime or not.

Remember that you have only a few hours to solve five to ten problems. Thus, the thing that makes the problems difficult is not the length of the solution, but finding the algorithmic approach that works. It would be rare for the solution to a programming-competition problem to exceed 50 lines of code.

How can a team of three work efficiently with just one workstation?

How did they do it in the good old days?

Talk to someone who remembers the days of punchcard processing, and ask how to program efficiently when you get only two runs per week. I'm serious--that's how it used to be, and programmers still got their work done! Lack of processing power forces you to work efficiently; here are some ways to limit your use of the workstation, while still programming effectively:

Pick your problem. Then do your homework before you go to the workstation.

Basically, you need to do as much work as possible on the desktop (the furniture one, not the electronic one). Take the problem set, and each of you should read the problems. Decide which ones are the easier ones. (Experienced teams might want to leave the easier problems to one member, and the rest of you tackle the hard ones. Inexperienced teams should work on the easier ones first. If you have never solved a problem under programming competition conditions, you are inexperienced.) Pick one problem each and split up. Write your solution on paper.

Know which programming rules to keep and which to break.

Of course you know that many of the programming rules enforced by your teacher are not in effect for the programming competition. That doesn't mean you can forget them--when your program won't work, you'll be glad you used meaningful identifiers, indented to show structure, etc. The only rules you should ignore are the ones about modularity (most competition programs are not very long), commenting to describe the problem (you have the problem handout), and meaningful output (the problem statement specifies the output format).

Limit your time on the workstation.

When you have a program written, go to the workstation and enter it with an editor. Compile. Print the file, and mark the syntax errors. Go back to the desk and fix ALL of the errors. Go back to the workstation and fix the errors. It should take just one or two iterations of this to eliminate all syntax errors.

Desk-check to find logic errors.

Next comes fixing the logic. Assuming your program doesn't run correctly the first time, get an up-to-date printout and go back to the desk. Trace the program, i.e., take the test data, and execute the program line-by-line, just as the computer would do. Use a piece of paper and list all the variables; put their values below the variable names, crossing out old values and entering new values below as reads and assignments occur. You could use a debugger on your workstation to help with this, but deskcheck first. You will find lots of errors this way without tying up the workstation.

Take advantage of your teammates' brains.

Okay, you've eliminated the syntax errors and the obvious logic errors, but the program still doesn't work properly? It's time to involve some clear heads--your teammates'. Start by describing your solution to a teammate. Sometimes this makes the error obvious to you, even before your teammate gets to say a word. Next, try turning over the debugging to your teammate; sometimes when we concentrate on a problem too long the flaws become invisible.

Pay close attention to the reason that the judges rejected your program.

Finally, what do you do when your program seems to work, but the judges mark it "wrong"? First, look at the reason the judges give for rejecting your solution. Depending on the reason the judges give (and they tend not to describe the problem in much detail) check output formatting. Check that you haven't forgotten an unusual but valid special case. Check that you are reading every line of data. And check that your test-data file has the same format as given in the problem statement. Check that your program doesn't have too much output: this is often caused by C++ programmers who don't know how to detect end-of-file, and their programs process the last set of data twice.

Surf to:

Last modified: December 14, 2005
Webmaster: Michael P. Conlon