Checker

The checker is usually used to check the answers of participants in cases where there are multiple correct answers, or when more detailed scoring requirements are needed.

Checkers usually need to process three files:

• Input file (inf): Input for the participant's program.
• Output file (ouf): Output of the participant's program.
• Answer file (ans): Usually equivalent to the output of the standard (main correct) program.

Checkers usually need to check two conditions:

• Based on the input file of the test point, determine whether the participant's output is "valid".
• Compare the participant's output with the standard answer and check if they are "equivalent".

Basics

Let's start with a simple example to explain how to write and use the checker.

Problem Description: Given two integers $a$ and $b$ ($-1000 \le a,b \le 1000$), you need to output the sum of $a$ and $b$.

Implementation

First, start with an empty working directory, copy cplib.hpp into the working directory, and then create a file named chk.cpp with the following code:

#include "cplib.hpp"
 
using namespace cplib;
 
CPLIB_REGISTER_CHECKER(chk);
 
void checker_main() {
  auto var_ans = var::i32("ans", -2000, 2000);
 
  int ouf_output = chk.ouf.read(var_ans);
  int ans_output = chk.ans.read(var_ans);
 
  if (ouf_output != ans_output) {
    chk.quit_wa(format("Expected %d, got %d", ans_output, ouf_output));
  }
 
  chk.quit_ac();
}

We will explain each line of this code step by step.

using namespace cplib;

The main functionalities of CPLib are stored in the namespace cplib. Since programs used in Competitive Programming are generally short, to a certain extent, using namespace cplib; greatly optimizes development efficiency.

CPLIB_REGISTER_CHECKER(chk);

The CPLIB_REGISTER_CHECKER(name) macro registers the program as a CPLib checker and saves the state of the checker in a global variable named name (in the code, the name is chk). name can be replaced with any variable name that complies with C++ syntax. However, for readability and conciseness, we will use chk as the global state variable name in this document.

void checker_main() {

checker_main is the main function of a program registered as a CPLib checker, which will be called once CPLib completes initialization, similar to the main function in a regular C++ program. The actual main function will be implemented by CPLib.

  auto var_ans = var::i32("ans", -2000, 2000);

Declare a variable reading template. The type is i32 (32-bit signed integer), and it is named ans. A variable reading template is responsible for specifying how to read a variable of a given type according to the given method.

  int ouf_output = chk.ouf.read(var_ans);
  int ans_output = chk.ans.read(var_ans);

Based on the variable reading template defined just now, read an integer from both the participant's output file and the standard answer file. We don't need to worry about the correctness of the reading format and the range of the integers, as CPLib will automatically perform the above checks.

When the participant's output does not meet the conditions, CPLib will immediately exit the program and report "Wrong Answer", while generating a clear reading stack trace information for reference.

When the standard answer does not meet the conditions, CPLib's behavior is roughly similar to when the participant's output is incorrect. The difference is that in this case, the result returned is "Internal Error". Of course, in actual problems, it is essential to prevent such cases of incorrect standard answers.

  if (ouf_output != ans_output) {
    chk.quit_wa(format("Expected %d, got %d", ans_output, ouf_output));
  }

When it is found that the participant's output and the standard answer are not consistent, the chk.quit_wa function needs to be called to report "Wrong Answer" and exit the program. We recommend providing clear information when using the chk.quit_wa series of functions. Here, the cplib::format function is used to format the error message. This function uses a format similar to printf, making it convenient to format strings.

  chk.quit_ac();

chk.quit_ac reports "Accepted", meaning there are no errors, and then exits the program.

Usage

g++ chk.cpp -o chk -std=c++17

./chk data/0.in data/0.out data/0.ans

Accepted, scores 100.0 of 100.

Advanced

In actual problems encountered in Competitive Programming, the problems are not as simple as A+B. Let's look at a slightly more complex example.

Problem Description: Given an undirected connected simple graph with $n$ nodes ($1 \le n \le 100$) and $m$ edges ($1 \le n \le 100$), where the endpoints of the $i$-th edge are $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), and the edge weight is $w_i$ ($1 \le w_i \le 100$). You need to solve two problems: find the sum of the weights of the shortest path from $1$ to $n$, and output any one shortest path.

Input Format: The first line contains two integers $n$ and $m$. Next, there are $m$ lines, each containing three integers $u_i,v_i,w_i$.

Output Format: The first line outputs an integer $\mathit{sum}$, representing the answer to the first problem. The second line first outputs an integer $\mathit{len}$ in the range $[1,n^2]$, representing the number of nodes traversed in the shortest path. Then it outputs $\mathit{len}$ integers, representing the node numbers traversed in the shortest path (including the starting node $1$ and the ending node $n$).

When writing a more complex checker, it is not recommended to include all the logic in checker_main. Below is a more readable and maintainable implementation of a checker:

#include <map>
#include <utility>
#include <vector>
 
#include "cplib.hpp"
 
using namespace cplib;
 
CPLIB_REGISTER_CHECKER(chk);
 
struct Edge {
  int u, v, w;
 
  static Edge read(var::Reader& in) {
    auto [u, v, w] = in(var::i32("u"), var::i32("v"), var::i32("w"));
    return {u, v, w};
  }
};
 
struct Input {
  int n, m;
  std::map<std::pair<int, int>, int> graph;
 
  static Input read(var::Reader& in) {
    auto [n, m] = in(var::i32("n"), var::i32("m"));
    auto edges = in.read(var::ExtVar<Edge>("edges") * m);
 
    std::map<std::pair<int, int>, int> graph;
    for (auto [u, v, w] : edges) {
      graph[{u, v}] = w;
      graph[{v, u}] = w;
    }
 
    return {n, m, graph};
  }
};
 
struct Output {
  int sum, len;
  std::vector<int> plan;
 
  static Output read(var::Reader& in, const Input& input) {
    auto [sum, len] = in(var::i32("sum", 0, std::nullopt), var::i32("len", 1, std::nullopt));
    auto plan = in.read(var::i32("plan", 1, input.n) * len);
 
    if (plan.front() != 1) in.fail("Plan should begin with 1");
    if (plan.back() != input.n) in.fail("Plan should end with n");
    int result_sum = 0;
    for (int i = 1; i < (int)plan.size(); ++i) {
      if (!input.graph.count({plan[i - 1], plan[i]}))
        in.fail(format("Edge %d <-> %d does not exist", plan[i - 1], plan[i]));
      result_sum += input.graph.at({plan[i - 1], plan[i]});
    }
    if (result_sum != sum) in.fail("Plan and shortest path length do not match");
 
    return {sum, len, plan};
  }
 
  static void check(const Output& expected, const Output& result) {
    if (result.sum > expected.sum)
      chk.quit_wa(format("Wrong sum, expected %d, got %d", expected.sum, result.sum));
 
    if (result.sum < expected.sum)
      panic(format("Contestant answers are better than standard answers, expected %d, got %d",
                   expected.sum, result.sum));
  }
};
 
void checker_main() {
  auto input = chk.inf.read(var::ExtVar<Input>("input"));
 
  auto output = var::ExtVar<Output>("output", input);
  auto ouf_output = chk.ouf.read(output);
  auto ans_output = chk.ans.read(output);
 
  Output::check(ans_output, ouf_output);
  chk.quit_ac();
}

This example demonstrates how to use variable reading templates for custom types.

First, define the structure Edge to describe an edge. The simplest way to create a variable reading template for reading Edge is to use cplib::var::ExtVar. Before using it, you need to write a public static method named read for the Edge structure. The first parameter type of this method must be cplib::var::Reader&: that is, a reference to the type corresponding to the objects chk.inf, chk.ouf, chk.ans introduced in the previous section. Subsequent parameters can be defined arbitrarily.

The code from the previous section shows the .read method of the cplib::var::Reader type, and the implementation of Edge::read uses its operator() operator overloading. This operator sequentially calls .read method with instances of multiple variable reading templates as parameters and packs all the results into a std::tuple in order. When reading multiple variables with no dependency relationship, using operator() can make the code shorter.

CPLib provides cplib::var::Vec for creating variable reading templates for std::vector, and also overloads operator*(size_t) for cplib::var::Var. Using a syntax similar to the one in the Input::read method in the code, you can quickly create a cplib::var::Vec by multiplying any object of a subclass of cplib::var::Var with an integer.

After writing Edge::read, we can use cplib::var::ExtVar<Edge> to create a variable reading template for reading an Edge type. When instantiating a cplib::var::ExtVar<T> for a target reading type T, if the number of parameters for T::read is greater than or equal to $2$, you need to pass arguments to the constructor of cplib::var::ExtVar<T> based on the second to last parameter of T::read. For types like the Edge type in this example, whose Edge::read method has only one parameter, the constructor does not need to pass any arguments.

When it is possible to check whether the participant's output is "valid" before reading all the participant's output, we recommend that you write the logic for checking "validity" in the corresponding type's read method, as shown in the implementation of Output::read in this example. If there is a case of reading that does not meet the requirements of the problem, the in.fail(message) function should be used to report the error. This function generates an error report based on the input parameter message and the current reading stack trace, and exits the program. Different input streams corresponding to Reader determine different types of error reports. For example, calling fail on chk.inf and chk.ans streams in the checker will result in an error type of "Internal Error", while on the chk.ouf stream, it will result in "Wrong Answer".

After checking for "validity", the next step is to check for the "equivalence" between the participant's output and the standard answer. We recommend that you implement a static check(expected, result) method on each type that needs to be compared, and call the check method of the outermost type Output in checker_main. Finally, after all the checks pass in check, call chk.quit_ac.

Suggestions

In summary, when writing more complex checkers, we recommend the following suggestions:

• Use custom types and cplib::var::ExtVar to encapsulate your code, instead of using basic type reading entirely.
• When checking the "validity" of T, consider implementing it in T::read first. Next, consider separately checking the result parameter in T::check.
• When checking the "equivalence" of T, consider implementing it in T::check, and only call the check method of the outermost variable in checker_main.
• For types that only appear in the test point input file, it is not necessary to implement "validity" checks for them: you should do this in the validator.