Ehem...some categories seem incorrect, and some problems cannot be classified into any categories and some problems can be classified into many categories...

There are still many problems that I always get Wrong Answer... If someone who see this website has got these problems accepted, please tell me your algorithm (please...), thanks :-)

ACM International Collegiate
Programming Contest 2000

Crossroads: How did you arrive at your present job?
Puglia: My undergraduate degree was in math and computer science. Directly out of collage I joined IBM as a programmer, I've been with IBM for 19 years and I'm now in engineering lab management.

Crossroads: What has it been like to be a technical woman at IBM?
Puglia: Mentors have been key to steering my direction. As the industry has grown, demand for technical staff far outstrips supply. Thus, one can move around to get experience in a variety of fields. IBM has a low attrition rate partly do to the size of the company, which means that there is lots of opportunity and variety internal to IBM.

Crossroads: In what ways does IBM encourage women staff members?
Puglia: IBM has corporate and regional networking for women, formal mentoring inside IBM with a focus in career development, and IBM takes time to think about how to recruit women to IBM and to information technology in general. IBM also is reaching out to the next generation of technical staff by starting programs for pre-collage students. For example, IBM in Canada has an annual one-day event to interest 7th and 8th grade girls in computing technology.

Crossroads: What are your problem solving techniques?
Puglia: When I encounter a problem that is outside my sphere of knowledge, I find an appropriate expert in the technology and also an expert with a business view of the situation if possible.

Crossroads: How do you get yourself to think creatively?
Puglia: I take a break and return later, or try to look at the problem from a different angle, or talk to someone else about the problem or idea.

Crossroads: How does the ACM programming contest encourage women to study computer science?
Puglia: The ACM programming contest is prestigious. When women compete in this contest, they show students that females can be successful in computer science. In 1999, 471 of the 13,000 participants at the regional contest level were women.

Crossroads: What further steps can encourage women to enter computing?
Puglia: Role models and mentors are very important, especially early. It is interesting to note that 45% of all jobs in America are filled by women but only 4% of the IT jobs are held by women.

Last Modified: Sunday, 21-Jan-01 17:06:25
Location: www.acm.org/crossroads/xrds6-5/progcon.html

A good team is essential to succeeding in a programming contest. A good programming team must have knowledge of standard algorithms and the ability to find an appropriate algorithm for every problem in the set. Furthermore, teams should be able to code algorithms into a working program and work well together.

As in all competitions, training under circumstances similar to contests is helpful. During the contest make sure you read all the problems and categorize them into easy, medium and hard. Tackling the easiest problems first is usually a good idea. If possible try to view the current standings and find out which problem is being solved the most. If that problem has not yet been solved by your team, try to solve it immediately, odds are it is an easy problem to solve. Furthermore, if the your solution to the easiest problem in the contest is rejected for careless mistakes, it is often a good idea to have another member redo the problem. When the judges reject your solution, try to think about your mistakes before trying to debug. Real-time debugging is the ultimate sin, you don't waste too much of your time with a single problem. In a five-hour contest you have 15 person-hours and five computer-hours. Thus, computer-hours are extremely valuable. Try not to let the computer sit idle. One way to keep the computer active is to use the chair in front of the computer only for typing and not for thinking. You can also save computer time by writing your program on paper, analyzing it, and then use the computer. Lastly, it is important to remember that the scoring system of a contest is digital. You do not get any points for a 99%-solved problem. At the end of the contest you may find that you have solved all the problems 90%, and your team is at the bottom of the rank list.

Your program must read input from a file or standard input according to the specification of the contest question. Judges will test your program with their secret input. If your program's output matches the judges' output you will be judged correct.

If the output of your program does not match what the judges expect, you will get an incorrect output notification. Generally, incorrect output occurs because you have either misunderstood the problem, missed a trick in the question, didn't check the extreme conditions or simply are not experienced enough to solve the problem. Problems often contain tricks that are missed by not reading the problem statement very carefully.

Your program does not produce an output. Generally this occurs because of a misinterpretation of the input format, or file. For example, there might be a mixup in the input filename e.g., the judge is giving input from "a.in," but your program is reading input from "b.in." It is also possible that the path specified in your program for the input file is incorrect. The input file is in most cases in the current directory. Errors often occurs because of poor variable type selection or because a runtime error has occurred, but the judge failed to detect it.

This error indicates that your program performs an illegal operation when run on judges' input. Some illegal operations include invalid memory references such as accessing outside an array boundary. There are also a number of common mathematical errors such as divide by zero error, overflow or domain error.

In a contest, the judge has a specified time limit for every problem. When your program does not terminate in that specified time limit you get this error. It is possible that you are using an inefficient algorithm, e.g., trying to find the factorial of a large number recursively, or perhaps that you have a bug in your program producing an infinite loop. One common error is for your program to wait for input from the standard input device when the judge is expecting you to take input from files. A related error comes from assuming wrong input data format, e.g., you assume that input will be terminated with a "#" symbol while the judge input terminates with end-of-file.

The maximum memory allowed on the Valladolid site is 32MB. This includes memory for global variables, the heap, and the stack. Even if you find that you have allocated much less than 64K memory, you will find that the judge often shows that more memory has been allocated. Also, you should not allocate 32 MB of global memory because 32MB is maximum for all types of memory. The maximum memory for real contests varies; for the World Final, it is greater than 128MB.

Many of us like to use DOS compilers like Turbo C++ 3.0 and Borland C++, which do not support allocating more than 64K memory at a time. It is always a good idea to allocate memory with a constant so that your test runs use less than 64K memory. Before the submit run, the size of memory can be increased by just changing the value of the constant. If you don't practice this, it is very likely that you will face problems like "Run time error," "Time limit exceeded," and "Wrong answer." An example:

When you submit a program to the judge, the judge gives you a response, but this response is not always accurate. For example, if you allocate less memory than is required, the program may not terminate (it may not even crash), and the judge will tell you "Time limit exceeded." On seeing this message, if you try to optimize your program rather than correcting the memory allocation problem, your program will never be accepted. The following example illustrates this problem. The skeleton of your program is as follows:

In this example, you have allocated a 100 element array. Your program attempts to access array element 100, which is out of the range [0..99], because of an error in the for loop statement. It will instead access the address of counter variable i. Because the value array[100] is set to 10000, the counter value will be set to 10000, so your loop will take a much longer time to terminate and may not even complete at all. So, the judge will give you message "Time limit exceeded" even though it actually is a memory allocation error.

There is always a sample input and output provided with each contest question. Inexperienced contestants get excited when one of their programs matches the sample output for the corresponding input, and they think that the problem has been solved. So they submit the problem for judgment without further testing and, in many cases, find they have the wrong answer. Testing only one set of data does not check if the variables of the program are properly initialized because by default all global variables have the value zero (integers = 0, chars = '\x0', floats= 0.0 and pointers = NULL). Even if you use multiple datasets the error may remain untraced if the input datasets are all the same size, in some cases descending in size or ascending in size. So, the size of the dataset sequence should be random. It is always a good idea to write a separate function for initialization.

Consider the following program segment:

When this program is run, many C/C++ compilers often show the error "Floating point format not linked." To get rid of this type of error, just change it to take the input into a normal floating point variable then assign that variable to the array, as follows:

Mark Dettinger was the coach for the team from the University of Ulm. He suggested to me that sometimes it is a good idea to avoid geometric problems unless one has prewritten routines. The routines that can be useful are:

• Line intersection.
• Line segment intersection.
• Line and line segment intersection.
• Convex hull.
• If a point is within a polygon.
• From a large number of points what is the number of maximum points on a single line.
• Closest pair problem. Given a set of points you have to find out the closest two points between them.
• Try to learn how to use C's built-in qsort() function to sort integers and records.
• Area of a polygon (convex or concave).
• Center-of-gravity of a polygon (convex or concave).
• Minimal circle, a circle with the minimum radius that can include the coordinates for a given number of points.
• Minimal sphere.
• Whether a rectangle fits in another rectangle even with rotation.
• Identify where two circles intersect. If they don't, determine whether one circle is inside another or if they are far away.
• Line clipping algorithms against a rectangle, circle, or ellipse.

takes one second to run for the judge, and an unknown N is the number of inputs given by the online judge. Send the following program with your code. Place it just after you have read the value of N.

From the runtime of the program you will know the number of input N. Using this method you can also determine how fast the judge's computer is compared with yours and thus find out the approximate time limit for any problem on your computer. Most of the live contests have a practice session prior to the contest. On this day you should try to determine the speed of the judge computer by sending programs consisting of many loops and nested loops.

Did you know that there was a mistake in a problem of the World Final 2000? The culprit problem was Problem F. The problem specification said that the input graph would be complete but not all inputs by the judge were complete graphs. At least one of the teams sent a program that checked if the input graph was complete. If the input graph was incomplete, then their program entered an infinite loop. So, the response from the judge was "Time limit exceeded." From this response they were able to know that some of the input graphs were incomplete and solved the problem accordingly.

It is always a good idea to use double instead of float because double gives higher precision and range. Always remember that there is also a data type called a long double. In Unix/Linux C/C++, there is also a long long integer. Sometimes it is specified in the problem statement to use float type. In those cases, use floats.

Those who have forgotten the advanced use of printf() and scanf(), recall the following examples:

This scanf() function takes only uppercase letters as input to line and any other characters other than A..Z terminates the string. Similarly the following scanf() will behave like gets():

Learn the default terminating characters for scanf(). Try to read all the advanced features of scanf() and printf(). This will help you in the long run.

If the content of a file (input.txt) is

and the following program is executed to take input from the file:

What will be the value of input and ch?

The following is a slight modification to the code:

What will be their value now? The value of ch will be '\n' for the first code and 'd' for the second code.

You should always try to remember the value of pi as far as possible, 3.1415926535897932384626433832795, certainly the part in italics. The judges may not give the value in the question, and if you use values like 22/7 or 3.1416 or 3.142857, then it is very likely that some of the critical judge inputs will cause you to get the wrong answer. You can also get the value of pi as a compiler-defined constant or from the following code:

You cannot always check the equality of floating point numbers with the = = operator in C/C++. Logically their values may be same, but due to precision limit and rounding errors they may differ by some small amount and may be incorrectly deemed unequal by your program. So, to check the equality of two floating point numbers a and b, you may use codes like:

Here, ERROR is a very small floating-point value like 1e-15. Actually, 1e-15 is the default value that the judge solution writers normally use. This value may change if the precision is specified in the problem statement.

Judges always try to make easy problem statements longer to make them look harder and the difficult problem statements shorter to make them look easy. For example, a problem statement can be "Find the common area of two polygons" -- the statement is simple, but the solution is very difficult. Another example is "For a given number find two such equal numbers whose multiplication result will be equal to the given number." Though the second statement is much longer than the first, the second problem statement is only asking to find the square root of a number, which can be done using a built-in function.

It is always nice to use the C/C++ assert() function, which is in the header file assert.h. With the assert() function you can check for a predefined value for a variable or an expression at a certain stage of your program. If for some reason the variable or expression does not have the specified value, assert() will print an error message. See your C/C++ documentation for further details.

It is almost always a good idea to avoid recursion in programming contests. Recursion takes more time, recursive programs crash more frequently especially in the case of parsing, and, for some people, recursion is harder to debug. But recursion should not be discounted completely, as some problems are very easy to solve recursively (DFS, backtracking), and there are some people who like to think recursively. However, it is a bad habit to solve problems recursively if they can be easily solved iteratively. In live programming contests, there is no point in writing classic code, or code that is compact but often hard to understand and debug. In programming contests, classic code serves only to illustrate the brilliance of the programmer. For example, the code for swapping two values can be written classically as:

But in a contest you will not get extra points for this type of code writing.

You should also be careful about using gets() and scanf() in the same program. Test it with the following scenario. The code is:

And the input file is:

What do you get as the value of name? "XXX" or "bbbbbXXX" (Here, "b" means blank or space)

Not all C/C++ functions available in DOS are available in UNIX. Check the documentation for the portability among operating systems. If a function is portable to UNIX, you can use it to solve problems on the Valladolid and USU sites. Use only standard input and output functions for taking inputs and producing outputs.

UNIX does not support the important function itoa(), which converts an integer to a string. The replacement for this function can be:

Try to find replacements for other functions that are not available in UNIX/LINUX.

Recently, I arranged several contests with Rezaul Alam Chowdhury and in collaboration with the University of Valladolid and have seen contestants make careless mistakes. The most prominent mistake is taking things for granted. In a problem I specified that the inputs will be integers (as defined in mathematics) but did not specify the range of input and many contestants assumed that the range will be 0->(2^32-1). But in reality many large numbers were given as input. The maximum input file size was specified from which one could assume what was the maximum possible number. There were also some negative numbers in the input because integers can be negative.

Compile error is a common error on the Valladolid site. It may seem annoying to compile and run a program, then send it to the online judge and get a compile error. Generally these errors occur because contestants omitted #include files. Some compilers do not require including the header files even when we use functions under those header files. However, the online judge never allows this. For example, some functions exist both in math.h and stdlib.h. For the online judge, you need to include both of the header files if you want to use them. Compiler errors also occur commonly when contestants do not specify the correct language. Often C code implemented in some compilers inadvertently takes advantage of C++ features. When the language specified to the judge is C, a compile error is generated. For example, the following may be compiled as a C program in a DOS/Windows environment but not in UNIX/LINUX.

Mail sent to the online judge should be in plain text format. If the mail is in Rich Text or HTML, the program will not compile. You should not send your program as an attachment.

When I first started programming for Valladolid, I used Turbo C++. After a program was successfully completed, I opened the source code in Notepad, selected the whole text, copied and pasted it in my mail editor, and sent the program to the Valladolid site. I got a Compile error message but could not discover the cause. One day, I pasted it in my email editor, saved it as a text file, and then opened it in my DOS text editor. I discovered some mysterious characters in the file, which were invisible in Windows. If you receive a Compile error message and cannot discover the cause, check if your mail or text editor is adding extra symbols to your code.

Compile errors are caused by the use of the functions which are only available in DOS and not in LINUX, such as strrev(), itoa() etc.

C++ allows a comment style that starts with //. If the mailer wraps a comment to two lines, you may get a compile error.

The next section provides suggestions for solving problems for the Valladolid online judge.

There are four types of input in the online judge. (Latest change)

• Non-multiple input without special correction program (Red Flag)
• Non-multiple input with special correction program (Orange Flag)
• Multiple input without special correction program (Blue Flag)
• Multiple input with special correction program (Green Flag)

"Multiple input programs" are an invention of the online judge. The online judge often uses the problems and data that were first presented in live contests. Many solutions to problems presented in live contests take a single set of data, give the output for it, and terminate. This does not imply that the judges will give only a single set of data. The judges actually give multiple files as input one after another and compare the corresponding output files with the judge output. However, the Valladolid online judge gives only one file as input. It inserts all the judge inputs into a single file and at the top of that file, it writes how many sets of inputs there are. This number is the same as the number of input files the contest judges used. A blank line now separates each set of data. So the structure of the input file for multiple input program becomes:

Note that there should be no blank after the last set of data. Sometimes there may be, so always check. The structure of the output file for a multiple input program becomes:

The USU online judge does not have multiple input programs like Valladolid. It prefers to give multiple files as input and sets a time limit for each set of input.

There are some issues that you should consider differently for multiple input programs. Even if the input specification says that the input terminates with the end of file (EOF), each set of input is actually terminated by a blank line, except for the last one, which is terminated by the end of file. Also, be careful about the initialization of variables. If they are not properly initialized, your program may work for a single set of data but give correct output for multiple sets of data. All global variables are initialized to their corresponding zeros. Thus, for a single set of input, the initialization may not be necessary, but for multiple inputs, it is a must.

Always be sure to see the Fixing Mistake section of the Valladolid online judge. Some of the problems in the Valladolid online judge have errors, which are corrected on this page.

Always try to read the message board of the Valladolid site. You will learn many things from other programmers. The USU online judge also has a message board. You can also submit your own views and problems via these boards.

Many people believe that the best programmer is the one with greatest knowledge of algorithms. However, problem-solving skills contribute to programming success as much as raw knowledge of algorithms. Don't lose your nerve during a contest, and always try to perform your best.

Shahriar Manzoor is grateful to Prof. Miguel A. Revilla for letting him arrange online contests and to Prof. William B. Poucher for asking people to participate in the World Final Warm-up Contest. He is also grateful to Ciriaco Garcia, Antonio Sanchez, F. P. Najera Cano, Fu Zhaohui, Dr. M. Kaykobad, Rezaul Alam Chowdhury, Munirul Abedin, Tanbir Ahmed, Reuber Guerra and above all his family.

Contest Environment

• Each team will have access to three compilers: a Pascal Compiler, a C Compiler and a C++ Compiler. Each submission may be in either language, without regard to the language used in previous submissions.
• Each submission must be one self-contained program. It must not rely on the presence of external data files (except for the test data input file), nor may it create such files.
• Submissions in Pascal must adhere to the ISO level 1 standard. No extensions to the language are permitted. It is the responsibility of the team, not the compiler, to ensure that the submission meets the required standard.
• Submissions in C must adhere to the ANSI standard X3.159-1989. The only permitted extension to the language are chosen functions of the ANSI standard library. It is the responsibility of the team, not the compiler, to ensure that the submission meets the required standard.
• Submissions in C++ must adhere to the language as defined in "The C++ Programming Language, Second Edition" by Bjarne Stroustrup. The only permitted extensions to the language are chosen functions of the ANSI C standard library and the iostreams library. It is responsibility of the team, not the compiler, to ensure that the submission meets the required standard.

Conduct of the Contest

• At least one problem will be posed. As far as possible, problems will avoid dependence on detailed knowledge of a particular applications area or a particular contest language.
• Problems will be posed in English.
• Solutions to problems submitted for judging are called runs. Each run is judged as accepted or rejected, and the team is notified of the result. Rejected runs will be marked as either "compile time error" or "run-time error" or "time-limit exceeded" or "wrong answer" or "presentation error" or "contest rule violation".
• Notification of accepted runs can be suspended at the appropriate time to keep final results secret. A general announcement to that effect will be made during the contest. Notification of rejected runs will continue until the end of the contest.
• While the contest is scheduled to last exactly the announced hours, the Online Judge manager has the authority to lengthen the contest in the event of unforeseen difficulties. Should the Contest duration be altered, every attempt will be made to notify contestants in a timely and uniform manner.
• The Contest Judges set by the organization which organizes the contest are solely responsible for determining the correctness of submitted runs. They are also responsible for determining the winners of the contest. The judging staff is empowered to adjust for or adjudicate unforeseen events and conditions. Their decisions are final and may not be appealed.
• Teams are ranked according to the most problems solved. Teams who solve the same number of problems are ranked by least total time. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the accepted run plus 20 minutes for each rejected run. There is no time consumed for a problem that is not solved.
• The Online Judge manager is solely responsible for ruling on unforeseen situations and interpreting this rules.

In this page, I would like to say a few things that you might be interested in making you a better programmer. You may disagree with me. That's fine. Everybody has their own opinion. However, I'm sure there are at least one thing that you will agree with me ^_^.

1. In doing every problem, anything that the problem maker consider important.
   It might be something that you think is important or might not. Even the silliest thing can be an important thing.
2. Do not make any assumption unless you have to.
   Say, if the problem statement doesn't state the limit of the input, don't assume that the limit is N. Ask first. If you don't get any satisfying answer, you may then assume (also take note of that assumption) or do as in Shahriar's advice (making a simple dummy program).
3. Outline your program, say in pseudocode (daily language).
   This is an important issue. You may say that this is time consuming, etc., but by doing so, you usually eliminate any major mistake that may arise.
4. Use variable names that you can relate to.
   Use wordy names if you have to, although it is not advisable especially in a time-limited competition. By doing this, you allow yourself to cut the time needed to figure out what the variables are for when you debug your program. I remember doing a contest in my early year as programmer. I used alphabet as my variables. If I am to explain that particular program today, I might not be able as I can't remember what they are for.
5. Make simple comments at places you consider important.
   It has the same purpose.
6. Use indentation and blank lines.
   Again, same purpose. However, when size does matter, you might want to eliminate all unnecessary blank spaces.
7. Watch out for any limitation.
   Still fresh in my mind, I used signed 16-bit integer for a problem where the input can go up to 50000. That particular mistake made me lose the entire problem.
8. In connection with above, use the largest possible variable type.
   Watch out though, if the problem specifies integer, you use integer type, not floating-point type. This advice only applicable when there is no or extremely big space-limit. As you grow, you may find this particular advice unimportant. The smaller the variable type, the faster the program run.
   Simple example, compare adding two 32-bit integers and two 16-bit integers. The former need 32 adding process while the latter only need 16 adding process. Of course, you have to watch out for the limit.
9. In a competition, watch out for execution-time limit.
   Efficiency is important. But also take this into mind, don't be too efficient if it makes the program a lot complicated. Always try to be simple. If you find that your program too slow, first of all try to think for another way. If you can't find any, you then develop short cuts.
10. Get used to the platform.
    From what I heard, using "Enter" can give different results in different platform. Say on Linux, you might only get CR (Carriage Return), but on Unix, you might get LF (Line Feeder) or the other way around, I don't really remember. This can get really annoying especially in reading the input. There shouldn't be any big trouble for C users, but for Pascal users, say "bye bye" to ReadLn.
11. End of Input <> End of File!!!
    This is very tricky. I've found at least 7 different types of input. The one with additional character after the end of the input, the one with no LF character, the one without CR character, etc. The best way to get used to this problem, is to follow the advice below.
12. Practice, practice and practice. I know, this is the most ... part, but still it's unavoidable. If there is any short cut, I would have taken it. :(

© 2000 Ilham W. Kurnia

A few seconds after sending the E-Mail with your program, you'll receive a confirmation reply by E-Mail from the judge system (unless you have selected not to receive replies by E-Mail: note that there is enough information in the Web, updated in real time).

Your program will be compiled and run in our system, and the automatic judge will test it with some inputs and outputs, or perhaps with a specific judge tool. After some seconds or minutes, you'll receive by E-Mail (or you'll see in the Web) one of these answers:

• Accepted (AC) (and the CPU time & memory used): OK! Your program is correct!. Note that during true contest perhaps only 1 CPU minute will be allowed If your program spents a reasonable time, it may be Ok, but this depends on the judge power in comparison with the true contest computers.
• Presentation Error (PE): Your program outputs are correct but are not presented in the correct way. Check for spaces, justify, line feeds...
• Accepted (P.E.): Same as above, but the Presentation Error is intended only for contests. The 24-hours judge takes it only as a warning. Don't worry a lot, since many of our problems have the output specification not very fine.
• Wrong Answer (WA): Correct solution not reached for the inputs. The inputs and outputs that we use to test the programs are not public (it is recomendable to get accustomed to a true contest dynamic ;-).
• Crash (WS): Your program failed during the execution (segmentation fault, floating point exception...). The exact cause is reported to the user.
• Time Limit Exceeded (TL): Your program tried to run during too much time; this error don't allows you to know if your program would reach the correct solution to the problem.
• Memory Limit Exceeded (ML): Your program tried to use more memory than the judge default settings. If you are sure that such problem needs more memory, please contact us.
• Output Limit Exceeded (OL): Your program tried to write too much information. This usually occurs if it goes into a infinite loop.
• Restricted Function (RF): Your source program tried to use a not allowed function (such as fork(), fopen(), ...)
• Compile Error (CE): The compiler (gcc/g++/gpc) could not compile your ANSI program. Of course, warning messages are not error messages. The compiler output messages are reported you by E-Mail.
• Submission Error (SE): You don't specified correctly the @JUDGE_ID fields (a incorrect User ID, number of problem...).
• Can't Be Judged (CJ): The judge hasn't test input and outputs for the selected problem. While choosing a problem be careful to ensure that the judge will be able to judge it!.
• Access Denied (AD): Your Internet address is not allowed to submit problems. Maybe you have setup to accept programs only from your E-Mail address: edit and update your personal information in the Web. Otherwise, contact us.
• Non Authenticated (NA): Your E-Mail is not authenticated or the submit tool did not sent authentication information. If you aren't a hacker, please contact us.
• Out Of Contest Time (OC): this message can only appear during a contest, if a program is submitted out of contest time.
• Delayed (DL): if the judge host is too busy, the execution of programs which spent too much resources (inside the allowed limits) is delayed by some seconds or minutes. Don't re-submit again your program (the judge would spent even more time before replying).
• Judge Disabled: this message may appear only during internal maintenance tasks, which are previously announced most times. Probably, your program will be processed later unless the letter explicitly tells you to resubmit it again in future.
• Judge Not Ready!: By some reason, the judge host has just rebooted and the judge software is currently being loaded. Try to submit again your program within a few seconds.

All E-Mails received and the results of their actions are logged; this would allow us to detect any possible intention to use the judge for incorrect purposes. If you submit several programs for the same problem and you get several accepted messages for it, you'll appear in the ranklist only with your better solution (less CPU time and/or memory spent).

A good problem set is the key to a successful programming contest. The production of such a problem set should be taken very seriously and requires a major effort by a number of people. The guidelines presented in this note should enable you to do a good and enjoyable job.

The Head Judge is responsible for the timely production of a suitable problem set. In the contest, each team should be provided with two (2) copies of the problem set.

The problem set consists of at least six (6) problems. There should be sufficient variation in both the difficulty and the computational aspects of the problems. Two (2) easy problems and one (1) more difficult problem should be included. All problems should be original in some respect. For example, a problem can be new as such, or its embedding into a context can be new, or its boundary conditions can be new.

The reason for having at least six problems is that we prefer to measure the strength of teams by number of problems solved and not by amount of time spent on solving them. (Recall that ranking is done first on account of number of problems solved and, in case of a tie, on account of time spent.) To provide sufficient resolution, the problem set should be so large that the strongest team can solve (almost) all problems just in time. Of course, the number of competing teams, the difficulty of the problems, and the duration of the contest are also important factors. At the Finals (a six-hour contest with 24 teams; five hours since 1990, and over 50 teams in 1998.) typically eight problems were posed with satisfactory results. The reasons to include at least two easy problems are the following.

1. Easy problems can serve as starters and allow early usage of the PC (this requires that the teams make the right judgment about difficulty; hence, assessment of problem difficulty is an important aspect of the contest).
2. Weak teams should have some fun too; therefore, they should be enabled to solve---not just work on---some problems.
3. Strong teams should be able to solve easy problems quickly (say, in half an hour), which acts as an incentive for themselves and others (including judges etc.).
4. Teams solving no problems cannot be differentiated in the final ranking, whereas teams that solved at least one problem can be ranked according to time spent.

The presence of one or two more difficult problems serves to differentiate the strongest teams on account of the number of problems solved and not just on account of time spent. Furthermore, difficult problems make the contest more interesting: we would not want the contest to degrade to mere implementation jobs.

We know from experience that it is unlikely that an interesting problem is too easy. (Keep in mind that teams usually read all problems first and need to decide on an appropriate order to solve them, before they start programming. Hence, it unlikely that a problem is solved within 15 minutes.) Moreover a problem can readily be made more difficult; making it easier is often painful. Also note that it hardly makes sense to include problems that are too difficult. The only thing that the presence of a too difficult problem can measure is the ability of the teams to recognize and then ignore the problem. This is not worthwhile the trouble of including such a problem.

The reason to cover various computational aspects are the following.

1. If one aspect (say, juggling with dates or numerical approximation) appears in many of the problems, then ``specialists'' in that field have an advantage.
2. Variation allows teams to work on those types of problem they like most (only strong teams will have little choice: they should solve all problems). On the other hand, a nice thing about two problems with a common aspect is that a team recognizing this fact may benefit by writing a combined solution.

The reasons for having original problems are

1. to make the contest interesting for the contestants and the organizers,
2. to avoid giving unfair advantage to teams familiar with particular problems, and
3. to attract some attention from the Computing Science community.

Each problem must have a short and unambiguous identifier, for instance, a letter. This identifier will also be used on the Run Envelopes, Clarification Requests, and Standings. The cover page of the problem set mentions the date, the number of problems, their identifiers, and the number of pages. For example,

This is the problem set for the
1990--91 European Regional Programming Contest
held on Saturday November 3, 1990.
It contains 7 problems labeled A through G
printed on 10 numbered pages.

The following phases can be distinguished in the production of a problem set.

1. Generate ideas for problems, making explicit what the crucial computational aspect is of each problem.
2. Select initial set, taking into account the need for originality and variation in difficulty and computational aspects, and eliminating too difficult problems.
3. Specify problems in detail.
4. Write complete programs for problems (including alternative solutions where necessary).
5. Write input validator and output verifier.
6. Produce test input data files (and test output data files where necessary).
7. Validate examples, validate test data, check spelling.
8. Print a sufficient number of copies of the problem set.

Each phase should take no more than one week to complete. We suggest that you have a review meeting at the end of each phase.

The Head Judge needs to take into account that only afterwards a problem may turn out to be unsuitable. Initially, aim at eight or even nine problems. In the 1989--90 European Regional we posed all nine problems that we had prepared (none had to be abandoned) and, contrary to our expectations, one team was able to solve all nine of them!

See to it that for each problem there is one person taking full responsibility for all aspects (this would usually include judging as well). Of course, it is also a good idea to have Problem Creators read each other's specifications and possibly even attempt solutions.

Here are some facts to keep in mind when creating a problem.

Each team consists of up to four (4) programmers (usually computing science students at undergraduate or graduate level). They have one (1) personal computer with Turbo Pascal 5.5 at their disposal and they may consult non-computer-readable literature and non-programmable calculators. The contest lasts six (6) hours. However, for the Finals that will now be five hours. By the way, they reduced the length of the Finals so that

1. there would be more excitement at the end of the contest.
2. it would be less likely that the winners be known prior to the Banquet.
3. teams not making much progress would feel less frustrated.
4. judges would not feel compelled to increase the number of problems (compensating for the increased power of modern software development environments).
5. judges would be less tired and less likely to err.
6. five hours fits nicely between 1pm and 6pm.

Judging is done by running the submitted program for some test cases and subsequently checking its output. A program is either accepted or rejected. In the latter case, the team is given a 20 minutes' penalty for the problem and one of the following reasons for rejection is indicated:

1. Syntax Error
2. Run-Time Error
3. Time-Limit Exceeded
4. Wrong Answer
5. Failed Test Case
6. Inaccurate Answer
7. Too Little/Much Output
8. Bad Output Format
9. Check Clarifications

The run-time limit is three (3) minutes unless otherwise indicated in the problem specification. There is still some controversy over these messages. We will come back to them in the section on testing.

A problem may be interesting for several reasons. Important aspects can be

• clever algorithm
• efficiency (time and/or space)
• preprocessing
• complicated case analysis
• irregularities
• internal data representation
• input parsing
• output format
• tricky issues (going beyond maxint, end-of-file detection)
• common subproblems

Problems will be posed in English. Each problem prescribes the names of the program source file and the data input and output files. Since judges recompile the program there is no need to mention the name of an executable file. A problem may require more than one input and/or output file. An execution time-limit is mentioned if it deviates from the standard amount (see above).

The problem specification will usually start with a story and the introduction of some concepts, possibly accompanied by instructive examples. This is followed by a short informal description of the programming task and then a more precise specification of input and output format and their desired relation. Finally, an example input set with corresponding output is given.

Of course, the aim is to specify a problem completely and unambiguously. Although teams may make clarification requests, it is better to obviate these by a careful problem specification. Keep in mind that English is a second language for most of the teams. Also keep in mind that long specifications tend to be more controversial than concise ones.

The following example was adapted from the 1989--90 Finals held in Washington D.C., USA.

The Problem Creator should summarize the crucial computational aspects of the problem for the Head Judge. In this summary, tricky issues, boundary cases, and required efficiency considerations may be mentioned. Of course, the summary should not be revealed to the contestants until after the contest. For the above sample problem the following summary might be produced.

Once a problem has been specified it is necessary to obtain a better estimate of its suitability for the contest. This can be done by writing a complete program for the problem. That way one may encounter some trouble spots that otherwise would remain unnoticed.

It should take the Problem Creator, who is intimately familiar with the problem after specifying it, no more than a couple of hours to implement a working solution. That solution should be more or less along the lines of an ``intended'' solution and should not make use of implementation specific extensions to Pascal. It is not necessary to come up with a very neat and fully annotated solution (in case you still think that would be a waste of time). From this solution one can also determine some limits on run-time and memory utilization, which are useful when putting together test cases (discussed in the next section).

If it is the intention to rule out some straightforward solutions on account of their inefficiency (e.g. O(N³) instead of O(N)), then it is necessary to implement ``unintended'' alternative solutions as well. The alternative solutions must fail the tests (see below) even if they were otherwise cleverly coded, possibly using some implementation specific extensions to Pascal! You may sometimes be surprised how ``good'' unintended solutions turn out to be.

Apart from the bare ``intended'' solution it is also necessary to write another program. Input validation is not part of the contestants' programming task. That is, teams may assume that input supplied to their programs is in agreement with the specification. The Problem Creator, however, has to see to it that examples and test input data are valid. It is strongly recommended that input validation is done by a program. The input validator may be implemented as a separate program or may be incorporated in an ``embellished'' solution. N.B. The embellished solution need no longer be suitable for run-time and memory utilization assessment, so keep a copy of the original ``bare'' solution!

Although we are interested in formally correct programs for the problems, judgment is based on testing. Hence, testability is an important issue.

If there is not much variety in the required output of a problem (e.g. only yes/no), then a program might ``unrightfully'' be accepted when it correctly ``guesses'' the output. Try to avoid this.

The test cases that are applied to exercise a program must allow a good assessment of the program's correctness. It may therefore be necessary to run more than one test case. Often it is convenient to specify the problem such that one input file actually allows a sequence of tests to be applied (this is not the case for Problem A above). Don't forget, however, that an execution time-limit must be set for the entire run (default unless otherwise stated).

In order to generate test cases it is desirable to have a programmed solution for your problem. In order to judge a program it is convenient to have an output verification program. This verifier takes the output of the submitted program and checks it, e.g., against the output of a known correct program or/and with the aid of the input file. It may be convenient to specify the problem such that each input file produces a unique output file, in which case the evaluator can simply compare two files character by character (this is the case for Problem A above). Note, however, that in this case the output must be completely specified, taking into account such oddities as trailing blanks, leading zeroes, empty lines, etc. ``Normalization'' of output text files before doing the output verification partly solves this problem (also see my note Additional Contest Information).

Of course, a simple file comparator cannot distinguish between such errors as Wrong Answer and Bad Output Format (but for the time being we do not mind). Currently, the error messages issued by the judges in the Finals when they reject a program are not sufficiently well-defined to be useful for automated judging. In particular, the messages Failed Test Case, Inaccurate Answer, Too Little/Much Output, Bad Output Format, and Check Clarifications are controversial. My suggestion is to ignore these possibilities. The teams will be told that these messages will not be issued. Hence, Wrong Answer covers any error not covered by Syntax Error, Run-Time Error, and Time-Limit Exceeded.

To get a good insight into the severity of the test cases it may be necessary to write yet another program that collects some statistics (to determine which situations occur how often). [Good example to be provided.] Like the input validator, this program could be a separate program or it could be incorporated in an ``embellished'' solution. It is sometimes also advisable to write a program that generates (possibly random) test cases with certain predetermined characteristics.

Aim at eight or nine original problems. Include two easy problems and one or two more difficult problems. Avoid too difficult problems. Cover various computational aspects. The best team should be able to solve (almost) all problems in the available time.

Each problem should fall under the responsibility of one person. For each problem the Head Judge needs to receive the following items from its Problem Creator:

1. a specification,
2. a short description of the crucial computational aspects,
3. a programmed solution (possibly also alternative solutions),
4. an input validation program,
5. an output verification program (the verifier could be a simple file comparator for deterministic problems, in which case a test output data file must be provided), and
6. a set of test input data files (preferably just one), including their typical run-time and some motivation for their discriminating power.

Items 1 and 2 are discussed in the section on Problem Specification, items 3 and 4 in section Problem Solution, items 5 and 6 in section Testing.

It would be nice if the Head Judge prepares solution suggestions to hand out after the contest. These could, for instance, be based on the ``description of crucial computational aspects'' as provided by the Problem Creators.

In case you want to organize contests more often, it is advisable to do an evaluation afterwards, in which you attempt to find out how well the objectives have been met. For instance, how difficult did the problems turn out to be, how many and which Clarification Requests were made, how well were the test cases, were any programs accepted unrightfully, were there any programs that got rejected because they failed on a single test case only, etc.

University of Valladolid (Spanish Judge) Online Judge contains past years ACM contest problems (either regional or finals) plus problems from another source. You can solve these problems and submit your solution to this Online Judge. The correctness of your program will be reported as soon as possible. Try solving these problems and see your name on the top-200 author rank list :-)

Note that even though this loop executes N*(N+1) / 2 iterations of the if statement, it is O(N^2) since doubling N quadruples the execution times.

Some problems can be rephrased into a somewhat different problem such that if you solve the new problem, you either already have or can easily find the solution to the original one; of course, you should solve the easier of the two only. Alternatively, like induction, for some problems one can make a small change to the solution of a slightly smaller problem to find the full answer.

We have a variety of programming languages in this world. In this section I want to give a comparison between C, Java and Pascal

Alias: Ackermann Function or Collatz Sequence

Any number can be reduced to 1 using this algorithm.

Sample: Ackermann function of (11) = 11-34-17-52-26-13-40-20-10-5-16-8-4-2-1

It's about how to place 8 queens on 8x8 chess board so that no queen can attack any other queen.

There are 92 possibilities to do so, don't believe it? then read on.

First strategy is to guess a solution... How many ways to arrange 8 queens on a 8x8 chessboard? Unfortunately, there are 4 426 165 368 ways to do so, too many.

Next approach is that no queen can reside in a row or a column that contain another queen, In other words, each row and column can contain exactly one queen, this reduce the possibility to 8! = 40 320 possible arrangements. This one is quite reasonable.

The best solution is to use backtracking (recursive). If a particular guess leads to a dead end, you go back and then try another solution.

This is my Web page for the ACM Programming Contest and Calvin's teams.

Your team will be given one computer to use. You can use it only to write your programs.

You will also be given a work area. Depending on the contest site, you may or may not have a chalk- or white-board available for your team. You should plan on using paper (which may or may not be provided).

During the five hours of the contest, your team will have to write six (or more) programs. When you submit a program, judges will compile and execute your code on some test data. You will get to see only a (very) small portion of this test data.

If your program works fine, you are given a score based on the elapsed time since the beginning of the contest. If your program fails, the judges will notify you of this and give you an extremely generic comment like "Bad format of output" or "Incorrect output". They will not tell you how the format is bad or how the output is incorrect. You can submit the program as many times as is needed, but each time it is rejected, you are given a time penalty for that problem.

The team that solves the most problems in the least amount of time (including time penalties) wins.

Judges can only answer questions of procedure or clarification. They cannot answer questions about what's wrong with your program.

We'll be competing at Western Michigan University in Kalamazoo. There's no word yet on the environment you'll be using there. In 2000, at Case Western University, the computers had (crippled?) Mandrake Linux installed on the computers.

The key to this contest is writing programs quickly. This implies quick-and-dirty solutions. While this means you maybe shouldn't spend the time on a full Object Centered Design a la CPSC 185, don't abandon design and programming style all together. Good design and good programming style lead to good programs; sacrifice them too much at your own debugging peril.

Keep in mind that the judges never look at your code. (Well, they might if they're curious, but it won't affect their acceptance of the program, and they won't say anything about it.) The look and design of the program matters only to you. So do enough so that it's easy for you and your teammates to debug, but not any more than that.

You probably should not even worry about separate file compilation. Just put everything into one file the easiest way you can.

You should work out a consistent style with your teammates since you'll (most likely) have to read and debug each other's code.

Do not program for bad input unless the problem specificly asks for it. (I'd be very surprised in any problem did ask for error handling.) Your program will be tested only with good data.

Write a few programs (based on the problems from previous contests) before the contest that merely read in different intput formats. Print off copies of these programs so that you have them with you during the contest. Actually do this. No, I'm completely serious. If you do nothing else, at least have a library of programs that handle a variety of I/O. It will not be enough that you get the code from someone else because you will have to work through the code during the contest. You cannot afford to spend time looking up the perculiarities of I/O routines.

Use your best judgement in terms of what problems are the easiest to solve. After a few teams have solved a problem or two, check the results. It's pretty obvious after a while which problem (or problems) are the easiest.

If you're not already working on that problem, I'm inclined to suggest that you immediately switch over to the easy problem as identified by those other teams if you're not already working on it. There are obvious drawbacks to this, and it does depend on how far you are on whatever problems you're already working on.

I'm unsure what's the best way to organize teams, but the Crossroads article linked above seems to have some good ideas. Discuss team strategies with your team. The Think Tank approach sounds the best to me, but you have to train for it.

My guess is that you'll be able to configure you're environment during the practice contest on Friday night. So you should be able to type in (or perhaps copy) editor configuration files and the like. Bring printed copies of these configuration files in case the computers are not connected to the Internet.

Here are some issues that have been important in other contests I've seen.