Skip to content

Overview of Problem Types

In algorithm competitions, there are various types of problems.

Traditional Problems

Traditional problems are the most common type in current algorithm competitions.

Contestants need to submit source code. The judging system uses pre-prepared input data and corresponding output data as test cases1. After compiling the submitted source code2, the contestant's program reads the input data, and the contestant's output is compared with the pre-prepared output to determine if the program is correct. This judging method is called black-box judging3.

For a test case, time limits and memory limits are often set.

Time limit refers to the restriction on program running time4. The contestant's program must not exceed the given time limit on a test case.

Memory limit refers to the restriction on the amount of memory used by the program. The maximum memory occupied by the contestant's program during runtime must not exceed the given memory limit.

After the program finishes running normally, the contestant's output is compared with the test case output. This comparison is generally done by filtering trailing newlines and trailing spaces, then performing a full-text comparison. For some special problems, Special Judge is used for comparison.

After this process, the judging system will give different verdicts5 based on 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 ends normally, but its output does not match the test case output.
  • Presentation Error (PE): The contestant's program ends normally, but the format does not meet the requirements7.
  • Runtime Error (RE): The contestant's program ends abnormally (the program's return value upon termination is non-zero).
  • Time Limit Exceeded (TLE): The contestant's program's running time exceeds 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 from the contestant's program exceeds the maximum limit.

In ICPC competitions, your program must achieve AC status on all test cases of a problem to be considered as solving that problem. In OI competitions, achieving AC status on a test case allows you to receive the points for that test case6.

Output-only Problems

Output-only problems are problems where you directly submit the answer. This type of problem usually provides input files and requires submitting a compressed package, folder, or plain files containing XXX1.out, XXX2.out, XXX3.out…XXXn.out.

After submission, the judging system compares the answer files with the standard answers and awards a certain score based on the quality of the contestant's answers and the task completion.

Since output-only problems do not require running source programs, there are no time or memory limits for these problems.

There are generally two methods to solve such problems:

  • Manual solving. This method is simple and straightforward, but it becomes ineffective when encountering larger data.
  • Write a program to obtain the answer files.

Interactive Problems

Interactive problems are problems that require the contestant's program to interact with the judge program to complete a task. A common scenario is that the contestant's program sends queries to the judge program and receives its feedback. The judge program may impose restrictions on the contestant's queries or adjust its response strategy to maximize the number of queries, which also brings more variations to the problem.

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

There are mainly two types of interaction methods. Although they differ technically, they have no practical difference in examining the essence of algorithms.

STDIO Interaction

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

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

Please note the added content at the bottom.

This problem is an interactive problem.

You are in a dark maze composed of \(n \times m\) squares and need to reach the end of the maze to complete the maze challenge.

Initially, you are at the starting point of the maze, i.e., \((1,1)\), facing right, and the end point is at \((n,m)\). Any two squares in the maze are connected, and there is exactly one unique path between them. The distance between two adjacent (i.e., connected up, down, left, right) squares is one unit length. There may be walls between two adjacent squares; the thickness of the walls is negligible compared to the squares. The boundaries of the maze all have walls, and each wall is connected to the boundary. The maze is completely dark, meaning you cannot obtain any information except for \((n,m)\).

To avoid getting lost in the dark, each time you advance, you can only start from the current square, follow the left or right wall, keep your left or right hand on the wall, and move exactly one unit length along the wall. Note that if the left or right wall does not exist, you cannot advance in that direction.

Staying in the dark for too long will make you feel fear, so you need to exit the maze as soon as possible. If you do not exit the maze within the limited number of steps, the challenge will fail.

For such problems, contestants only need to write queries to standard output as usual, flush the output buffer, and then read the results from standard input. After the contestant's program flushes the output buffer, the judge program (called the interactor) connected to it via a pipe can immediately receive this data. In C/C++, fflush(stdout) and std::cout << std::flush can achieve this operation (using std::cout << std::endl to add a newline also automatically flushes the buffer, but std::cout << '\n' does not); in Pascal, it is flush(output).

Grader Interaction

Grader interaction is commonly seen in international OI competitions like IOI and APIO (especially competitions on the CMS platform).

Example Problem UOJ #206.【APIO2016】Gap

There are \(N\) strictly increasing non-negative 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 directly read this integer sequence, but you can query information about the sequence through given functions. For details about the query functions, please refer to the implementation details section below according to the language you are using.

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

For such problems, contestants only need to write a specific function to complete a certain task, which interacts by calling several given auxiliary functions. To facilitate local testing by contestants, the problem provides a header file and a reference judge program grader.cpp (for Pascal, a library graderlib). Contestants compile their own program together with grader.cpp to obtain the executable.

1
2
g++ grader.cpp my_solution.cpp -o my_solution -Wall -O2
./my_solution   # Execute the program

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

During actual judging, the contestant's program is compiled with a different grader.cpp. This grader.cpp will call the contestant's written function in a similar way and record its score. Generally, all global symbols in this version of grader.cpp are set to static, meaning it cannot be cracked by conflicting names, but any attempt to break the grader's restrictions will be disqualified.

Differences

An obvious advantage of STDIO interaction is that it can support any programming language, but the overhead of input/output can become a bottleneck in problem design, sometimes making it impossible to distinguish differences in program time efficiency. Grader interaction is the opposite; due to the low overhead of function calls, it often allows up to \(10^6\) queries, but language limitations are its shortcoming.

If designing problems or organizing competitions yourself, 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 problem's input and produces some output; the input of the second program is related to the first's output (sometimes passed directly as a parameter, sometimes processed by the judge to obtain), and it needs to produce the solution to the problem.

Examples of communication problems include: UOJ #178. New Year's Telegram, #454.【UER #8】Snowball Fight, etc.

Local testing methods vary widely due to different problem settings. Common forms include:

  • Manual input
  • Writing an auxiliary program to convert the first program's output to the second program's input
  • Using bidirectional pipes to connect the standard input/output of the two programs

Due to limited support for communication problems on judging platforms, so far, communication problems are only common in IOI series competitions and a few online platforms like UOJ. It remains an area to be explored.

Function Completion Problems

Function completion problems are problems that require contestants to complete a program. It can be understood as an interactive problem where the contestant's code is given, and auxiliary functions need to be written.

Usually, there are the following forms:

  • Given a program, and informing where the code block to be completed will be embedded.
  • Not giving the program, but using the input information as parameters of the function to be submitted.

This type of problem is more common on LeetCode and PTA - Pintia.

Other Types

Example Problem Quine

Write a program that outputs its own source code.

The code must contain at least ten visible characters.

The problem is classic, but it is difficult to implement on most OJs.

Reference Code

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

1
2
3
4
5
6
// 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

  1. Due to technical and resource limitations, the test cases for a problem often cannot cover all data satisfying the data range. ↩

  2. For interpreted languages like Python, the program is directly interpreted and run by the interpreter. ↩

  3. In fact, the implementation of judging systems is far more complex than this; this is just a general introduction to the judging process. ↩

  4. To be precise, it is generally the program's user-mode time. ↩

  5. Most of these verdicts also apply to other types of problems. ↩

  6. Some test cases may have partial scores. Contestants can receive a certain proportion of points if they complete part of a test case's task, or if their output is correct but not optimal enough. ↩

  7. Most judging systems classify PE status under WA status. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用