Checker

Checker, also known as Special Judge, is used to verify whether an answer is valid. Using Testlib can save us from checking many things, making the implementation much simpler.

A Checker reads the input file name, the contestant's output file name, and the standard output file name from command-line arguments, determines whether the contestant's output is correct, and returns a predefined result.

Please read General before proceeding.

Simple Example

Problem

Given two integers \(a,b\) (\(-1000 \le a,b \le 1000\)), output their sum.

This problem obviously doesn't need a checker, but if one must write one:

#include "testlib.h"

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

  int pans = ouf.readInt(-2000, 2000, "sum of numbers");

  // Assume the standard output is correct, do not check its range
  // Later we will see this is not reasonable
  int jans = ans.readInt();

  if (pans == jans)
    quitf(_ok, "The sum is correct.");
  else
    quitf(_wa, "The sum is wrong: expected = %d, found = %d", jans, pans);
}

Writing the readAns Function

Suppose you have a problem where both input and output contain many numbers, e.g., given a DAG, find the longest path from \(s\) to \(t\) and output the path (multiple possible, output any one).

Below is an example of a bad checker.

Bad Implementation

#include "testlib.h"
//
#include <map>
#include <vector>
using namespace std;

map<pair<int, int>, int> edges;

int main(int argc, char* argv[]) {
  registerTestlibCmd(argc, argv);
  int n = inf.readInt();  // No need for readSpace() or readEoln()
  int m = inf.readInt();  // Because we don't need to check the validity of standard input in the checker
                          // (there is a validator)
  for (int i = 0; i < m; i++) {
    int a = inf.readInt();
    int b = inf.readInt();
    int w = inf.readInt();
    edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
  }
  int s = inf.readInt();
  int t = inf.readInt();

  // Read standard output
  int jvalue = 0;
  vector<int> jpath;
  int jlen = ans.readInt();
  for (int i = 0; i < jlen; i++) {
    jpath.push_back(ans.readInt());
  }
  for (int i = 0; i < jlen - 1; i++) {
    jvalue += edges[make_pair(jpath[i], jpath[i + 1])];
  }

  // Read contestant output
  int pvalue = 0;
  vector<int> ppath;
  vector<bool> used(n);
  int plen = ouf.readInt(2, n, "number of vertices");  // At least includes s and t
  for (int i = 0; i < plen; i++) {
    int v = ouf.readInt(1, n, format("path[%d]", i + 1).c_str());
    if (used[v - 1])  // Check if each vertex is used only once
      quitf(_wa, "vertex %d was used twice", v);
    used[v - 1] = true;
    ppath.push_back(v);
  }
  // Check start and end validity
  if (ppath.front() != s)
    quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s,
          ppath.front());
  if (ppath.back() != t)
    quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t,
          ppath.back());
  // Check if adjacent vertices have an edge
  for (int i = 0; i < plen - 1; i++) {
    if (edges.find(make_pair(ppath[i], ppath[i + 1])) == edges.end())
      quitf(_wa, "there is no edge (%d, %d) in the graph", ppath[i],
            ppath[i + 1]);
    pvalue += edges[make_pair(ppath[i], ppath[i + 1])];
  }

  if (jvalue != pvalue)
    quitf(_wa, "jury has answer %d, participant has answer %d", jvalue, pvalue);
  else
    quitf(_ok, "answer = %d", pvalue);
}

This checker has two main issues:

1. It assumes the standard output is correct. If the contestant's output is better than the standard output, it will be judged as WA, which is not ideal. Also, if the standard output is invalid, it will also produce WA. For both cases, the correct action is to return the Fail status.
2. The code for reading the standard output and the contestant's output is duplicated. In this problem, writing it twice is not a big deal—just a for loop—but if a problem has complex output, it will make the checker structure messy. Duplicate code greatly reduces maintainability and makes debugging or format modifications difficult.

The way to read the standard output and the contestant's output is actually identical, which is why we usually write a reading function that takes a stream as a parameter.

Good Implementation

// clang-format off

#include "testlib.h"
#include <map>
#include <vector>
using namespace std;

map<pair<int, int>, int> edges;
int n, m, s, t;

// This function takes a stream, reads from it,
// checks the validity of the path, and returns the path length.
// When stream is ans, all stream.quitf(_wa, ...)
// and failed readXxx() will return _fail instead of _wa.
// That is, if the output is invalid, for the contestant output stream it returns _wa,
// and for the standard output stream it returns _fail.
int readAns(InStream& stream) {
  // Read output
  int value = 0;
  vector<int> path;
  vector<bool> used(n);
  int len = stream.readInt(2, n, "number of vertices");
  for (int i = 0; i < len; i++) {
    int v = stream.readInt(1, n, format("path[%d]", i + 1).c_str());
    if (used[v - 1]) {
      stream.quitf(_wa, "vertex %d was used twice", v);
    }
    used[v - 1] = true;
    path.push_back(v);
  }
  if (path.front() != s)
    stream.quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s,
                 path.front());
  if (path.back() != t)
    stream.quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t,
                 path.back());
  for (int i = 0; i < len - 1; i++) {
    if (edges.find(make_pair(path[i], path[i + 1])) == edges.end())
      stream.quitf(_wa, "there is no edge (%d, %d) in the graph", path[i],
                   path[i + 1]);
    value += edges[make_pair(path[i], path[i + 1])];
  }
  return value;
}

int main(int argc, char* argv[]) {
  registerTestlibCmd(argc, argv);
  n = inf.readInt();
  m = inf.readInt();
  for (int i = 0; i < m; i++) {
    int a = inf.readInt();
    int b = inf.readInt();
    int w = inf.readInt();
    edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
  }
  int s = inf.readInt();
  int t = inf.readInt();

  int jans = readAns(ans);
  int pans = readAns(ouf);
  if (jans > pans)
    quitf(_wa, "jury has the better answer: jans = %d, pans = %d\n", jans,
          pans);
  else if (jans == pans)
    quitf(_ok, "answer = %d\n", pans);
  else  // (jans < pans)
    quitf(_fail, ":( participant has the better answer: jans = %d, pans = %d\n",
          jans, pans);
}

Note that with this approach we also check whether the standard output is valid. Writing the checker this way makes the program shorter and easier to understand and debug. This approach is also suitable for problems that output YES (and possibly a solution) or NO.

Note

For checking certain constraints, the InStream::ensure/ensuref() functions can be used more concisely. For example, lines 23 to 25 above can be equivalently written as:

stream.ensuref(!used[v - 1], "vertex %d was used twice", v);

Warning

Avoid calling global functions ::ensure/ensuref() in readAns, as this may cause _fail to be returned for contestant outputs that should be judged as WA, leading to errors.

Suggestions and Common Mistakes

• Write the readAns function; it can really make your checker great.

• Always specify ranges when reading contestant output. If some variables are not range-checked and are used as parameters, your checker may judge incorrectly or cause RE.

  • Bad Example

  // ....
  int k = ouf.readInt();
  vector<int> lst;
  for (int i = 0; i < k; i++)  // k = 0 and k = -5 behave the same here (loop body not entered)
    lst.push_back(ouf.readInt());
  // But we don't want to accept a list of length -5, right?
  // ....
  int pos = ouf.readInt();
  int x = A[pos];
  // Someone might output -42, 2147483456, or other illegal numbers causing checker RE
  

  • Good Example

  // ....
  int k = ouf.readInt(0, n);  // Invalid length will immediately judge WA instead of continuing check and causing RE
  vector<int> lst;
  for (int i = 0; i < k; i++) lst.push_back(ouf.readInt());
  // ....
  int pos = ouf.readInt(0, (int)A.size() - 1);  // Prevent out of range
  int x = A[pos];
  // ....
  

• Use item aliases.

• Unlike validators, checkers do not need to specifically check for non-whitespace characters. For example, for a checker that compares integers in order, we only need to check whether the contestant's output integers correspond to the answer integers. Whether the contestant outputs one integer per line or all integers on one line is a formatting issue that our checker does not need to care about.

Usage

Usually, we don't need to run it locally; the judging tool/OJ will handle it for us. But if needed, run it on the command line in the following format:

./checker <input-file> <output-file> <answer-file> [<report-file> [<-appes>]]

Some Preset Checkers

Often, our checker's task is simple (e.g., checking if output integers are correct, or if output floating-point numbers meet precision requirements). Testlib has already provided implementations for these checkers, which we can use directly.

Some commonly used checkers are:

• ncmp: Compare 64-bit integers in order.
• rcmp4: Compare floating-point numbers in order, with maximum acceptable error (absolute or relative) not exceeding \(10^{-4}\) (there are also rcmp6, rcmp9, etc., for different precision requirements, used similarly to rcmp4).
• wcmp: Compare strings in order (ignoring spaces, newlines, and other non-whitespace characters).

• yesno: Compare YES and NO, case-insensitive.

  This article is mainly translated from Checkers with testlib.h - Codeforces. The GitHub repository for testlib.h is MikeMirzayanov/testlib.

---

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