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" (i.e., conforms to the output format and constraints).
• Compare the participant's output with the standard answer and check if they are "equivalent" (i.e., logically correct according to problem rules).

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;
 
// Define the Input struct to read problem-specific inputs (A and B for A+B problem)
struct Input {
  int a, b;
 
  static Input read(var::Reader& in) {
    // Read integer 'a' within range [-1000, 1000]
    auto a = in.read(var::i32("a", -1000, 1000));
    // Read integer 'b' within range [-1000, 1000]
    auto b = in.read(var::i32("b", -1000, 1000));
    return {a, b};
  }
};
 
// Define the Output struct to read the answer and evaluate it
struct Output {
  int ans;
 
  // Static read method to parse participant/jury output
  // It receives a var::Reader and the Input struct for context if needed.
  static Output read(var::Reader& in, const Input&) {
    // Read integer 'ans' within range [-2000, 2000]
    auto ans = in.read(var::i32("ans", -2000, 2000));
    return {ans};
  }
 
  // Static evaluate method to compare participant's output with jury's output
  // It receives an evaluate::Evaluator, participant's output (pans),
  // jury's output (jans), and the original Input.
  static evaluate::Result evaluate(evaluate::Evaluator& ev, const Output& pans, const Output& jans,
                                   const Input&) {
    // Use ev.eq to compare the 'ans' field.
    // If pans.ans == jans.ans, it contributes to AC. Otherwise, it marks WA.
    auto res = evaluate::Result::ac();
    res &= ev.eq("ans", pans.ans, jans.ans);
    return res;
  }
};
 
// Register the checker with CPLib, specifying the Input and Output structs.
// This macro sets up the main checker logic behind the scenes.
CPLIB_REGISTER_CHECKER(chk, Input, Output);

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.

struct Input { /* ... */ };

The Input struct encapsulates all data read from the problem's input file. It must contain a static method read that takes a cplib::var::Reader& as its first parameter and returns an instance of Input. This method is responsible for parsing the input file and performing any necessary initial validations on the input data itself.

struct Output { /* ... */ };

The Output struct encapsulates all data read from a program's output file (both participant's and jury's). It must contain:

• A static method read that takes a cplib::var::Reader& as its first parameter, and optionally a const Input& as its second parameter (if output parsing depends on input data). It returns an instance of Output. This method is responsible for parsing the output file and performing "validity" checks on the output format and constraints. If the output is invalid (e.g., out of range, wrong format), it should call in.fail("message").
• A static method evaluate that takes an evaluate::Evaluator&, const Output& pans (participant's output), const Output& jans (jury's output), and const Input& input as parameters. It returns an evaluate::Result. This method is responsible for comparing pans and jans based on the problem's logical correctness rules.

  auto a = in.read(var::i32("a", -1000, 1000));

This line demonstrates reading a variable using a variable reading template. cplib::var::i32 is an alias for cplib::var::Int<int32_t>. It's a template that specifies how to read a 32-bit signed integer. The constructor parameters ("a", -1000, 1000) define:

• "a": The name of the variable. When an error occurs during reading, this name will be displayed in the error message along with the reading stack trace, making error reports more readable.
• -1000, 1000: The minimum and maximum allowed values for the integer. CPLib automatically checks if the read value falls within this range.

    auto res = evaluate::Result::ac();
    res &= ev.eq("ans", pans.ans, jans.ans);
    return res;

Inside the Output::evaluate method, evaluate::Evaluator& ev is used to compare results. ev.eq("ans", pans.ans, jans.ans) compares the ans field of the participant's output (pans) with the jury's output (jans). If they are equal, it contributes to an "Accepted" result. If they are not equal, it marks the result as "Wrong Answer" and provides a detailed message including the variable name "ans" and the values.

When an output file (participant's or jury's) does not meet the format or range constraints specified in its read method, CPLib will automatically exit the program and report an error. For participant's output, this results in "Wrong Answer". For jury's output, it results in "Internal Error", indicating a problem with the test data itself.

CPLIB_REGISTER_CHECKER(chk, Input, Output);

The CPLIB_REGISTER_CHECKER(name, InputStruct, OutputStruct) macro registers the program as a CPLib checker. name (in the code, chk) is the name of the global state variable for the checker. InputStruct and OutputStruct are the names of the structs that define how to read the problem input and how to read and evaluate the program output, respectively. CPLib will internally manage the main function and call the read and evaluate methods of these structs.

Usage

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

./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 recommended to structure the logic using Input and Output structs with their respective read and evaluate methods. This approach leads to more readable and maintainable implementations.

#include <map>
#include <optional>
#include <string>
#include <utility>
#include <vector>
 
#include "cplib.hpp"
 
using namespace cplib;
 
// Define an Edge struct for reading graph edges
struct Edge {
  int u, v, w;
 
  // Edge::read takes a Reader and the graph size 'n' as context
  static Edge read(var::Reader& in) {
    // Using in() operator for reading multiple variables conveniently
    auto [u, v, w] = in(var::i32("u"), var::i32("v"), var::i32("w"));
    return {u, v, w};
  }
};
 
// Define the Input struct to hold graph data
struct Input {
  int n, m;
  std::map<std::pair<int, int>, int> graph; // Adjacency map for quick edge lookup
 
  static Input read(var::Reader& in) {
    auto [n, m] = in(var::i32("n"), var::i32("m"));
    // Read 'm' edges, passing 'n' as context to Edge::read via var::ExtVar
    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; // Undirected graph
    }
 
    return {n, m, graph};
  }
};
 
// Define the Output struct to hold the shortest path sum and the path itself
struct Output {
  int sum, len;
  std::vector<int> plan;
 
  // Output::read takes Reader and the Input struct as context
  static Output read(var::Reader& in, const Input& input) {
    // Read sum and length, with appropriate ranges
    auto sum = in.read(var::i32("sum", 0, std::nullopt));
    auto len = in.read(var::i32("len", 1, input.n * input.n)); // Max path length for N nodes
 
    // Read the path plan, ensuring nodes are within [1, input.n]
    auto plan = in.read(var::i32("plan", 1, input.n) * len);
 
    // Perform validity checks on the path
    if (plan.empty()) in.fail("Path cannot be empty");
    if (plan.front() != 1) in.fail("Path should begin with 1");
    if (plan.back() != input.n) in.fail("Path 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 {} <-> {} does not exist", plan[i - 1], plan[i]));
      result_sum += input.graph.at({plan[i - 1], plan[i]});
    }
 
    if (result_sum != sum)
      in.fail(format("Calculated path sum ({}) from plan does not match reported sum ({})",
                     result_sum, sum));
 
    return {sum, len, plan};
  }
 
  // Output::evaluate compares participant's output with jury's output
  static evaluate::Result evaluate(evaluate::Evaluator& ev, const Output& pans, const Output& jans,
                                   const Input&) {
    auto res = evaluate::Result::ac();
 
    // If participant's sum is strictly less than jury's sum,
    // it implies the jury's answer is not optimal. This is an internal error.
    if (pans.sum < jans.sum) {
      ev.fail(
          format("Participant's path sum ({}) is less than jury's path sum ({})! This indicates a "
                 "judge error.",
                 pans.sum, jans.sum));
    }
 
    // The problem asks for the shortest path sum.
    // If participant's sum is greater than jury's, it's WA.
    res &= ev.eq("sum", pans.sum, jans.sum);
 
    // If sums are equal, the path itself needs to be valid (already checked in read)
    // and correctly connects 1 to n (also checked in read).
    // No further comparison of 'plan' is strictly needed if 'sum' is correct,
    // as any valid path yielding the shortest sum is acceptable.
    // However, for completeness or stricter checks, one might compare 'len' or 'plan'
    // if multiple shortest paths exist and specific ones are preferred.
    // For this problem, we only care about the sum.
 
    return res;
  }
};
 
// Register the checker
CPLIB_REGISTER_CHECKER(chk, Input, Output);

This example demonstrates how to use variable reading templates for custom types and how to structure the evaluation logic.

Structured Data Types and read Methods:

• Edge struct: Defines the structure for a single edge. Its static read method reads u, v, and w.
• Input struct: Encapsulates n, m, and the graph adjacency map. Its static read method reads n and m, then uses var::ExtVar<Edge>("edges") * m to read m edges. var::ExtVar<T> is used to create a variable reading template for a custom type T. When T::read requires additional parameters, these parameters are passed to the var::ExtVar<T> constructor. 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 parameters without name. The operator() of in (e.g., in(var::i32("n"), var::i32("m"))) provides a concise way to read multiple variables with no interdependencies into a std::tuple.
• Output struct: Holds the reported sum, path length, and the path itself. Its static read method performs crucial "validity" checks:
  • Ensuring path nodes are within [1, input.n].
  • Verifying the path starts at 1 and ends at n.
  • Checking if all edges in the path exist in the graph.
  • Confirming that the reported sum matches the sum calculated from the plan.
  • If any validity check fails, in.fail(message) is called, which immediately reports "Wrong Answer" (for participant's output) or "Internal Error" (for jury's output) with a detailed stack trace.

Evaluation with evaluate::Evaluator:

The Output::evaluate method is where the core "equivalence" check happens.

• It receives an evaluate::Evaluator& ev, which is the primary tool for reporting results.
• A special case is handled: if pans.sum < jans.sum, it means the participant found a better answer than the jury's. This indicates a problem with the jury's solution or test data. ev.fail() is used here to report an "Internal Error" with a specific message, prompting a review of the jury's answer. This is a robust way to handle such scenarios, distinguishing them from a regular "Wrong Answer".
• ev.eq("sum", pans.sum, jans.sum) checks if the participant's sum (pans.sum) is equal to the jury's sum (jans.sum). If pans.sum > jans.sum, it automatically marks "Wrong Answer" with a descriptive message.

Suggestions

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

• Structure your code: Use custom Input and Output structs with their static read and static evaluate methods. This modular design improves readability and maintainability.
• Leverage var::Var: Use cplib::var::ExtVar for custom types and operator* for vectors. The operator() of in can simplify reading multiple independent variables.
• Perform "validity" checks in read methods: Implement checks for output format, ranges, and basic consistency (e.g., path starts/ends correctly, edges exist) within the static read methods of your Output struct and its nested types. Use in.fail("message") to report these errors.
• Perform "equivalence" checks in evaluate methods: Implement the core logical comparison between participant's and jury's outputs in the static evaluate method of your Output struct. Use evaluate::Evaluator methods (like ev.eq, ev.approx, ev.fail) for robust and descriptive result reporting.