Translate from Polygon advices by Sshwy.

如果你准备在 Codeforces 上准备一场比赛(Codeforces Round),那么请将这些建议当作规则,尽可能地遵守。

带星号的建议仅适用于 Codeforces。

Checker, validator and interactor

Checker

  • 默认情况下,使用 std::ncmp.cpp,除非你确实需要使用另一个 checker。
  • 尽可能使用标准 checker(std::)。
  • 对于回答 Yes/No 的问题,使用std::yesno.cpp
  • 对于自定义 checker,不要检查空白字符除非你确实需要(尽可能不使用readLine(),使用readToken()代替)。
  • 不要在 checker 里检查输入文件的合法性(不要使用inf.readSpace()或者inf.readEoln())。
  • 务必检查(正解和参赛者程序)输出的合法性,比如answer = readInt(1,n,"answer")(相当于限定了答案在之间)。
  • 务必使用相同的方式来读入和检查正解与参赛者程序(参考 readAns paradigm),不要忘了在 checker 的最开始初始化所有全局变量。

Tests and generators

  • 不要一直使用“add tests from archive/files”功能。只将你手造的数据来手动上传,其他的请使用生成器(generator)。
  • 不要在 generator scripts 中使用gen > {1-100}的语法。编写只生成一组数据的生成器。
  • 使用可区分的生成器名字。
    • 不好的命名:gen1gen2gen3
    • 不好的命名(传递参数):gen type=1gen type=2gen type=3
    • 好的命名:gen_pathgen_binarygen type=random
  • 把所有可能的小数据都生成(比如),如果他们的总数不是太多。
  • 一般来说一共有组到组数据。
  • 务必构造抵达下界,抵达上界以及范围介于两者之间的数据。
  • * 通常来说,pretests 需要包括:
    • 一组抵达上界的数据(例如最大的);
    • 一组 32 位整数会溢出的数据(如果有);
    • 一些随机小数据;
    • 容易被发现的极端情况数据(如时输出之类的)。如果你故意不想加入一些极端情况数据,可以和 coordinator 商量。
  • * pretests 的数量在~之间(D2A),最多在~之间(D1E)。
  • * 对于每种可能的输出格式有至少一个样例,一共至少两个样例。对于简单的问题最好有多个样例。
  • 务必写样例解释。
  • 务必创建至少一个随机大数据对正解的 stress,把其他人(tester)的正解加到这里来对拍。也创建一个随机小数据的 stress。
  • 不要使用生成器的同一个参数生成两次一样数据(即使只是参数一样,随机种子不同)。

Statements

  • 不要撰写特别长的题面。题面的长度应该恰好能装进文本区在 Polygon 上的初始大小。
  • 使用拼写检查器(以及语法检查器如果你对你的英语表达不确定)。
  • 尽量使用常用的短语。如果你想使用一个在别的问题中出现过的句子,直接复制过来即可。
  • 把每个变量的限制写在它后面的括号中。括号字符不要包含在 TeX 公式中。比如:$n$ ($1 \le n \le 10^5$)
  • 只使用小写字母表示变量。
  • 所有文字元素(单词,空格,标点)不要包含在 TeX 公式中。
    • 错误用法:two integers $x, y$
    • 正确用法:two integers $x$, $y$
  • 所有变量和重要的常量要包含在 TeX 公式中。
    • 错误用法:..., m does not exceed one hundred
    • 正确用法:..., $m$ does not exceed $100$
  • 在 Input 段落中,编写清晰的文段结构使得它能反映读入数据的结构。例如把每一行的读入分段落描述,把同一行的读入放在同一段描述。
  • 对于 HTML 题面(包括 Codeforces),使用 \t{} 来写以单元减号开头的限制。
  • 使用下标或者列表来表示一个序列。
    • 错误用法:a sequence $x_i$
    • 正确用法:a sequence $x$ of length $n$,或者最好使用 a sequence $x_1, x_2, \ldots, x_n$
  • 使用 TeX 撰写题面:
    • 把所有的公式用美元符号($)包裹。
    • 对于破折号,在英文题面中使用~---。例如 word1~--- word2
    • 对于下标使用 $i$-th
    • 另起一个段落时请空一行。
    • 使用意大利斜体 \textit{} 来描述一个定义。使用粗体 \textbf{} 来标注重要的东西。只在少数几个单词上使用他们。如果你想要把若干句话加粗,请重写题面。
    • 在公式中使用\cdot表示乘法符号。
    • 在公式中使用\bmod表示取模符号。
    • 使用\equiv\pmod{}来表示同余方程。
  • 撰写题意清晰的题面。每句话用句点结束。每句话使用大写字母开头。正确使用空格。
    • 错误用法:word1,word2word1(word2)word3word1 ( word2 ) word3
    • 正确用法:word1, word2word1 (word2) word3
  • 不要使用多个单词构成的短语除非实在需要。
  • 如果下面的内容中有可以用在你的题面中的,复制粘贴即可。

Statement Sentence Sample

  1. 第一行包含一个整数)。
    The first line contains a single integer $n$ (1 \le n \le 10^5).
  2. 第二行包含个整数)。
    The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
  3. 接下来的行包含两个数)。

    Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \le x,y \le n$).

    或者

    接下来的行,第行包含两个整数)。

    The $i$-th of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1\le x_i,y_i \le n$).
  4. 你可以任意输出大写或者小写字母。
    You can print each letter in any case (upper or lower).
  5. 如果有多个答案,输出任意一个即可。
    If there are multiple answers, print any.
  6. 如果无解,输出
    If there is no solution, print a single integer $-1$.
  7. 输出答案模

    Output ... modulo $998~244~353$.
    
    Formally, let $M = 998~244~353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q\not \equiv 0 \pmod {M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.
  8. 我们保证,答案一定存在。

    We can show that an answer always exists.

    这个句子应该放在 legend/output 的位置,表示对于所有可能的输入都存在答案。这里没有额外的限制。

  9. 我们保证……

    It is guaranteed that ...

    这句话表示,读入数据被特殊处理过来保证满足条件。它应该放在 legend 和 input 段落中。

  10. 你的答案被视为正确答案仅当答案的绝对精度或者相对精度不超过

    形式化地,设你的答案为,正确答案为。你的答案被接受当且仅当

    Your answer is considered correct if its absolute or relative error does not exceed $10^{-9}$.
    
    Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max{(1,|b|)}} \le 10^{-9}$.
  11. ……,其中表示 按位异或.
    ..., where $\oplus$ denotes the \href{https://en.wikipedia.org/wiki/Bitwise_operation#XOR}{bitwise XOR operation}.
  12. ……,其中表示 按位与.
    ..., where $\&$ denotes the \href{https://en.wikipedia.org/wiki/Bitwise_operation#AND}{bitwise AND operation}.
  13. ……,其中表示 按位或.
    ..., where $|$ denotes the \href{https://en.wikipedia.org/wiki/Bitwise_operation#AND}{bitwise OR operation}.
  14. …, 其中表示最大公约数
    ..., where $\gcd(x,y)$ denotes the \href{https://en.wikipedia.org/wiki/Greatest_common_divisor}{greatest common divisor (GCD)} of integers $x$ and $y$.
  15. 字符串字典序的定义:
    A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:
    \begin{itemize}
    \item $a$ is a prefix of $b$, but $a$ \ne $b$;
    \item in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.
    \end{itemize}
  16. 序列字典序定义:
    A sequence $a$ is lexicographically smaller than a sequence $b$ if and only if one of the following holds:
    \begin{itemize}
    \item $a$ is a prefix of $b$, but $a$ \ne $b$;
    \item in the first position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.
    \end{itemize}
  17. 子序列定义:
    A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements.
  18. 子区间定义:
    A sequence $a$ is a subsegment of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
  19. 子串定义:
    A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
  20. 交互题的注意事项:
    After printing a query do not forget to output end of line and flush the output. Otherwise, you will get \t{Idleness limit exceeded}. To do this, use:
    \begin{itemize}
    \item \t{fflush(stdout)} or \t{cout.flush()} in C++;
    \item \t{System.out.flush()} in Java;
    \item \t{flush(output)} in Pascal;
    \item \t{stdout.flush()} in Python;
    \item see documentation for other languages.
    \end{itemize}
    
    Answer ``\t{...}'' instead of ``\t{...}'' or ```\t{...}'' means that you made an invalid query. Exit immediately after receiving ``\t{...}'' and you will see \t{Wrong answer} verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.
  21. 多测题的格式大纲:
    Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 100$).
    
    Description of the test cases follows.
    
    The first line of each test case contains...
    
    It is guaranteed that the sum of $n$ over all test cases does not exceed...

Solutions

  • 对于每个题目你需要准备:
    • 标准正解(主正解):不包含任何非渐进性(非复杂度层面,比如编译优化)的优化。它的时空应该最多达到时间限制和空间限制的一半。
    • 如果你的题目有可能让 Java 程序运行得很慢(包括但不限于,C++ 程序使用的时间超过时限的或者使用的内存超过MB),那么你需要提供一个 Java 正解。
    • 其他正解:包括至少一个不是原作者写的正解。所有的正解都需要满足时空最多一半。
    • 一个暴力解法:暴力模拟题面的描述,它应该是 AC 或者 TLE 的。给它打一个 Time Limit Exceeded or Correct 的标记(使用while(1)如果需要)。
    • 会 TLE 的程序:给它疯狂加优化,确保它不能过。
  • 对于简单的问题,编写 Python 程序并确保它能在没有优化的情况下通过。
  • 如果存在整数溢出的可能性,写一个 Python 的正解。
  • 如果存在因为溢出导致不通过的可能性,编写在那些可能的地方溢出的程序。确保他们不能通过 pretests。
  • 如果可以,不要卡(卡常,卡时,卡空间)。
  • 如果有一种分类讨论的解法,或者问题的某个部分需要分类讨论,就写一个这样的程序。并且对于各个情况编写一个不能通过的程序,注释标程哪个情况不能通过。确保他们不能通过 pretests。

General

  • * Polygon 的题目中不应该存在警告(warning),除了在题面中写样例。
  • Time Limit Exceeded or Correct 只能在那些卡时的程序上标记。对于一定会 TLE 的程序,使用 Time Limit Exceeded 标记。
  • 题解要写在题面描述下面的文本框中。
  • * 在比赛结束时就应准备好英文题解。