tcframe Documentation¶

Components of a runner program¶

Each runner program consists of the following components.

Problem specification

Where you specify the problem’s time/memory limits, I/O variables, I/O formats, constraints, etc. It is a very formal specification of what are stated in the problem description.

Generator specification

Where you define the sample and official test cases, which solution to use, where to store the generated test cases, etc. It is tied to a particular problem specification: each test case must conform to the problem constraints, etc.

Writing main() function¶

To be able to be compiled into an executable, a runner program must have a main() function. Currently, there is only one way to write the main() function, as follows.

int main(int argc, char* argv[]) {
    Runner<Problem> runner(argc, argv);

    runner.setGenerator(new Generator());
    return runner.run();
}

In most cases, you would want to just copy and paste the above snippet as your main() function.

Compiling runner program¶

You must have g++ at least version 4.7 to compile a runner program. It must be compiled with the following additional options:

• -I <tcframe-location>/include, where tcframe-location is where you downloaded and extracted tcframe.
• -std=c++11, since tcframe relies on C++11 features.

For example:

g++ -I ~/tcframe/include -std=c++11 -o runner runner.cpp

Running runner program¶

A runner program is an ordinary executable program. It can be run by executing it:

./runner

The above execution will produce the actual test case files.

Notes¶

• A runner consists of only problem and generator specifications. We are planning to support other components, for example, checker and inline solution specifications.
• A problem specification and the corresponding generator specification must be in the same file. We might support separating the specifications into two files.

Configuring problem¶

Several properties of the problem can be configured by overriding Config() method. In the method, we can set a property by calling the appropriate method as follows.

Slug

By calling setSlug(<slug>). A slug is a simple name, codename, or identifier for the problem. For example: aplusb, wf-2016-a, tree-paint, etc. The resulting test case files will be prefixed by the slug, for example: aplusb_1.in.

Time limit

By calling setTimeLimit(<timeLimit>). Time limit is specified in seconds. Time limit will be enforced when simulating submissoin.

Memory limit

By calling setTimeLimit(<memoryLimit>). Memory limit is specified in megabytes. Similarly, it will be enforced when simulating submission.

Here is an example of a valid problem configuration:

void Config() {
    setSlug("rabbit-jump");
    setTimeLimit(2);
    setMemoryLimit(256);
}

Supported I/O variable types¶

tcframe supports three types of I/O variables as follows.

Scalar

Variables of built-in integral types (int, long long, char, etc.), built-in floating-point types (float, double), and std::string.

Vector

std::vector<T>, where T is a scalar type as defined above.

Matrix

std::vector<std::vector<T>>, where T is a scalar type as defined above.

Other types are not supported as I/O variables. tcframe prefers STL types whenever possible. For example, char* is not supported as strings. Also, regular arrays (T[]) and 2D arrays (T[][]) are not supported.

Supported I/O segments¶

The list of supported segments is given below. In all segments, it must be noted that:

• The terms scalar, vector, and matrix below refer to the I/O variable types described in the previous chapter.
• Vectors and matrices will have 0-based indexing. This is strict and there is no way to enforce 1-based indexing.

Empty line

Specified by the macro EMPTY_LINE(). Represents a single, empty line.

Singe line

Specified by the macro LINE(...). Represents space-separated values in a single line.

The macro accepts one or more I/O variables as arguments. The value of the variables will be space-separated. For example: ”... the first line consists of two space-separated integers N and M” can be specified by LINE(N, M).

Besides scalars, the arguments can be vectors, too. You need to specify the number of elements using % SIZE(<size>) syntax after each vector. For example: ”... the next line consists of N space-separated integers A[0], A[1], ... A[N-1]” can be specified by LINE(A % SIZE(N)). The size can be a constant as well; for example, LINE(B % SIZE(3)).

You can freely combine scalars and vectors in LINE(); for example, LINE(N, A % SIZE(N), C % SIZE(2)) would represent a line consisting of N A[0] A[1] ... A[N-1] C[0] C[1].

Lastly, you can specify a vector without fixed size, as long as it is the last argument. For example: ”... the input consists an integer X followed by space-separated integers” can be specified by LINE(X, A) (assuming A is a vector).

Multiple lines

Specified by the macro LINES(...) % SIZE(<size>). Represents multiple lines, each containing an element of a vector given as the argument.

For example: ”... each of the next N lines contains an integer X[i]” can be specified by LINES(X) % SIZE(N).

There could be more than one vector as well. For example: ”... the next N lines each contains space-separated integers X[i] and Y[i]” can be specified by LINES(X, Y) % SIZE(N). If there are multiple vectors, they all must have the same number of elements.

You also could specify jagged vector as the last argument. This is useful for input format like, ”... then M lines follow. Each line begins with a string op. If op is UPDATE, then it is followed by two integers x y. If it is QUERY, then it is followed by a single integer z”. This can be specified by LINES(op, data) where op is a vector<string> and data is a vector<vector<int>>. Then, data[i] represents a vector of integers in the i-th line, which can consist of one of two elements.

Grid

Specified by the macro GRID(...) % SIZE(<row>, <column>). Represents a grid containing elements of a matrix given as the argument, laid out in a grid.

For example: ”... each fo the next R lines contain C integers G[i][j]” can be specified by GRID(G) % SIZE(R, C).

If the matrix is of type char, the elements in each row is not space-separated, otherwise they are space-separated.

For more details, consult the API reference for I/O segments.

Notes¶

Unfortunately, the following are not supported (yet):

Constants in I/O segments

For example: ”... the first line will always consist of the string BEGIN.” Everything must be wrapped in variables.

As a workaround, just create an input variable and initialize it to BEGIN.

Complex conditional I/O format that can’t be handled by jagged vectors

There is NO known general workaround yet. We’re still working on designing how to handle complex format.

However, there are workarounds for simple cases, for example:

“Output the required sum, or the string IMPOSSIBLE if there is no solution.”

In this case, you can just use a string as the output variable. The downside is that it is not type-safe; for example, the generation won’t fail if the reference solution mistakenly output an invalid string such as 123abc.

However, a last resort for a workaround does exist for output format. If you have complex output format, you can just omit the method OutputFormat() altogether and your solution’s output won’t be checked at all for validity.

Constraint definitions¶

Constraints are specified as a list of constraint definitions. Each constraint definition is a boolean predicate of some property of the input variables. The predicate is passed as an argument to the CONS() macro. The macros are then called one-by-one as method calls:

void Constraints() {
    CONS(<predicate 1>);
    CONS(<predicate 2>);
    ...
}

The constraint definition can be pulled directly from the constraints section in the actual problem description. For example: “1 ≤ A ≤ 1,000” can be specified by CONS(1 <= A && A <= 100). “1 ≤ A, B ≤ 1,000” translates into two specifications: CONS(1 <= A && A <= 1000) and CONS(1 <= B && B <= 1000). “1 ≤ A ≤ B ≤ 1,000” translates into CONS(1 <= A && A <= B && B <= 1000).

How about more complex predicates, such as “1 ≤ A[i] ≤ 1,000”? You can write a private method for this purpose. For example, it can be translated into CONS(eachElementBetween(A, 1, 1000)) and a private method as follows:

bool eachElementBetween(const vector<int>& X, int lo, int hi) {
    for (int x : X) {
        if (x < lo || x > hi) {
            return false;
        }
    }
    return true;
}

This also applies to even more complex predicates, such as “It is guaranteed that the given graph is a tree”. This can be translated to CONS(graphIsTree()) and define the appropriate private boolean method.

Notes¶

It is tedious to write eachElementBetween() predicate over and over again as it is very common in problems. We are working on providing such helper methods as core part of tcframe in the next versions.

Subtask definitions¶

A subtask is basically just a set of constraints. It can be specified by the method SubtaskX(), where X is the subtask number. Inside the method, the constraint specifications are given, similar to what you usually do in the Constraints() method.

Thus, the above example can be implemented as:

void Subtask1() {
    CONS(N == 1);
    CONS(1 <= K && K <= 100);
}

void Subtask2() {
    CONS(1 <= N && N <= 100);
    CONS(K == 1);
}

void Subtask3() {
    CONS(1 <= N && N <= 100);
    CONS(1 <= K && K <= 100);
}

Test groups¶

If your problem has subtasks, you will be writing test groups, not test cases. Refer to this chapter on how to do that.

Notes¶

Currently, tcframe does not provide a way to specify subtask points. It is up to the grader to implement the scoring.

Configuring generator¶

Several properties of the problem can be configured by overriding Config() method. In the method, we can set a property by calling the appropriate method as follows.

Test cases directory

By calling setTestCasesDir(<directory>). This directory will contain the generated test cases. The directory is specified as a relative path to the runner. The default value is tc.

Solution command

By calling setSolutionCommand(<command>). The command for executing the reference solution. The default value is ./solution.

Here is an example of a valid problem configuration:

void Config() {
    setTestCasesDir("generated-tc");
    setSolutionCommand("java Solution");
}

For simplicity, usually you don’t have to specify this method at all and just accept/use the default values.

Test case definition¶

Test cases are specified as a list of test case definitions. Each test case definition is a comma-separated list of input variable assignments. The list is passed as the argument to the CASE() macro. The macros are then called one-by-one as method calls:

void TestCases() {
    CASE(<assignments list 1>);
    CASE(<assignments list 2>);
    ...
}

For example, a valid test case definition is CASE(N = 100, M = 75). Vectors and matrices can be assigned conveniently using braces; for example, CASE(V = {1, 2, 3}, M = {{1, 2}, {3, 4}}).

For more complex assignment, such as constructing a tree, create a private void method that constructs the tree, and call it in CASE(). For example, CASE(N = 100, linearTree()) and having this private method:

/* Constructs a linear tree */
void linearTree() {
    parent.clear(); // important!
    for (int i = 0; i < N; i++) {
        parent.push_back(i-1);
    }
}

Each test case definition will be realized as a pair of input/output files, with the following filenames: <slug>_<case-number>.in and <slug>_<case-number>.out. For example, aplusb_1.in, aplusb_1.out.

Sample test case definition¶

Unlike test cases, sample test cases are specified as literal strings, exactly as they appear in problem statement. This way, you can be visually sure that you are typing sample test cases in problem statement correctly.

The literal strings are passed line-by-line to the SAMPLE_CASE() macro as follows (note the {} braces):

void SampleTestCases() {
    // Sample test case 1
    SAMPLE_CASE({
        "<line 1>",
        "<line 2>",
        ...
    });

    // Sample test case 2
    SAMPLE_CASE({
        "<line 1>",
        "<line 2>",
        ...
    });

    ...
}

For example, these sample test cases:

3 4
1 2 3

and

6 2
10 1 4 5 7 3

can be translated to:

void SampleTestCases() {
    SAMPLE_CASE({
        "3 4",
        "1 2 3"
    });

    SAMPLE_CASE({
        "6 2",
        "10 1 4 5 7 3"
    });

    ...
}

Each sample test case definition will be realized as a pair of input/output files, with the following filenames: <slug>_sample_<case-number>.in and <slug>_sample_<case-number>.out. For example, aplusb_sample_1.in, aplusb_sample_1.out.

Random number generator¶

tcframe provides a simple random number generator object, tcframe::rnd. For example, you can use it to generate a random array: CASE(N = 100, randomArray()) where randomArray() is defined as follows.

void SampleTestCases() {
    A.clear();
    for (int i = 0; i < N; i++) {
        A.push_back(rnd.nextInt(1000000));
    }
}

For more details, consult the API reference for random number generator.

Manipulating input variables with different representation¶

Often, you want to manipulate input variables with a different representation from what is defined in the input format section. For example, suppose that you want to have a tree as an input. In the input format (in problem specification class), you specify the tree as a list of edges (U[i], V[i]) as follows:

void InputFormat() {
    LINE(N);
    LINES(U, V) % SIZE(N - 1);
}

and you want to manipulate the tree as a vector P[], where P[i] is the parent of node i. (I.e., you have private variable vector<int> P in generator specification class.)

This can be achieved by writing a special method FinalizeInput() in generator specification class and transforming the vector P[] into a pair of vectors (U[], V[]) in it.

void FinalizeInput() {
    U.clear();
    P.clear();
    for (int i = 0; i < N; i++) {
        if (P[i] != -1) {
            U.push_back(i);
            V.push_back(P[i]);
        }
    }
}

Notes¶

Due to how currently the CASE() macro is implemented, it is not possible for it to refer to a for-loop counter. For example, this is illegal:

void TestCases() {
    for (int i = 1; i <= 100; i++) {
        CASE(N = i);
    }
}

In fact, for now please do not use any block constructs at all inside TestCases(). The CASE() macros should be first-level statements.

This may change in future versions.

Designing test groups¶

In this example, we will use this subtasking scheme:

Our advice on designing test groups is as follows.

First, create a Venn diagram denoting the valid test cases for all subtasks. For this problem, the diagram will be like this:

In order to have a strong set of test cases, we should create a test group for each closed region in the Venn diagram. In this case, we will have four test groups as follows:

• Test group 1: consists of only one test case N = K = 1. Assign it to subtasks {1, 2, 3}.
• Test group 2: generate test cases that satisfy N = 1; 2 ≤ K ≤ 100. Assign them to subtasks {1, 3}.
• Test group 3: generate test cases that satisfy 2 ≤ N ≤ 100; K = 1. Assign them to subtasks {2, 3}.
• Test group 4: generate test cases that satisfy 2 ≤ N, K ≤ 100. Assign them to subtasks {3}.

Test group definitions¶

To define test groups, write each of the methods TestGroupX(), where X is a positive integer denoting the test group number, starting from 1. Then, call the assignToSubtasks(S) method as the first statement, where S is a list of subtask numbers. The remaining bodies of test group methods are test case definitions. For the above example:

void TestGroup1() {
    assignToSubtasks({1, 2, 3});
    // CASE() calls follow
}
void TestGroup2() {
    assignToSubtasks({1, 3});
    // CASE() calls follow
}
void TestGroup3() {
    assignToSubtasks({2, 3});
    // CASE() calls follow
}
void TestGroup4() {
    assignToSubtasks({3});
    // CASE() calls follow
}

Each test case definition will be realized as a pair of input/output files, with the following filenames: <slug>_<group-number>_<case-number>.in and <slug>_<group-number>_<case-number>.out. For example, aplusb_2_3.in, aplusb_2_3.out.

Notes¶

Although a test group may be assigned to several subtasks, tcframe will produce the test case files according to their test group and test case number as defined above. It is up to the implementation of the grader on how to choose which test cases to grade for a subtask. For example, if your grader only accepts a set of test cases for each subtask, you can duplicate each test case for every subtask it is assigned to.

For tcframe‘s submission simulation feature, each test case will be executed only once. The result is shared for every subtask it is assigned to.

Problem specification class¶

• Declare an integer input variable (e.g., T) that will hold the number of test cases in a single file.

  protected:
      int T;
  
      ...
  

• In the problem configuration, call the setMultipleTestCasesCount() method with the previous variable as the argument.

  void Config() {
      ...
  
      setMultipleTestCasesCount(T);
  
      ...
  }
  

• The input format specification should not contain T. It should specify the format of a single test case only. The number of test cases will be automatically prepended in the final combined test case input file.

• Constraints can be imposed on T, by writing the method MultipleTestCasesConstraints() method and defining constraints there.

  void MultipleTestCasesConstraints() {
      CONS(1 <= T && T <= 20);
  }
  

Generation specification class¶

No changes are necessary.

Solution program¶

Although the input format only specifies a single test case, the solution should read the number of test cases in the first line. In other words, the solution will read the final combined test cases input file.

Notes¶

Currently, it is impossible to prepend each output with something like Case #X, where X is the test case number.

Brief output¶

If you want to automate checking the result of each solution, you can set the output of the submission to be “brief”, i.e., concise and easy to parse by another program. Just pass the command-line option --brief:

./runner submit ./alt_solution --brief

Here is a sample brief output for problems with subtasks:

1:AC
2:WA
3:RTE

And here is for problems without subtasks:

WA