Problem Setting

Preparation Before Setting Problems

Have a Certain Level

On the one hand, it is difficult for someone to set problems whose difficulty exceeds their own level; a certain level of OI helps one come up with better ideas and excellent solutions. On the other hand, OI level represents OI experience to some extent, and contestants who have seen more problems will also have their own views on what makes a "good problem."

Have a Serious and Responsible Attitude

Problems are set for other people to solve. Compared with showing off oneself, the purpose is more to serve others. Algorithm competitions are competitions among contestants, not contests between problem setters and solvers. Therefore, a problem should not aim to stump contestants (of course, appropriate anti-AC measures and good discrimination are also very important), but should allow contestants to gain something from the contest. It is very important to spend enough time and energy learning how to set problems and to set them seriously and responsibly.

Be Prepared to Spend a Great Deal of Time

If you want to set problems seriously, you will inevitably have to spend a great deal of time. Without being mentally prepared, you may prepare the contest in a hurry and fail to meet the required quality, or later regret not having spent that time studying. However, setting problems can also bring many wonderful memories. If you are genuinely interested in problem setting and have made sufficient mental preparations, what you gain from setting problems can make up for the time spent.

Read This Article Carefully

This article introduces the entire problem-setting process from two aspects: how to set problems and how to set them well. Anyone who wants to set problems will certainly benefit greatly from reading it carefully.

Problem Content

When setting a problem, the idea—that is, the essence of the problem—is its soul and the first step in setting it.

Sources of Ideas

  1. Be inspired by existing problems (but do not copy them or strengthen them meaninglessly, such as moving a sequence problem to a cactus).
  2. Be inspired by knowledge you have learned (but do not put together unrelated knowledge points).
  3. Be inspired by life or games (but be careful not to turn a game into a large simulation).
  4. Think of a problem for no particular reason.

What Makes an Idea Bad

About Original Problems

Original problems can roughly be divided into three types: completely identical, nearly identical, and having the same solution.

  • Completely identical: the AC code for one problem can AC the other problem.
  • Nearly identical: modifying the AC code for one problem into the AC code for the other can be done by someone who does not know the problem.
  • Same solution: the core idea and approach are the same, but the code implementation and less important details differ.

These three types of original problems form an inclusion relationship from bottom to top.

The following situations should not occur:

  1. Setting an original problem when you know that a nearly identical original problem exists.
  2. Setting a nearly identical original problem because you did not search with a search engine and therefore did not know the original problem existed.
  3. Setting an original problem when an original problem with the same solution is widely known (such as an original NOIP or NOI problem).
  4. Including an original problem with the same solution as a non-giveaway problem in a selective examination.

The following situations are best avoided:

  1. Setting an original problem when you know that an original problem with at least the same solution exists.
  2. Setting an original problem with the same solution because you did not search with a search engine and therefore did not know the original problem existed.
  3. Setting a nearly identical original problem under any circumstances.

Exceptions where the requirements can be relaxed:

  1. In-school mock contests.
  2. Mock contests intended for topic-specific training.
  3. Low-difficulty contests or problems positioned as giveaways.

About "Monster Problems"

The concept of a "monster problem" is very vague and subjective. Here, we quote some discussions by predecessors and add some of our own understanding. This is a very open topic, and everyone is welcome to share their views.

A good problem should not be two problems put together; a good problem should have its own idea—and it should highlight this idea without excessive packaging.

A good problem should be novel. A truly good problem should be a good problem that makes people come up with new good problems.

——vfk, "The Source and Development of the UOJ Spirit"

Example: "XR-1" The Conan Family. The first and second parts of the solution are completely disconnected: the first half is "Template" Suffix Sorting on a Tree, while the second half is a classic tree problem. Even if arbitrary vertex weights are assigned to the tree, the second part can still be solved; the two parts are unrelated.

A class of OI problems is mainly mathematical. Both the problem statement and the approach have the characteristics of mathematical problems, and the solution contains no algorithm-related knowledge points. This class of OI problems is collectively called pure mathematics problems.

——Wang Tianyi, "On the Harm of Off-topic Problems"

Classic example: "NOIP2017" Xiaokai's Confusion

The difference between mathematical problems in OI and other mathematical problems, which also reflects an essential characteristic of OI, is that mathematical problems in OI often focus not on what the answer is, but on how to speed up its computation. If a problem focuses on "how to calculate" rather than "how to calculate quickly," then such a mathematical problem is generally unsuitable for OI.

Some off-topic problems involve university physics, causing contestants to become at a loss when facing physical knowledge they have never encountered, creating a barrier in their knowledge.

——Wang Tianyi, "On the Harm of Off-topic Problems"

Classic example: "Tsinghua Training 2015" Polygon Goes into the Sea

Not only physics, OI problems should not involve too much knowledge from other disciplines. If such knowledge is involved, a detailed explanation should be provided, and it should not become a major obstacle to solving the problem.

A good problem, regardless of its difficulty, should have its own thinking difficulty and require contestants to think and discover some properties.

The code of a good problem may be long, but it must not become long by forcibly nesting or adding conditions. It should be naturally long, making people feel that the code for this problem should be that long.

——Wang Tianyi, "On the Harm of Off-topic Problems"

Classic examples: "SDOI2010" Piggy Kill, "Training Team Mutual Test 2015" Future Program · Revised

In ordinary OI contests, thinking difficulty should occupy the main part. Of course, engineering problems such as Day 2+ of THUWC/THUSC also have a reason to exist—after all, the purpose of the experience camp includes not only examining contestants' algorithm-design ability, but also engineering code and documentation skills connected with university study. In ordinary OI contests, however, more emphasis should still be placed on algorithm design and thinking ability.

Statement

Write Formulas in LaTeX

There are many LaTeX tutorials online, such as:

Pay attention to the formatting requirements of LaTeX formulas when using them.

Problem Background

The problem background should preferably be as short as possible. When the background is long, it should be separated from the problem description.

It is absolutely necessary to avoid the problem background seriously affecting the understanding of the problem.

When necessary, a problem description combined with the background and a concise problem description can be provided in two versions.

Problem Description

In short, the problem description needs to be clear and easy to understand.

Every definition in the statement that may not be understood should be explained; concepts should not appear out of nowhere without definitions. For example, in CF1172D Nauuo and Portals, you must explain in the statement what a "portal" is.

Every concept involved in the statement should be described using a single term. For example, do not say "fee" in one place and "cost" in another.

Words with meanings different from their original or common meanings should not be used without explanation. For example, do not use "path" to refer to an edge without explanation.

You need to ensure that your statement is not self-contradictory. For example, in CF1173A Nauuo and Votes, "?" is not treated as a kind of "result" because "?" means "there are more than one possible results."

You need to ensure that your statement cannot be incorrectly interpreted and then made internally consistent, even if such an interpretation is counterintuitive and no one would normally think of it. For example, in CF1172D Nauuo and Portals, the definitions of "walk into" and "teleport" are carefully distinguished to prevent the interpretation that one can reach another portal through a portal, and arriving at a portal causes teleportation, resulting in repeated bouncing back and forth.

Reading the problem description in order should make every sentence understandable, and the task and requirements should be clear. At least in the immediately following paragraph, any questions should be answered, rather than requiring the reader to wait several paragraphs, read the input/output format, or even guess the meaning from the samples. For example, in "GuOJ Round #1" Cirno's Snow Banquet, the objective of the problem—"the maximum amount of water that Lake of Mist can ultimately receive"—first appears in the output format. Moreover, the sentence "Reimu can of course quickly calculate the total cost of cleaning all the streams" is misleading, making the statement easier to misread. This is undesirable; the objective should be explained in the problem description itself. (This example also has the problem of the background seriously affecting the understanding of the problem.) The same mistake appears in CF1423(4)N Bubblesquare Tokens, where the objective "friend pairs and number of tokens each of them gets on behalf of their friendship" first appears in the output format.

Input and Output Format

The input and output formats only need to be clearly complete; there are no rigid requirements. Personally, I suggest referring to Codeforces problems when writing the input and output formats. For details, see Instructions for Codeforces Problem Setters.

For contestants' convenience, the input and output formats should preferably explain the exact meaning of every variable, unless the meaning is too long to explain in one sentence (in which case one may say "see the problem description for the meaning").

Special attention is needed when the output contains decimals: try to use SPJ to limit the size of the error instead of requiring "printing x decimal places."

The precision requirement of "printing x decimal places" may be infinite. For example, if three decimal places are required and the actual answer is 0.00150.0015, any error, however small, that makes the computed answer less than 0.00150.0015 will cause a wrong answer; even a computed answer of 0.00149999⋯0.00149999\cdots will be judged incorrect.

If SPJ cannot be used, ensure that the precision requirement is finite. For example, ask contestants to output the answer rounded to three decimal places. Let the standard answer be ansans; the data guarantees that any value satisfying ∣x−ans∣max⁡(1,ans)<10−9\frac{|x-ans|}{\max(1,ans)}<10^{-9}, denoted by xx, has the same rounded result as ansans.

Some sentences that can be used as references:

The first line of the input contains three positive integers $n$, $m$, and $k$ ($1\le n,m\le 2\cdot 10^5$, $1\le k\le 100$) — $n$ denotes the length of the sequence, $m$ denotes the number of operations, and the meaning of $k$ can be found in the problem description.

The second line of the input contains $n$ non-negative integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — the sequence given in the problem.

Of the next $m$ lines, the $i$-th line contains two positive integers $l_i$ and $r_i$ ($1\le l_i\le r_i\le n$), indicating that the $i$-th operation is performed on the interval $[l_i,r_i]$.

Each of the next $n-1$ lines contains two positive integers $u$ and $v$ ($1\le u,v\le n$), indicating that $u$ and $v$ are connected by an edge.

The given edges are guaranteed to form a tree.

The only line of the input contains a non-empty string consisting of lowercase English letters, whose length does not exceed $10^6$.

The second line of the input contains a real number $x$ with at most three digits after the decimal point ($-10^6\le x\le 10^6$); see the problem description for its meaning.

The output contains a real number. It is considered correct if the absolute error or relative error between your output and the standard answer is less than $10^{-6}$.

The second line of the output contains $n$ positive integers, representing a solution you construct — the $i$-th number is the index of the $i$-th card you play.

If there are multiple valid answers, output any one of them.
Generating Input Data with a Random Number Generator in Contestant Code

Because input data may be too large and reading it may take too long, some problems require contestants to generate data in their code through a given generator instead of reading it through standard input or from a file.

This approach needs to be considered carefully because it has many disadvantages:

  • It may introduce randomness in the data that is unnecessary for the intended solution, or make constructing data difficult.
  • It may increase the difficulty of understanding the input format.
  • If the random number generator is poorly encapsulated, understanding how to use the generator itself may be difficult.
  • If contestants do not use the language recommended by the problem setter, they may need to write a data generator themselves.

This approach is generally used to prevent input from taking too long to read. One possible alternative is to provide a sufficiently fast input/output optimization template, to ensure that everyone's input time is as consistent as possible; in this way, even if reading takes a long time, it will not affect differences in running time between languages. Another solution is to package the problem as a function-call-style (rather than IO-style) interactive problem. Even if there is no interaction during the algorithm, an interactive problem can unify input time; IOI adopts the approach that all problems are interactive. However, both solutions limit the languages contestants can use, and problem setters must manually support every permitted language.

Returning to the source of the problem, one can also consider whether excessively large input data is necessary, whether the goal can be achieved with smaller input data, and whether it is necessary to eliminate approaches whose complexity is only slightly worse than that of the intended solution.

Data Constraints

According to Codeforces requirements, data constraints should be written in the input format, but in China, they are often written at the end of the problem.

The most common mistake in data constraints is incompleteness. Every number and every string in the input should have a clear specification. The input/output format examples above include some correct ways to write data constraints.

Common omissions in data constraints:

  1. The "integer" in "integer".
  2. The statement only says that something is an "integer" rather than a "positive integer," and the data constraints give only an upper bound and no lower bound.
  3. The character set of a string.
  4. The number of digits after the decimal point of a real number.
  5. The range of some variable.

You need to ensure that the standard solution can pass any data set satisfying the data constraints stated in the problem.

About "Guaranteeing Randomly Generated Data"

Some problems state that "the data is guaranteed to be randomly generated." Often, this restriction is not the optimal solution, because "randomly generated" does not clearly limit the data and makes it difficult to determine the exact data constraints or provide hack data.

Generally, "the data is guaranteed to be randomly generated" can be replaced by a data property required by the solution. For example, randomly generating a tree can often be replaced by restricting the height of the tree.

If random generation must be guaranteed, specify the exact random-generation procedure. For example, state whether a tree is generated by randomly selecting a parent or by randomly generating a Prüfer sequence.

Note that nondeterministic algorithms and algorithms that depend on data randomness are different. The former have a high probability of obtaining the intended solution for any data, while the latter obtain the intended solution for most data but cannot do so for certain specific data.

Samples

Samples should have sufficient strength to catch simple errors. Contestants who misunderstand the problem should be able to discover their misunderstanding through the samples.

For problems with multiple operations, every type of operation should appear in the samples.

For problems with multiple possible outputs (such as CF1173A Nauuo and Votes), every output type should appear in the samples. An exception is a problem where a solution is in fact always possible but contestants are asked to determine whether a solution exists.

Sample Explanation

The more complex and difficult to understand the problem description is, the more detailed the sample explanation should be.

The simpler the problem, the more detailed the sample explanation should be.

A detailed sample explanation may optionally be accompanied by images.

Large samples may have no sample explanation.

For the sake of people with color-vision deficiencies, it is best not to make color essential to understanding the sample explanation. Colored images may be used to improve the appearance of the explanation, but if color must convey necessary information, it is best not to use red and yellow or red and green together.

Time Limit, Memory Limit, and Partial Scores

The purpose of time and memory limits is to eliminate approaches with incorrect complexity. (Of course, they also prevent evaluation from taking too long; for example, even an interactive problem with only a limit on the number of interactions and no time-complexity limit has a time limit.)

Therefore, in principle, the time limit should be as large as possible without allowing incorrect approaches to pass.

In general, the time limit should satisfy the following requirements:

  1. It should be at least twice the time used by the standard solution in the worst case.
  2. If Java is allowed in the contest, Java should be able to pass.
  3. It should not allow incorrect approaches to pass (except when they cannot realistically be eliminated or a particular wrong solution is intentionally allowed).

To eliminate wrong solutions while allowing approaches with large constants to pass, one can generally increase both the data constraints and the time limit. However, be careful: sometimes the intended solution has a huge increase in its constant due to cache or other mysterious issues when the data constraints increase. In that case, increasing the data constraints may not increase the difference in running time between the intended solution and the wrong solution.

In contests with partial scores, one can also use data with varying scales and smaller data constraints to prevent relatively good wrong solutions and intended solutions with large constants from passing, while allowing them to obtain relatively high partial scores.

It is worth noting that when the data size is less than 5⋅1055\cdot 10^5, one should consider whether the solution can pass by using an instruction set.

In general, the memory limit should be sufficiently large, unless the approach with better space complexity is genuinely clever and worth eliminating approaches with high space complexity. In this case, consider setting a relatively loose memory limit for partial scores. Note that if you do not want to eliminate approaches with high memory consumption, data-structure problems generally need a relatively large memory limit.

A good problem should have its selection property and sufficient discrimination. It should have at least four levels of partial scores, so that beginners can obtain some points and experts can demonstrate their strength.

——vfk, "The Source and Development of the UOJ Spirit"

Partial scores are generally divided into two types: smaller data constraints and special properties.

Smaller data constraints should generally have multiple levels. Even if you cannot think of an approach with a certain complexity, you can consider giving one level of points for that complexity. Generally, to avoid constant-factor issues, one level of partial scores can be set with the maximum data divided by two.

"Data with varying scales" is best replaced with multiple levels of partial scores.

The setup of partial scores for special properties depends on the particular problem. Ideally, a special-property subtask should guide contestants toward thinking about the intended solution. Unlike partial scores for smaller data constraints, if you do not know an approach targeting a certain special property, it is best not to give that special property a level of partial scores. For example, many people complained during the explanation of "CTS2019" Random Cuboid that the k=1k=1 partial-score level hindered thinking about the intended solution.

If the way points are awarded differs from the default (for example, subtasks are bound in an ordinary OI-format contest), it must be stated in the problem statement.

It is not recommended to use statements such as "XX percent of the data satisfies XX," especially when there are multiple variables in the data constraints. For example, "30%30\% of the data satisfies n≤1000n \le 1000" and "40%40\% of the data satisfies m≤100m \le 100" may describe a property of 70%70\% of the data, or may describe a property of only 40%40\% of the data. Generally, a subtask or a data-constraint table is a better choice.

Generating Data

Data generation is a necessary step in problem setting and is also essential for differential testing. Mastering some data-generation techniques makes data generation easier and produces stronger data.

Generating Random Data

Generating Random Numbers

Please refer to the random functions page.

It is worth emphasizing that when generating values from a range larger than the values returned by a random function, do not use expressions such as rand() * rand(). The random numbers generated this way are extremely non-uniform.

In addition, when setting problems, it is recommended to use testlib to generate data. This ensures that the same seed generates the same random numbers on different platforms, and the seed is automatically generated according to the command-line arguments.

Generating Random Permutations

You can use the STL function std::shuffle, in the form std::shuffle(a, a + n, rng), where rng is a random-number generator, such as std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count()).

Do not use std::random_shuffle; it was deprecated in C++14 and removed in C++17.

Generating Random Intervals

A common incorrect method is to randomly generate the left endpoint in [1,n][1,n] and call it ll, then randomly generate the right endpoint in [l,n][l, n] and call it rr. This makes the generated intervals biased toward the right.

A relatively correct method (the recommended method) is to randomly generate two numbers in [1,n][1, n], and use the smaller as the left endpoint and the larger as the right endpoint.

The truly uniform method is to generate a random number in [0,n][0, n] and call it xx. If x=0x = 0, generate another random number in [1,n][1, n] and call it yy, and let the interval be [y,y][y, y]; otherwise, generate the interval using the "relatively correct method."

Generating Random Trees

A common method is to randomly choose a parent for every node from 2∼n2\sim n, calling the node ii, from [1,i−1][1,i-1]. The resulting tree is not uniformly random and has expected height O(log⁡n)O(\log n).

Another random method is to randomly choose from [i⋅low,i⋅high][i\cdot low, i\cdot high] the parent of ii. With suitable values of lowlow and highhigh, trees with relatively high strength can be generated.

The truly uniform random method uses a Prüfer sequence: first generate a random Prüfer sequence, then generate a tree from the sequence. This gives the tree expected height O(n)O(\sqrt n).

In addition, one can randomly generate a permutation to renumber the vertices or shuffle the order of the edges.

Constructing Data

Problems Related to Intervals

Common constructions include intervals with particularly small lengths (in particular, all singletons) and particularly large lengths (in particular, the entire sequence).

Problems Requiring Factorization

To maximize the number of prime factors counted with multiplicity: a power of 22.

To maximize the number of distinct prime factors: the product of several smallest primes.

To maximize the number of divisors: refer to sequence A002182 on OEIS.

Problems Requiring Greatest Common Divisors

Make the two numbers whose greatest common divisor is needed be adjacent terms of the Fibonacci sequence; this can make the Euclidean algorithm reach its worst-case time complexity.

Tree Problems

Common constructions:

  • A chain
  • A star
  • A complete binary tree
  • Replace every vertex of a complete binary tree with a chain of length n\sqrt n
  • Attach a chain to a star
  • Attach some single vertices to a chain
  • A tree of height dd with d>1d>1, whose root has two children; the left subtree is a chain of length d−1d-1, and the right subtree is a tree of height d−1d-1 constructed in the same way.

If you are not in a contest, you can also use Tree-Generator to generate various trees.

Generating Data in Batches

The author recommends using command-line arguments together with bat/sh scripts.

For example:

gen.cpp:

#include "testlib.h"

using namespace std;

int n, m, k;
vector<int> p;

int main(int argc, char* argv[]) {
  registerGen(argc, argv, 1);

  int i;

  n = atoi(argv[1]);
  m = atoi(argv[2]);
  k = rnd.next(1, n);

  for (i = 1; i <= n; ++i) p.push_back(i);

  shuffle(p.begin(), p.end());
  // Use rnd.next() to perform the shuffle

  printf("%d %d %d\n", n, m, k);
  for (i = 0; i < n; ++i) {
    printf("%d%c", p[i], " \n"[i == n - 1]);
    // Treat a string as an array: spaces in the middle and a newline at the end is a common trick when generating data
  }

  return 0;
}

gen_scripts.bat:

gen 10 10 > 1.in
gen 1 1 > 2.in
gen 100 200 > 3.in
gen 2000 1000 > 4.in
gen 100000 100000 > 5.in

The advantage is that for different data, you only need to write one generator, and you can conveniently modify the parameters of a particular test point.

Requirements for Data Generation

The data should include the minimum and maximum values of every parameter.

The data should include various corner cases.

When using subtasks, the data (including input and output) should preferably cover every range of the value domain, rather than only its maximum value.

To prevent special-case handling for a particular construction from passing, different constructions can be combined in one test point, or most of the data can be constructed data mixed with a small amount of random data.

The data should contain various constructions, even if you do not know what wrong solution would fail on that construction. (This should be handled appropriately in a test-point-scored contest.)

Of course, if you know a wrong solution with a correctness issue that a normal person could think of and write, try to eliminate it as much as possible.

It is especially important to note that if integer overflow is possible, you must eliminate approaches that overflow. In a contest with partial scores, people who do not use long long should not receive the same or even fewer points than brute force.

If there are pretests, they should be as strong as possible (and as few as possible). In other words, pretests should contain all known counterexamples to wrong solutions using as few data groups as possible.

If you want a small number rather than no FSTs, you should still ensure that the pretests are strong, because in an actual contest there may be unexpected errors, resulting in far more FSTs than expected.

Data Format

Here are some data-format requirements for common situations, which can serve as a reference:

  1. Use the line-break format of the test environment.
  2. The last line of the file ends with a newline character; that is, the last character of the entire file must be \n.
  3. There are no whitespace characters at the beginning or end of any line.
  4. There is at most one consecutive space.

Data generated in a Windows environment usually uses \r\n line breaks, while mainstream judging systems run on Linux and use \n. If Windows-format line breaks are read on Linux, reading strings may handle line breaks incorrectly, causing program behavior to differ between environments. If output generated on Linux is compared with standard output generated on Windows, the comparison may differ because the line-break formats differ. To keep program behavior consistent, all data must use the line-break format of the environment in which the program runs.

Linux-format data can generally be generated in the following ways:

  1. Generate the data directly in a Linux environment.
  2. Use the dos2unix tool to convert input and output files; this tool is included in toolchains such as Cygwin and MinGW.
  3. Open the output file in binary mode and use \n line breaks.
  4. Refer to the dos2unix.cpp code on this page and write the tool yourself.

Special Judge

SPJ Writing Tutorial

Output-solution problems and floating-point-output problems are two common types that need an SPJ; other problems may also need an SPJ depending on the situation. On Codeforces, all problems must use a testlib-based checker. For example, when a problem requires outputting several integers, the ncmp checker included with testlib allows contestants to output arbitrary whitespace (spaces or newlines).

Checkers are generally written using testlib. Since a checker must handle all kinds of invalid output, it needs to be extremely robust; writing a good checker without testlib is difficult.

When writing a checker, pay attention to the following two points:

  1. You need to handle all kinds of invalid output, so check whether every input variable is within its valid range (readInt(minvalue, maxvalue)). For example, when reading a variable that will be used as an array index during checking, its range must be checked; otherwise, an out-of-bounds access may occur, which sometimes causes RE and sometimes may be judged AC.
  2. In principle, a checker should not check whitespace (that is, it should not use readSpace(), readEoln(), or readEof()). It is worth mentioning that testlib automatically checks for extra output.

Editorial

The purpose of an editorial is to make the problem understandable to the people expected to participate in the contest. Therefore, the required level of detail for an official editorial is higher than that of an ordinary editorial.

About Partial Scores

For problems with partial scores, the editorial may also discuss the approaches for obtaining partial scores.

About Knowledge Points

The knowledge points used in the solution should be clearly indicated. For knowledge points whose difficulty is comparable to that of the problem, it is best to provide material for learning them, such as a blog post.

About Definitions

Concepts should not appear out of nowhere in an editorial.

For example, a DP editorial should clearly explain the definition of the state.

About Details

If a specific implementation detail is relatively clever, it is best to write it down; otherwise, "see the code" is also acceptable. If you say "see the code," it is best to add some comments to the code.

Standard Solution

Redundant parts should preferably be removed from the standard solution. For example, some editorials retain a complete define template (to speed up solving, containing many defines and common functions, often used in online contests such as Codeforces), although a large part of it is unused. This is undesirable.

If the implementation includes details not explained thoroughly in the editorial, an appropriate number of comments should preferably be added.

Contests

The Difficulty in Contest Announcements Should Be Accurate

Remember that authors tend to underestimate the difficulty of their problems.

——Reminder on the Codeforces PROPOSE A PROBLEM page

Problem setters are likely to estimate difficulty incorrectly. Therefore, if the contest announcement includes the contest difficulty, it should be considered carefully. It is best to have someone test and evaluate the problems in advance.

Distributing Problem Difficulties

In domestic-OI-style mock contests, it is often sufficient for the overall difficulty of the three problems to match the contest difficulty.

In online contests such as CF/ATC, difficulty should be made as increasing as possible (although this often cannot truly be achieved because of inaccurate difficulty estimates), and large difficulty gaps should be avoided as much as possible. A problem can be split into an easy and a hard problem (two subtasks) to reduce a difficulty gap, but splitting into subtasks requires careful consideration, and many people dislike subtasks in the CF format (Are subtasks evil?), for reasons including but not limited to:

  • Due to the contest format, solving the easy version first and then the hard version may result in less penalty time and a higher total score.
  • The scores assigned to subtasks are often not proportional to problem difficulty.
  • In many cases, the easy version is not a qualified problem (it is uninteresting).
  • In many cases, the solution to the easy version does not help with thinking about the intended solution to the hard version.

Distributing Problem Knowledge Points

A contest should cover as broad a range of knowledge points as possible (except for topic-specific training contests, of course).

Classic counterexample: CTS2019 covered many knowledge points, including dynamic programming, expectation, combinatorial counting, the inclusion-exclusion principle, and polynomials.

I have to choose six problems from five; I cannot help it.

——The reason given by the CTS2019 problem setters, who did not receive enough problem submissions

Problem-Setting Platforms

Polygon

Polygon is a very powerful platform for setting problems collaboratively. It can be the preferred choice for collaborative problem setting on any website (exporting through the package function to websites that do not support Polygon), and it is also a good choice for setting problems alone (especially on different devices). See Introduction to Polygon for instructions.

Codeforces

Codeforces is the world's most famous algorithm-contest website. Its problem quality is relatively high, making it very suitable for problem setters with some experience who want to further improve their problem-setting skills and create a set of high-quality problems. Its disadvantage is that review is slow (usually taking several months), but you can also begin preparing the problems during the review period (although there is a risk that preparation will be wasted if a problem is rejected).

Qualifications for Setting Problems

  • Blue and have participated in at least 25 rated contests;
  • Purple and have participated in at least 15 rated contests;
  • Orange and have participated in at least 5 rated contests;
  • Red or black-red.

Submitting a Contest Proposal

Once you have the qualifications to set problems, you can see the Propose a contest/problems button in the sidebar.

After entering, first write a contest proposal (in PROPOSE A CONTEST), then write a problem proposal and add it to the contest.

After deciding on the problems, you can set the contest proposal to open to review (submit it for review).

Preparing Problems on Polygon

Refer to Introduction to Polygon.

Contacting the Management

There are two purposes for contacting the management:

  1. Speed up the review.
  2. The management will provide suggestions and help after the preparation stage begins.

The formal contact method is to submit an application as a proposal in the proposal system; after the management begins reviewing it, discussion takes place in comments below the proposal.

In practice, if a proposal remains unreviewed for a long time, you may consider sending a private message to the management (although CF says "Don't send private messages or emails to coordinators," 300iq said in a comment that private messages are acceptable).

Comet OJ

Comet OJ link

No longer active (as of November 2021; the last contest was in January 2020).

Problem-setting application: https://info.cometoj.com/contests/Questionnaire_IssuerInfo/

CodeChef

An Indian algorithm-contest platform with three formats: the 10-day Long Challenge with challenges, the 2.5-hour ICPC-style Cook-Off, and the 3-hour IOI-style LunchTime.

Problem-setting FAQ: https://www.codechef.com/wiki/faq-problem-setters

Problem-setting guide: https://www.codechef.com/problemsetting

AtCoder

An algorithm-contest platform from Japan. Contact for problem setting: contest@atcoder.jp.

UOJ & LOJ

Domestic OJs with relatively few contests.

Luogu

Staff participating in problem setting need to have a certain award-certification level. After creating a contest, the person in charge submits an application through the ticket system.

Open-contest specifications: https://help.luogu.com.cn/rules/academic/opencontest-standard

References

  1. vfk, "The Source and Development of the UOJ Spirit"

  2. Wang Tianyi, "On the Harm of Off-topic Problems"

  3. Instructions for Codeforces Problem Setters (image version accessible in China)

  4. Self-Cultivation of Codeforces Problem Setters

This article was reproduced and modified and supplemented from ouuan's problem-setting guidelines by the original author.

Previous section
012 Common Tricks

This content comes from OI Wiki: Problem Setting. See the original for authors and revision history. AIOJ has adapted the formatting, in-site links, and resource paths.

Content is shared under CC BY-SA 4.0 and SATA license; additional terms are governed by the original notice. Thanks to the OI Wiki authors and contributors; per the SATA terms, please visit the OI Wiki repository and star it to show your support.