AIOJ

In algorithmic contests, there are many different types of problems.

Traditional Problems

Traditional problems are currently one of the more common types of problems in algorithmic contests.

Contestants need to submit source code. The judging system uses pre-prepared input data and corresponding output data as test points¹, compiles the submitted source code², lets the contestant's program read the input data, and determines whether the program is correct by comparing the contestant's output with the pre-prepared output. This judging method is called black-box judging³.

For a test point, a time limit and a memory limit are often also set.

The time limit is the limit on the program's running time⁴. The contestant's program must not run for longer than the given time limit on a test point.

The memory limit is the limit on the amount of memory used by the program. The maximum memory occupied by the contestant's program while running must not exceed the given memory limit.

After the program finishes running normally, the contestant's output is compared with the test point's output. This comparison generally removes the newline at the end of the file and spaces at the ends of lines, and then compares the entire text. For some special problems, a Special Judge is used for comparison.

After this process is complete, the judging system gives different judging results⁵ according to the program's running status:

Accepted (AC): The contestant's program is accepted.
Compile Error (CE): The contestant's program cannot be compiled normally.
Wrong Answer (WA): The contestant's program finishes normally, but its output does not match the test point's output.
Presentation Error (PE): The contestant's program finishes normally, but its format does not meet the requirements⁶.
Runtime Error (RE): The contestant's program terminates abnormally (the return value when the contestant's program ends is nonzero).
Time Limit Exceeded (TLE): The contestant's program runs for longer than the given time limit.
Memory Limit Exceeded (MLE): The maximum memory occupied by the contestant's program exceeds the given memory limit.
Output Limit Exceeded (OLE): The amount of output produced by the contestant's program exceeds the maximum limit.

In ICPC contests, your program must obtain AC status on all test points of a problem to be considered to have solved that problem. In OI contests, obtaining AC status on a test point is enough to receive that test point's score⁷.

Output-only Problems

Output-only problems are problems where the answers are submitted directly. Such problems generally provide input files and require the submission of an archive, folder, or plain file containing XXX1.out, XXX2.out, XXX3.out…XXXn.out.

After the answer files are submitted, the judging system compares them with the standard answers and awards a certain score according to the quality of the contestants' answers and the degree to which the task is completed.

Because output-only problems do not require a source program to be run, they have no time or memory limits.

There are generally two ways to solve such problems:

Do it by hand. This method is simple and crude, but it is helpless when the data is large.
Write a program to obtain the answer files.

Interactive Problems

Interactive problems are problems that require the contestant's program to interact with the judging program to complete a task. A common situation is that the contestant's program sends queries to the judging program and receives its feedback. The judging program may restrict the contestant's queries or adjust its response strategy to increase the number of queries as much as possible, which also brings more variations to the problem.

For a more detailed explanation of interactive problems, see Interactive Problems.

There are mainly the following two types of interaction. Although they differ considerably in technical terms, they have no practical difference in what algorithms they examine.

STDIO Interaction

STDIO interaction (standard I/O interaction) is the interaction method used by online platforms such as Codeforces and AtCoder, and is also the standard in ICPC contests. Codeforces provides a more concise explanation (in English).

Example LOJ #559.「LibreOJ Round #9」ZQC's Maze

Please note the content added at the bottom.

This is an interactive problem.

You are in a dark maze made up of $n \times m$ squares and need to reach the endpoint of the maze to complete the maze challenge.

Initially, you are at the starting point of the maze, $(1,1)$ , facing right, and the endpoint is at $(n,m)$ . Every two squares in the maze are connected, and there is exactly one path between any two of them; the length between two adjacent squares (that is, squares connected in the four directions: up, down, left, and right) is one unit. There may be walls between adjacent squares. The thickness of a wall is very small relative to a square and is ignored for simplicity. All boundaries of the maze have walls, and every wall is connected to the boundary. The maze is completely dark, which means that you cannot obtain any information other than $(n,m)$ .

To avoid getting lost as much as possible in the dark, each time you move forward you may only start from the current square and move along the wall on the left or right, keeping your left or right hand on the wall, and make the hand touching the wall move exactly one unit of length. Note that if there is no wall on the left or right, you cannot move in that direction.

Having been in the dark for too long will make you afraid, so you need to get out of the maze as soon as possible. If you do not get out of the maze within the prescribed number of steps, the challenge will fail.

For this type of problem, contestants only need to write queries to standard output as usual, flush the output buffer, and then read the result from standard input. Only after the contestant's program flushes the output buffer can the judging program connected to it through a pipe (called the interactor) receive the data immediately. In C/C++, fflush(stdout) and std::cout << std::flush can perform this operation (std::cout << std::endl also automatically flushes the buffer when outputting a newline, but std::cout << '\n' does not); in Pascal, it is flush(output).

Grader Interaction

Grader interaction is common in international OI contests such as IOI and APIO (especially contests on the CMS platform).

Example UOJ #206.【APIO2016】Gap

There are $N$ strictly increasing nonnegative integers $a_1,a_2,\cdots,a_N (0\leq a_1<a2<\cdots<a_N\leq 10^{18})$ . You need to find the maximum value among $a_{i+1}−a_i (0\leq i\leq N−1)$ .

Your program cannot read this integer sequence directly, but you can query information about the sequence through the given functions. For details about the query functions, refer to the implementation details below according to the language you use.

You need to implement a function that returns the maximum value among $a_{i+1}−a_i (0\leq i\leq N−1)$ .

For this type of problem, contestants only need to write a specific function to complete a task, and it interacts by calling several given auxiliary functions. To facilitate local testing, the problem provides a header file and a reference judging program grader.cpp (for Pascal, a library graderlib); contestants compile their program together with grader.cpp to obtain an executable file.

g++ grader.cpp my_solution.cpp -o my_solution -Wall -O2
./my_solution   # Run the program

The compiled program behaves similarly to a traditional problem program. It opens fixed files, reads data in a fixed format, calls the function written by the contestant, and displays the result and some information (such as the number of queries and whether the answer is correct) on standard output.

During actual judging, the contestant's program is compiled with a different grader.cpp. This grader.cpp sets all global symbols to static, meaning that it cannot be hacked by using conflicting names, but any attempt to break through the restrictions imposed by this version's grader.cpp will be judged as disqualification.

Differences

An obvious advantage of STDIO interaction is that it can support any programming language, but the time spent on input and output can easily become a bottleneck in problem design, sometimes making it impossible to distinguish differences in the time efficiency of programs. Grader interaction is exactly the opposite: since function-call overhead is small, it often allows on the order of $10^6$ queries, but language restrictions are its shortcoming.

If you design problems yourself or organize a contest, you need to carefully weigh and compare the two.

Communication Problems

Communication problems are problems that require two contestant programs to communicate and cooperate to complete a task. The first program receives the input to the problem and produces some output; the input of the second program is related to the output of the first (sometimes it is passed as an argument unchanged, and sometimes it is processed by the judging end), and the second program needs to produce the solution to the problem.

Examples of communication problems include UOJ #178. New Year's Greeting and #454.【UER #8】Snowball Fight.

Because of the differences in problem settings, there are many ways to test locally. Common forms include:

Entering input manually
Writing an auxiliary program to convert the output of the first program into the input of the second program
Connecting the standard input/output of the two programs with a bidirectional pipe

Because online judging platforms have limited support for communication problems, so far communication problems have only been common in IOI contests and contests held by a few online platforms such as UOJ. They remain a field awaiting exploration.

Function-completion Problems

Function-completion problems are problems that require contestants to complete a program. They can be understood as interactive problems in which the problem provides the contestant's code and asks the contestant to write auxiliary functions.

They usually take one of the following forms:

A program is provided, along with information about where the code block to be completed will be embedded.
No program is provided; instead, the input information is passed as the parameters of the function to be submitted.

This type of problem is relatively common on LeetCode and PTA - Pinti A.

Other Types

Example Quine

Write a program that outputs its own source code.

The code must contain at least ten visible characters.

The problem is very classic, but it is difficult to implement on the vast majority of OJs.

Reference Code

Note: The source code does not include the first line below (that is, // clang-format off).

// clang-format off
#include<cstdio>

char *s={"#include<cstdio>%cchar *s={%c%s%c};%cint main(){printf(s,10,34,s,34,10);return 0;}"};

int main(){printf(s,10,34,s,34,10);return 0;}

References and notes

Footnotes

Due to technical and resource limitations, the test points of a problem generally cannot cover all data satisfying the data range. ↩
For interpreted languages such as Python, the program is directly interpreted and run by the interpreter. ↩
In fact, the implementation of a judging system is much more complicated than this; this is only a general introduction to the judging process. ↩
More precisely, this is generally the program's user-mode time. ↩
Most of the judging results here also apply to other types of problems. ↩
Most judging systems classify PE status as WA status. ↩
Some test points may have partial scores. Contestants can receive a certain proportion of the score when they complete part of the task for a test point, or when their output is correct but not optimal enough. ↩