Checker

A checker, or Special Judge, is used to verify whether an answer is valid. Testlib lets us avoid checking many things, making implementation much simpler.

A checker reads the input file name, participant output file name, and standard output file name from command-line arguments, determines whether the participant output is correct, and returns a predefined result:

Read General before reading the following text.

A Simple Example

This problem clearly does not need a checker, right? However, one can still be written if necessary:

#include "testlib.h"

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

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

  // Assume that the standard output is correct, and do not check its range
  // We will see later that 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 whose input and output both contain many numbers, such as: given a DAG, find the longest path from $s$ to $t$ and output the path (there may be multiple paths; output any one).

Here 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 the validity of the standard input does not need to be checked 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 the 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 the participant output
  int pvalue = 0;
  vector<int> ppath;
  vector<bool> used(n);
  int plen = ouf.readInt(2, n, "number of vertices");  // At least includes the two vertices 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 that each edge is used only once
      quitf(_wa, "vertex %d was used twice", v);
    used[v - 1] = true;
    ppath.push_back(v);
  }
  // Check the validity of the start and end vertices
  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 whether there is an edge between adjacent vertices
  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 problems:

1. It assumes that the standard output is correct. If the participant output is better than the standard output, it will be judged WA, which is not ideal. At the same time, if the standard output is invalid, it will also produce WA. For both cases, the correct operation is to return the Fail status.
2. The code for reading the standard output and participant output is duplicated. In this problem, writing the input code twice is not a major issue because only one for loop is needed; however, if a problem has very complex output, this will make the structure of your checker confusing. Duplicated code greatly reduces maintainability and makes debugging or modifying the format difficult.

The ways of reading the standard output and participant output are actually exactly the same. This is why we usually write a reading function that takes a stream as its 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 accepts a stream and reads from it
// Checks the validity of the path and returns its length
// When stream is ans, all stream.quitf(_wa, ...) calls
// and failed readXxx() calls return _fail rather than _wa
// That is, if the output is invalid, it returns _wa for the participant output stream,
// and _fail for the standard output stream
int readAns(InStream& stream) {
  // Read the 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);
}

Notice that this version also checks whether the standard output is valid. Writing the checker this way makes the program shorter and easier to understand and debug. This approach also applies to problems that output YES (and an accompanying solution, for example) or NO.

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

Suggestions and Common Mistakes

• Write a readAns function; it really can make your checker excellent.

• Always constrain the range when reading participant output. If some variable is not constrained and is used as a parameter somewhere, your checker may judge incorrectly or produce an RE.

  • Negative example

  // ....
  int k = ouf.readInt();
  vector<int> lst;
  for (int i = 0; i < k; i++)  // k = 0 and k = -5 have the same effect here (the loop body is not entered)
    lst.push_back(ouf.readInt());
  // But we do not want to accept a list of length -5, do we?
  // ....
  int pos = ouf.readInt();
  int x = A[pos];
  // Someone might output -42, 2147483456, or another invalid number and cause the checker to RE
  

  • Positive example

  // ....
  int k = ouf.readInt(0, n);  // An invalid length is immediately judged WA and the check does not continue to cause an 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 a validator, a checker does not need to specifically check for non-whitespace characters. For example, for a checker that compares integers in order, we only need to determine whether the integers in the participant output correspond to the integers in the answer. The checker need not care about formatting issues such as whether the participant outputs one integer per line or all integers on one line.

Usage

Usually, we do not need to run it locally; the evaluation tool/OJ will handle everything. If necessary, however, run it from the command line in the following format:

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

Some Predefined Checkers

Often, the work done by our checker is very simple, such as determining whether an output integer is correct or whether an output floating-point number meets the precision requirements. Testlib has already provided implementations of these checkers, so we can use them directly.

Some commonly used checkers are:

• ncmp: Compare 64-bit integers in order.

• rcmp4: Compare floating-point numbers in order, accepting a maximum error (absolute or relative) of no more than $10^{-4}$ (there are also rcmp6, rcmp9, and other checkers with different precision requirements; their usage is similar to rcmp4).

• wcmp: Compare strings in order (without whitespace, newline characters, or other non-whitespace characters).

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

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