tcframe Documentation

Note

tcframe 1.x has been released! Check out 1.0.0 release notes for migration guide from 0.x.

Welcome to the official documentation of tcframe, a competitive programming test cases generator framework! This documentation is organized into several sections:

Introduction

General information of tcframe project. Contains some code examples. Start here to grasp general understanding of this framework.

Getting Started

After getting the high-level concept of the framework, why not actually start writing a test cases generator? This section will guide you to install and write your very first generator.

Topic Guides

Now that you got your hand wet with your first generator, master each of tcframe’s key concepts in more details here.

Tutorials

Tutorials, case studies, and best practices in writing generators for real competitive programming problems.

API Reference

Finally, this is an API documentation of all tcframe features that you will be looking up often when writing your generator.


Introduction

tcframe is a C++ framework for generating test cases of competitive programming problems. This framework helps problem writers prepare test cases in a structured manner and ensures that the generated test cases are valid according to the specified constraints.

Example high-level usage:

  1. Specify input/output variables.

    int A, B;
    int sum;
    
  2. Specify input/output formats, using a rich set of format macros.

    void InputFormat() {
        LINE(A, B); // A line containing space-separated A and B
    }
    void OutputFormat() {
        LINE(sum);
    }
    
  3. Specify the grading configuration.

    void GradingConfig() {
        TimeLimit(2);
        MemoryLimit(64);
    }
    
  4. Specify the constraints. Subtasks are supported.

    void Constraints() {
        CONS(1 <= A && A <= 1000);
        CONS(1 <= B && B <= 1000);
    }
    
  5. Specify the sample test cases.

    void SampleTestCase1() {
        Input({
            "2 8"
        });
        Output({
            "10"
        });
    }
    void SampleTestCase2() {
        Input({
            "42 100"
        });
        Output({
            "142"
        });
    }
    
  6. Specify the official test cases. Simple random number generator is available.

    void TestCases() {
        CASE(A = 1, B = 1);
        CASE(A = 77, B = 99);
        CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000));
    }
    
  7. Write and compile the official solution to this problem, using any programming language you wish. Of course, it is the infamous A+B problem.

    #include <iostream>
    using namespace std;
    
    int main() {
        int A, B;
        cin >> A >> B;
        cout << (A + B) << endl;
    }
    
  8. Run the generator. Actual test cases (.in and .out files) will be generated. Profit!

  9. If you ever specified an invalid test case, such as CASE(A = 0, B = 1), you will get a nice error message:

    sum_4: FAILED
      Description: A = 0, B = 1
      Reasons:
      * Does not satisfy constraints, on:
        - 1 <= A && A <= 1000
    

Features

tcframe supports:

  • Batch and interactive problems.
  • ICPC-style problems and IOI-style problems with subtasks and points.
  • Multiple test cases per file.
  • Local grading against the generated test cases, with time and memory limits.
  • Simple random number generation helper.

Requirements

tcframe requires:

  • Linux/OS X. Windows is not supported.
  • GCC ≥ 4.8. tcframe relies heavily on C++11 features.

Motivations

Why do we need test case generators?

  • Writing test cases manually is error-prone and time-consuming.
  • To enable distributing the test cases as a single, small generator file. No need to send 20 MB of testcases.zip over email anymore.
  • During problem development, constraints often change. Using a generator, we can easily amend the constraints and rerun the generator when needed.

Why do we need a framework for that?

  • Not everyone knows how to write a good test cases generator.
  • To avoid writing repetitive and boring tasks. For example: creating test case files with correct suffixes (foo_1.in, foo_1.out), running the official solution against the test case input files, etc.
  • To have a consistent format for generators, so that problem writers in a contest can better collaborate in writing test case generators.

Credits

tcframe is based on a paper submitted to IOI conference in 2015: Introducing tcframe: A Simple and Robust Test Cases Generation Framework, written by Ashar Fuadi.

tcframe was mainly inspired from testlib, written by Mike Mirzayanov et al.


License

tcframe is released under MIT license.

Source code can be found on GitHub.

Getting Started

In tcframe world, a problem is defined by a problem package, which consists of a spec file and one or more solution files. The spec file is then compiled into a runner program. The runner program together with the compiled solution files can then generate test cases for the problem.

Let’s write our first problem package! We are going to write a package for the following infamous “A+B” problem:

A+B Problem
Time Limit: 1 second
Memory Limit: 64 MB

Description
You are given two integers A and B. Compute the sum of them!

Input Format
A single line containing two space-separated integers A and B.

Output Format
A single line containing the required sum.

Sample Input
4 6

Sample Output
10

Constraints
- 1 ≤ A ≤ 1,000
- 1 ≤ B ≤ 1,000

Note

This starter guide will just demonstrate the basic features of tcframe. For more advanced features, please consult the Topic Guides afterwards.


Installation

Firstly, we must get tcframe on our system. It consists of C++ header files and a few helper scripts.

Download the latest tcframe here. Extract the zip file somewhere on your system; for example, ~/tcframe. We will call this directory “tcframe home”. Confirm that you extracted it correctly by verifying that the directory include exists directly inside tcframe home.

Then, add the following lines to your ~/.bashrc. This will set the environment variable TCFRAME_HOME to our tcframe home directory, and make tcframe command available everywhere.

export TCFRAME_HOME=~/tcframe
alias tcframe=$TCFRAME_HOME/scripts/tcframe

Restart your terminal session. Now, if you run

tcframe version

You should see the following output

usage: tcframe <command>

Available commands:
  build         Compile spec file into runner program
  version       Print tcframe version

You’re good to go!


Preparing package directory

Create a directory called sum somewhere. This will be our package directory for this A+B problem. Store all the files you will be creating on this guide in this directory.


Writing solution file

In order to be able to generate the test case output files, a reference solution must be available. For the purpose of this guide, call the solution file solution.cpp. Example solution:

#include <iostream>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    cout << (A + B) << endl;
}

Then, compile it to solution executable, for example:

g++ -o solution solution.cpp

Writing spec file

A spec file contains problem spec and test spec.

Create a C++ source file called spec.cpp. Copy-paste the following code to the file:

#include <tcframe/spec.hpp>
using namespace tcframe;

class ProblemSpec : public BaseProblemSpec {
protected:
    int A, B;
    int sum;

    void InputFormat() {
        LINE(A, B);
    }

    void OutputFormat() {
        LINE(sum);
    }

    void GradingConfig() {
        TimeLimit(1);
        MemoryLimit(64);
    }

    void Constraints() {
        CONS(1 <= A && A <= 1000);
        CONS(1 <= B && B <= 1000);
    }
};

class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    void SampleTestCase1() {
        Input({
            "4 6"
        });
        Output({
            "10"
        });
    }

    void TestCases() {
        CASE(A = 1, B = 1);
        CASE(A = 1000, B = 1000);
        CASE(A = 42, B = 100);
        CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000));
    }
};

We will explain this spec file in more details later – keep going!

Building runner program

Next, we will compile this spec file into what we call a runner program. We will use the tcframe command. Simply run this in the sum directory:

tcframe build

This will compile spec.cpp into runner. Make sure that it compiles before continuing this getting started guide!

Finally, run the runner program:

./runner

If everything is OK, you should get the following output:

Generating test cases...

[ SAMPLE TEST CASES ]
  sum_sample_1: OK

[ OFFICIAL TEST CASES ]
  sum_1: OK
  sum_2: OK
  sum_3: OK
  sum_4: OK

Generation finished. All test cases OK.

Congratulations, you have just written your first problem package using tcframe framework! Now, check out your sum/tc directory – it will contain the generated test case files.


Inspecting problem package

We will now examine each component of a problem package in more details.

Slug

A slug is a unique name/codename/identifier for the problem. It is taken from name of the problem package directory. Since we call our problem package directory sum, the slug of our example problem is sum.

Spec file

A spec file is a C++ source file called spec.cpp that lives inside the problem package directory.

tcframe header
#include <tcframe/spec.hpp>
using namespace tcframe;

tcframe/spec.hpp is the main tcframe’s header file for spec files. Each component of tcframe lives in the tcframe namespace, just like the STL functions that live in the std namespace. By importing the namespace, we don’t have to explicitly prefix each class/object we want to use with tcframe::.

Problem spec class
class ProblemSpec : public BaseProblemSpec {
protected:
    ...
};

A problem spec class is where we define the I/O formats, constraints, and some configurations of our problem. This class must inherit tcframe::BaseProblemSpec, and must be called ProblemSpec.

All required members of this class must go in the protected section.

Grading configuration
void GradingConfig() {
    TimeLimit(1);
    MemoryLimit(64);
}

Quite self-explanatory. This has actually no effect during test cases generation, and will affect local grading as explained in later section of this guide. If not specified, the default time limit is 2 seconds, and the default memory limit is 64 megabytes.

Input/output variables and formats
int A, B;
int sum;

void InputFormat() {
    LINE(A, B);
}

void OutputFormat() {
    LINE(sum);
}

Next, we defined the input and output variables and formats. The input consists of two values: A and B. The output consists of one value; let’s call it sum. We must declare a variable for each of those values, and then tell tcframe how to format them in the input/output files.

Here, we declared two integers A and B as input variables, and an integer sum as an output variable. InputFormat() and OutputFormat() methods specify the input/output formats in terms of the input/output variables. The LINE() macro here specifies a line consisting of space-separated values of the given arguments.

Constraints
void Constraints() {
    CONS(1 <= A && A <= 1000);
    CONS(1 <= B && B <= 1000);
}

The last part of a problem spec is constraints specification.

A constraint must depend on input variables only. Each constraint can be specified as a boolean predicate inside the CONS() macro.

Here, we have two constraints, which are just direct translations of what we have in the problem statement.


We now have a formal specification of our A+B problem. The next part is writing a test spec that specifies test cases which conform to the problem spec.


Test spec class
class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    ...
};

A test spec is a class that inherits tcframe::BaseTestSpec<T>, where T is the problem spec class. It must be called TestSpec.

This is where we actually write the test case definitions.

Test case definitions
void SampleTestCase1() {
    Input({
        "4 6"
    });
    Output({
        "10"
    });
}

void TestCases() {
    CASE(A = 1, B = 1);
    CASE(A = 1000, B = 1000);
    CASE(A = 42, B = 100);
    CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000));
}

Here, we finally defined the test cases (yeay!). For the purpose of this guide, we defined four test cases: 3 hand-made and 1 randomized. We also defined one sample test case that match with the one in the actual problem statement.

In tcframe, sample test cases, if any, are defined in the SampleTestCaseX() methods, where X is the sample test case number. Each sample test case is defined as line-by-line verbatim strings in the Input() and Output() methods. Sample test cases must conform to the input format, or tcframe will complain.

Test cases are defined in the TestCases() method. Each test case is defined by listing input variable assignments the CASE() macro, separated by commas. Here, we just defined a min case, max case, random hand-made case, and a randomized case. The last one is achieved using tcframe::rnd, a simple random number generator provided by tcframe.

Note

Yes, you can access the input variables directly inside the test spec, even though they are declared in the problem spec class!


We’ve covered each component of our problem package in more details. Next, let’s play around with our runner program.


Trying out invalid test cases

What happens when we specify invalid test cases? Let’s just try. Add this test case to our test spec:

CASE(A = 0, B = 1);

and this sample test case:

void SampleTestCase2() {
    Input({
        "1",
        "2"
    });
    Output({
        "3"
    });
}

Recompile (by running tcframe build) and rerun the runner program. You should now get the following output instead:

Generating test cases...

[ SAMPLE TEST CASES ]
  sum_sample_1: OK
  sum_sample_2: FAILED
    Reasons:
    * Expected: <space> after variable `A`

[ OFFICIAL TEST CASES ]
  sum_1: OK
  sum_2: OK
  sum_3: OK
  sum_4: OK
  sum_5: FAILED
    Description: A = 0, B = 1
    Reasons:
    * Does not satisfy constraints, on:
      - 1 <= A && A <= 1000

Generation finished. Some test cases FAILED.

Sweet! If we ever have invalid test cases, tcframe will tell us in human-readable message.

Remove the invalid test cases and move on to the next section.


Local grading

When preparing a problem, it’s ideal if we have at least another solution as an alternative/secondary solution. tcframe lets you “grade” another solution using the main solution as the reference. The time and memory limits from GradingConfig() as explained previously will be taken into consideration.

First, fix our spec file and re-run it to get back the correct test cases (important!). Then, write an alternate solution that deliberately behaves incorrectly on some test cases. Write the following as solution_alt.cpp:

#include <iostream>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;

    if (A == 1) {
        cout << 3 << endl;
    } else if (A == 1000) {
        while (true);
    } else if (A == 42) {
        return 1 / 0;
    } else {
        cout << (A + B) << endl;
    }
}

Compile the solution into solution_alt executable, and then run the following command:

./runner grade --solution=./solution_alt

The above command tells tcframe to run the specified alternate solution command against the output files previously produced by the main solution.

You should get the following output:

Local grading with solution command: './solution_alt'...

[ SAMPLE TEST CASES ]
  sum_sample_1: Accepted

[ OFFICIAL TEST CASES ]
  sum_1: Wrong Answer
    * Diff:
(expected) [line 01]    2
(received) [line 01]    3

  sum_2: Time Limit Exceeded
  sum_3: Runtime Error
    * Execution of submission failed:
      - Floating point exception: 8
  sum_4: Accepted

[ VERDICT ]
  Time Limit Exceeded [25]

We get a detailed verdict of each test case. Nice, isn’t it? The final result here is Time Limit Exceeded, which is the “worst” verdict among all test case verdicts, and we get 25 points because we get one test case correct out of all four test cases.


We’ve covered the basics of tcframe. At this point, continue reading Topic Guides for more in-depth explanation of tcframe features.

Topic Guides

In this guide, we will learn each aspect of tcframe more thoroughly. Each section may have notes at the end, explaining the current limitations and future plans of the corresponding aspect.

Problem package

A problem package is the unit of work in tcframe that defines a problem and its test data. It is a directory that consists of all files related to the problem, particularly a spec file and one or more solution files. It is identified by a unique name called slug.

Slug

A slug can be considered as the codename of a problem. For example, if your problem name is “Counting Tree”, the slug could be tree or counting-tree or whatever you like, as long as it consists of one or more characters a-z, A-Z, 0-9, and -. The produced test case files will have the slug as the prefix, for example: tree_1.in.

The slug will be taken from the name of the problem package’s directory. For example, if your problem package directory is /home/fushar/my-contest/tree/, then the slug would be tree.

It is also possible to prepend the slug with some metadata string, separated by an underscore (_). For example, if tree if your third problem in your contest, you might want to call your problem package directory /home/fushar/my-contest/c_tree/. In this case, the slug would be still tree.

Components of a problem package
Spec file
The formal specification of the problem.
Solution files
A reference solution and one or more alternate solutions to the problem.
Evaluator helper files
Optional, e.g. custom scorer and communicator.

Spec and runner

The core activity when preparing test cases using tcframe is writing spec files. A spec file, along with a reference solution program and optionally some evaluator helper files, completely define the test cases of a single problem. A spec file is compilable into a single executable called runner program, which generates the test cases when executed.

To write a spec file, create a C++ source file called spec.cpp in the problem package directory, and include the following header:

#include <tcframe/spec.hpp>

Every component of tcframe falls under tcframe namespace, so you might want to import it for convenience:

using namespace tcframe;

In this file, you will be writing two classes: ProblemSpec and TestSpec.


Problem spec

A problem spec is a formal representation of a problem statement/description. It is the first step and the source of truth of the entire preparation of a problem. Once a problem spec is finalized, the corresponding test spec and a reference solution can then be developed.

In tcframe, a problem spec is implemented as a class called ProblemSpec that inherits tcframe::BaseProblemSpec.

class ProblemSpec : public BaseProblemSpec {
protected:
    ...
};

All members of this class must go into the protected section, except for private helper methods.

I/O variables
Member variables which compose the I/O formats.
I/O formats
How I/O variables are arranged in actual test case files.
Constraints
Conditions that I/O variables must satisfy.
Subtasks
Set of constraints in subproblems.

Test spec

A test spec defines the actual test cases for a particular problem spec. For problems with subtasks, it also defines how the test cases are distributed to the subtasks.

In tcframe, a problem spec is implemented as a class called TestSpec that inherits tcframe::BaseTestSpec<T>, where T is the problem spec class (which should be ProblemSpec).

class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    ...
};

All members of this class must go in the protected section, except for private helper methods.

Test cases
Particular set of values of input variables.
Test groups
Set of test cases which conform to the same set of subtasks

Compiling spec file

You must have g++ at least version 4.8 to compile a spec file.

A spec file is compiled into a runner program using the following tcframe command:

tcframe build

The above command will compile spec.cpp into an executable runner program in the problem package directory.

It is also possible to specify additional compilation flags, by setting the $TCFRAME_CXX_FLAGS environment variable. For example:

export TCFRAME_CXX_FLAGS="-Wall -O2"

Runner program

A runner program is an ordinary executable program. By executing the runner program, the test cases will be generated. By default, the produced test cases will be output to tc directory inside problem package directory.

./runner

See the API reference for more details on supported command-line options, such as specifying which solution to run for producing the output files.

A runner program can also be used for performing local grading.

I/O variables

Input variables are C++ variables whose values compose test cases input files. They are are direct translations from variables mentioned in the problem statement’s input format section into C++ variables. For example, given the following description:

The first line contains two integers N and K. The second line contains N space-separated integers A[1], A[2], …, A[N].

we will have three input variables: int N, int K, and vector<int> A.

Input variables are the basic units of computation in tcframe. For example, they are manipulated in three different places:

Output variables are defined in a similar way, the only difference being that they are just manipulated in output format definition. Also, usually they consist of just a single variable without name in the problem statement’s output format. We can just name them result or something similar.

I/O variables are defined as protected member variables in the problem spec class. For example:

class ProblemSpec : public BaseProblemSpec {
protected:
    int N, K;
    vector<int> A;

    string result;

    // the rest of problem spec components follow
};

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.

I/O formats

Input format specifies two things at the same time:

  • How the input variable values should be printed to official test case input files.
  • How the sample test case input files should be parsed into input variables, as they are specified as literal strings. If some sample sample test cases can’t be parsed, it means that you have written invalid sample test cases, and the whole generation will fail.

Output format specifies how the output files should be parsed into output variables. If the output files can’t be parsed, it means that you have written invalid solution program, and the whole generation will fail.

Each of the I/O formats is defined as a list of I/O segments in InputFormat() and OutputFormat() methods of the problem specification class, respectively, as follows.

void InputFormat() {
    // list of input segments
}

void OutputFormat() {
    // list of output segments
}

Each I/O segment is specified by a function-like C++ macro. The I/O segments are specified one-by-one, each as a statement that calls the macro. For example:

void InputFormat() {
    LINE(N, M);
    EMPTY_LINE();
    LINE(A % SIZE(N));
}

Supported I/O segments

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

There are two categories of I/O segments: raw segments and tokenized segments.

Raw segments

These segments do not do any special formatting to the value of the variables; they will print/parse them as-is.

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

Specified by the macro RAW_LINE(...). Represent a line of the string given as the only argument. The argument must be of std::string type.

For example: “… the next line consists of a sentence containing arbitrary printable ASCII characters S” can be specified by RAW_LINE(S) (where S is a string).

Multiple raw lines

Specified by the macro RAW_LINES(...) % SIZE(<size>). Represent lines of string given as the only argument. The argument must be of std::vector<std::string> type.

For example: “… each of the next N lines consists of a sentence containing arbitrary printable ASCII characters S” can be specified by RAW_LINES(S) % SIZE(N) (where S is a vector of strings).

The size can also be omitted, as long as this is the last segment.

Tokenized segments

These segments do some formatting to the value of the variables. For example, the elements of a vector variable in a line will be printed space-separated.

Note

In tokenized segments, string variables cannot have whitespaces. For example, hello, world! is considered to have two string variables: hello, and world!. Use raw segments if you want to work with strings containing whitespaces.

Single 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) (where 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 or two elements.

Lastly, the size can also be omitted, as long as this is the last segment.

Grid

Specified by the macro GRID(...) % SIZE(<row>, <column>). Represents a grid containing elements of a matrix given as the only 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 formats.


BeforeOutputFormat()

The special BeforeOutputFormat() method, if specified, will be executed right before the produced output is validated against the output format. It is useful when the output format segments depend on the input variables. For example, suppose that the input is a list of commands, each of which is either a query or an update. The output should contain as many lines as the number of update commands present in the input.

You can declare a helper variable, e.g. update_count, and have LINES(answers) % SIZE(update_count) as the output format. Then, compute the value of update_count in the BeforeOutputFormat() method. For example:

int update_count;
vector<int> answers;

void BeforeOutputFormat() {
    // count the number of update queries and assign it to update_count
}

void OutputFormat() {
    LINES(answers) % SIZE(update_count);
}

Multiple output formats

Sometimes, there are more than one possible output formats. For example: “If there is no valid solution, output a single line containing -1. Otherwise, the first line of the output should contain K, followed by a line containing K space-separated integers representing the answer.”

This can be accomplished using OutputFormatX(), where X is the output format number. A test case output is valid if it conforms to at least one of the output formats.

Note

As of this version, you can define up to 5 output formats: OutputFormat1() .. OutputFormat5().

The above example could be implemented as follows.

int impossible;

int K;
vector<int> answers;

void OutputFormat1() {
    LINE(impossible);
}

void OutputFormat2() {
    LINE(K);
    LINE(answers % SIZE(K));
}

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/raw line(s)
As a workaround, if you have a very complex output format, you can just omit the methods OutputFormat()/OutputFormatX() altogether and your solution’s output won’t be checked at all for validity.

Problem Styles

The StyleConfig() method of the problem spec class can be used to configure several aspects related to the nature of the problem itself and is independent from the test spec.

void StyleConfig() {
    // option specifications
}
Evaluator

An evaluator specifies how to run a solution against a test case. Two types of evaluators are supported:

Batch

Enabled by calling BatchEvaluator(). This is the default evaluator if none is specified. The solution must read the test cases from the standard input and print the output to the standard output.

The following options are further configurable:

  • CustomScorer()

    By default, the output will be checked with the default diff program, unless a custom scorer is specified. See the Helper programs section on how to write a scorer.

  • NoOutput()

    If the problem is using a custom scorer and it does not depend on test case output of any test case, then this option can be enabled. If enabled, then .out files will not be generated, and it is not allowed to specify Output() in sample test cases.

Interactive

Enabled by calling InteractiveEvaluator(). The solution will participate in a 2-way communication with a special program called communicator, which will ultimately print the verdict of the solution. See the Helper programs section on how to write a communicator.


Helper programs
Scorer

A scorer is a program which decides the verdict of a test case. It will receive the following arguments:

  • argv[1]: test case input filename
  • argv[2]: test case output filename
  • argv[3]: contestant’s produced output filename

It must print the test case verdict to the standard output, which is a line consisting of either:

  • AC: indicates that the contestant’s output is correct.

  • WA: indicates that the contestant’s output is incorrect.

  • OK: indicates that the contestant’s output is partially correct. The second line must contain a floating-point number denoting the points. For example:

    OK
    9
    

See also local grading verdicts on how the verdicts will be interpreted during local grading.

The scorer must be compiled prior to test cases generation/local grading, and the execution command should be passed to the runner program as the --scorer option. For example:

./runner grade --solution=./solution_alt --scorer=./my_custom_scorer

The default scorer command is ./scorer if not specified.

Here is an example scorer which gives AC if the contestant’s output differs not more than 1e-9 from the official output.

#include <bits/stdc++.h>
using namespace std;

int wa() {
    cout << "WA" << endl;
    return 0;
}

int ac() {
    cout << "AC" << endl;
    return 0;
}

int main(int argc, char* argv[]) {
    ifstream tc_in(argv[1]);
    ifstream tc_out(argv[2]);
    ifstream con_out(argv[3]);

    double tc_ans;
    tc_out >> tc_ans;

    double con_ans;
    if (!(con_out >> con_ans)) {
        return wa();
    }

    if (abs(tc_ans - con_ans) < 1e-9) {
        return ac();
    } else {
        return wa();
    }
}
Communicator

A communicator is a program which performs 2-way communication with the solution program, and then decides the verdict. It will receive the following (only) argument:

  • argv[1]: test case input filename

During the communication, the communicator can read the solution program’s output from the standard input, and can give input to the solution program by writing to the standard output. Make sure the communicator flushes after every time it writes output. Ultimately, the communicator must print the test case verdict to the standard error, with the same format as a scorer as described in the previous section.

The communicator must be compiled prior to local grading, and the execution command should be passed to the runner program as the --communicator option. For example:

./runner grade --solution=./solution_alt --communicator=./my_communicator

The default communicator command is ./communicator if not specified.

Here is an example communicator program in a typical binary search problem.

#include <bits/stdc++.h>
using namespace std;

int ac() {
    cerr << "AC" << endl;
    return 0;
}

int wa() {
    cerr << "WA" << endl;
    return 0;
}

int main(int argc, char* argv[]) {
    ifstream tc_in(argv[1]);

    int N;
    tc_in >> N;

    int guesses_count = 0;

    while (true) {
        int guess;
        cin >> guess;

        guesses_count++;

        if (guesses_count > 10) {
            return wa();
        } else if (guess < N) {
            cout << "TOO_SMALL" << endl;
        } else if (guess > N) {
            cout << "TOO_LARGE" << endl;
        } else {
            return ac();
        }
    }
}

Constraints

Constraints are conditions that must be satisfied by the input variables. The conditions will be verified on each test case. If any of the constraints is not satisfied, then the generation is considered to fail on that test case. There will be a nice error message explaining which constraints are not satisfied.

The truth value of a constraint must depend only on the values of the input variables in order for it to be a semantically correct constraint.

Constraints can be specified in the Constraints() method of the problem spec class.

void Constraints() {
    // list of constraint definitions
}

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 <= 1000). “1 ≤ A, B ≤ 1,000” translates into two specifications: CONS(1 <= A && A <= 1000) and CONS(1 <= B && B <= 1000). “1 ≤ AB ≤ 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.

See also

Subtasks

The concept of subtasks was first formally introduced in IOI 2010. The idea is basically to split a problem into two or more smaller problems with gradually increasing difficulty, and assign them different points.

For example:

Subtask 1 (20 points)
- N = 1
- 1 ≤ K ≤ 100

Subtask 2 (20 points)
- 1 ≤ N ≤ 100
- K = 1

Subtask 3 (60 points)
- 1 ≤ N ≤ 100
- 1 ≤ K ≤ 100

In this type type of problem, you won’t be writing a Constraints() method. Instead, you will be writing SubtaskX() methods, where X is the subtask number.

Note

As of this version, you can define up to 25 subtasks: Subtask1() .. Subtask25().


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. Points for each subtask can be given using Points() method, that takes a floating-point number argument as the points.

Thus, the above example can be implemented as:

void Subtask1() {
    Points(20);

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

void Subtask2() {
    Points(20);

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

void Subtask3() {
    Points(60);

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

Global constraints

It is possible to specify a set of constraints that apply to every subtask, via the Constraints() method. For example, we can extract common constraints in the above example as follows:

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

void Subtask1() {
    Points(20);

    CONS(N == 1);
}

void Subtask2() {
    Points(20);

    CONS(K == 1);
}

void Subtask3() {
    Points(60);

    // no additional constraints
}

Test groups

If your problem has subtasks, you will be writing test groups, not test cases.

Test cases

Technically, a test case is a particular state of input variables, with the corresponding correct values for the output variables. If the values of the input variables conform to each of the specified constraints, then the test case is considered valid, otherwise it is invalid.

Test cases are defined in the TestCases() method of the test spec class.

void TestCases() {
    // list of test case definitions
}

A sample test case is similar to a test case, except that it is not secret and appears in the problem statement. Sample test cases are defined in the SampleTestCaseX() methods of the test spec class, where X is the sample test case number.

void SampleTestCase1() {
    // sample test case I/O definitions
}

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() {
    for (int i = 0; i < N; i++) {
        parent.push_back(i-1);
    }
}

Note

The values of input variables before each test case are undefined, and may contain leftover computation from previous test cases. See Test case lifecycle on how to initialize them.

You can also use for-loop construct for assigning some input variables. This is usually done if you want to exhaust all valid possibilities of some input variables. For example:

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

We recommend not using this style unless absolutely necessary.

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, sum_1.in, sum_1.out.


Sample test case definition

Note

As of this version, you can define up to 25 sample test casses: SampleTestCase1() .. SampleTestCase25().

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 Input() and Output() calls as follows (note the {} braces):

void SampleTestCase1() {
    Input({
        "<line 1>",
        "<line 2>",
        ...
    });
    Output({
        "<line 1>",
        "<line 2>",
        ...
    });
}

The supplied output must match with the actual output produced by the solution program.

For example, this sample test case:

Input:

3 4
1 2 3

Output:

2
100
200

can be translated to:

void SampleTestCase1() {
    Input({
        "3 4",
        "1 2 3"
    });
    Output({
        "2",
        "100",
        "200"
    });
}

Note

The Output() part of a sample test case definition is optional, and if not present, the solution will be run to produce the output. However, it is only for easier migration from tcframe 0.x. You should always specify both input and output, so that you are sure you are typing the output correctly in the problem statement by only looking at the spec file (no need to check with the actual produced output file).

Of course, if NoOutput() is enabled (see Problem Styles), then Output() is not allowed to be specified.

If your problem has subtasks, you also need to assign each sample test case to a set of subtasks, by calling Subtasks() at the beginning of each SampleTestCaseX() with the set of subtask numbers, as follows.

void SampleTestCase1() {
    Subtasks({2, 3});
    Input({
        "3 4",
        "1 2 3"
    });
    Output({
        "2",
        "100",
        "200"
    });
}

Each sample test case 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, sum_sample_1.in, sum_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 randomArray() {
    for (int i = 0; i < N; i++) {
        A.push_back(rnd.nextInt(1000000));
    }
}

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


Test case lifecycle

Note

This section only applies to official test cases. It is not applicable to sample test cases.

tcframe declares two methods that you can implement in the test spec class: BeforeTestCase() and AfterTestCase() to hook up additional logic to run during a test case generation. For each test case, the following things will happen in order:

  1. BeforeTestCase() is executed.
  2. The assignments/method calls inside CASE() are executed.
  3. AfterTestCase() is executed.
  4. Input variable values are printed according to the input format.
BeforeTestCase()

This method can be implemented to initialize input variables. For example, if you have vectors as input variables, you will want to initialize them first before calling e.g. randomArray() inside CASE() macro.

void BeforeTestCase() {
    parent.clear();
    A.clear();
}
AfterTestCase()

You may 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 spec 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 the test spec class.)

This can be achieved by implementing AfterTestCase(), transforming the vector P[] into a pair of vectors (U[], V[]) there.

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

Test groups

A test group is a set of test cases that are assigned/included to the same set of subtasks. If your problem has subtasks, then instead of writing TestCases() method, you will be writing TestGroupX() methods instead, where X is the test group number.

For the whole test cases to be strong, a test case should be assigned in multiple subtasks if possible. In other words, several subtasks may share some test cases. In tcframe, a test case must be assigned to a subtask if (and only if) it satisfies the constraints of that subtask.


Designing test groups

In this example, we will use this subtasking scheme:

Subtask 1
- N = 1
- 1 ≤ K ≤ 100

Subtask 2
- 1 ≤ N ≤ 100
- K = 1

Subtask 3
- 1 ≤ N ≤ 100
- 1 ≤ K ≤ 100

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:

_images/venn-diagram.png

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 Subtasks(S) method as the first statement, where S is a set of subtask numbers. The remaining bodies of test group methods are test case definitions. For the above example:

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

Note

As of this version, you can define up to 25 test groups: TestGroup1() .. TestGroup25().

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, sum_2_3.in, sum_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 local grading feature, each test case will be executed only once. The result is shared for every subtask it is assigned to.

Multiple test cases per file

tcframe supports ICPC-style test cases, where there are multiple test cases in a single file, which preceded by a single line containing the test case count.

The following is how tcframe will combine multiple test cases into individual files:

  • All sample test cases in SampleTestCaseX() methods will be combined into <slug>_sample.{in,out}.
  • All test cases in TestCases() method will be combined into <slug>.{in,out}.
  • All test cases in each of the TestGroupX() method will be combined into <slug>_<X>.{in,out}.

You need to apply the following changes in order to make a spec file ICPC-style.


Problem spec class

Add the following as members of ProblemSpec:

Input variable counter

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

protected:
    int T;

    ...

Then, write a method MultipleTestCasesConfig(), and call the Counter() method with T as the argument.

void MultipleTestCasesConfig() {
    Counter(T);
}
Output prefix

You can also specify the prefix to be prepended before the output of each test case in a file. For example, in ICPC, usually each test case in the output must be prepended by Case #X:, where X is the test case number in that file. This can be achieved by calling OutputPrefix() method in MultipleTestCasesConfig(), with the prefix string as the argument. The string may contain %d which will be replaced with the actual test case number. For example:

void MultipleTestCasesConfig() {
    Counter(T);
    OutputPrefix("Case #%d: ");
}
Input format

The input format 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

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

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

Test spec class

No changes are necessary. You also don’t need to prepend the output prefix in sample test case outputs. Write the sample test cases as if they are not combined into a single file.


Solution program

Although the input/output format only specifies a single test case, you must write the solution as if the test cases are already combined. In other words, the solution will read the number of test cases in the first line, then that many of test cases, and must output the answer of each test case.

Example

Here is our sample sum problem in ICPC-style.

#include <tcframe/spec.hpp>
using namespace tcframe;

class ProblemSpec : public BaseProblemSpec {
protected:
    int T;
    int A, B;
    int sum;

    void InputFormat() {
        LINE(A, B);
    }

    void OutputFormat() {
        LINE(sum);
    }

    void GradingConfig() {
        TimeLimit(1);
        MemoryLimit(64);
    }

    void MultipleTestCasesConfig() {
        Counter(T);
        OutputPrefix("Case #%d: ");
    }

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

    void Constraints() {
        CONS(1 <= A && A <= 1000);
        CONS(1 <= B && B <= 1000);
    }
};

class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    void SampleTestCase1() {
        Input({
            "4 6"
        });
        Output({
            "10"
        });
    }

    void TestCases() {
        CASE(A = 1, B = 1);
        CASE(A = 1000, B = 1000);
        CASE(A = 42, B = 100);
        CASE(A = rnd.nextInt(1, 1000), B = rnd.nextInt(1, 1000));
    }
};

Local grading

tcframe allows you to grade solutions locally, on your machine.

Before grading a solution, you must have already generated the test cases:

./runner

Then, you can “grade” a solution, by executing:

./runner grade [--solution=<solution-command>]

where <solution-command> is the command for executing the solution. If it is omitted, the default is ./solution.

For example, suppose you have written a problem package for a problem. Your friend also has written an alternate solution to the problem, and he wants to check whether his solution agrees with yours. Let’s assume that his solution file is solution_alt.cpp. Compile it into solution_alt, place it in the problem package, and then run

./runner grade --solution=./solution_alt

The verdicts of each test case, each subtask (if any), as well as the overall verdict will be shown, as described below.

Verdicts

A verdict consists of the verdict status and optionally verdict points.

The recognized statuses, from the best to the worst, are as follows:

Accepted
The output produced by the solution is correct.
OK
The output produced by the solution is partially correct.
Wrong Answer
The output produced by the solution is incorrect. By default, the diff will be shown, truncated to the first 10 lines.
Runtime Error
The solution crashed or used memory above the limit, if specified.
Time Limit Exceeded
The solution did not stop within the time limit, if specified.
Internal Error
Custom scorer / communicator (if any) crashed or did not give a valid verdict.
Test case verdicts

The verdict of each test case will be shown. For OK statuses, the points (given by the scorer) will be also shown.

Subtask verdicts

If the problem has subtasks, the verdict of each subtask will be shown as well. The verdict of a subtask is the combination of:

  • status: the worst status of test case verdicts in the subtask
  • points:
    • the subtask points (assigned via Points()), if all test case verdicts in the subtask are Accepted,
    • the minimum points of OK verdicts in the subtask, if at least one test case verdict is OK and the rest are Accepted, or
    • 0, otherwise.
Overall verdict

Finally, the overall verdict is as follows.

For problem without subtasks:

  • status: the worst test case verdict status
  • points: the sum of test case verdict points, where:
    • an Accepted status will be given 100 / (number of test cases) points
    • an OK status will be given its own points
    • any other status will be given 0 points

For problem with subtasks:

  • status: the worst subtask verdict status
  • points: the sum of subtask verdict points
Sample local grading output

Here is a sample output of a local grading for problems without subtasks.

Local grading with solution command: './solution_alt'...

[ SAMPLE TEST CASES ]
  k-product_sample_1: Accepted

[ OFFICIAL TEST CASES ]
  k-product_1: Accepted
  k-product_2: Accepted
  k-product_3: OK [21]
  k-product_4: Wrong Answer
    * scorer Diff:
(expected) [line 01]    11
(received) [line 01]    12

[ VERDICT ]
  Wrong Answer [71]

and here is for problems with subtasks.

Local grading with solution command: './solution_alt'...

[ SAMPLE TEST CASES ]
  k-product_sample_1: Accepted

[ TEST GROUP 1 ]
  k-product_1_1: Accepted

[ TEST GROUP 2 ]
  k-product_2_1: Accepted
  k-product_2_2: Accepted
  k-product_2_3: Accepted

[ TEST GROUP 3 ]
  k-product_3_1: Accepted
  k-product_3_2: Wrong Answer
    * scorer: Diff:
(expected) [line 01]    11
(received) [line 01]    12

  k-product_3_3: Accepted

[ TEST GROUP 4 ]
  k-product_4_1: Accepted
  k-product_4_2: Accepted
  k-product_4_3: Accepted
  k-product_4_4: Accepted
  k-product_4_5: Accepted
  k-product_4_6: Runtime Error
    * Execution of solution failed:
      - Exit code: 1
      - Standard error:

[ SUBTASK VERDICTS ]
  Subtask 1: Accepted [40]
  Subtask 2: Wrong Answer [0]
  Subtask 3: Runtime Error [0]

[ VERDICT ]
  Runtime Error [40]

This local grading feature is useful for creating “unit tests” for your test cases. For each problem, you can write many solutions with different intended results. For example, solution_123.cpp should pass subtasks 1 - 3; solution_12.cpp should pass subtasks 1 and 2 but not subtask 3, etc.

Brief mode

You can pass an additional --brief argument to make the output concise. This is primarily intended to be consumed by scripts instead of human eyes.

The first line of the output contains the overall the verdict in the following format:

<status code> <points>

where the status code mapping is:

  • AC: Accepted
  • OK: OK
  • WA: Wrong Answer
  • RTE: Runtime Error
  • TLE: Time Limit Exceeded
  • ERR: Internal Error

If the problem has subtasks, the subtask verdicts will be output in the following lines, one line per subtask verdict ordered by subtask number, in the same format as above.

The sample outputs from the previous sections would become the following using --brief argument:

WA 71

and

RTE 40
AC 40
WA 0
RTE 0
Notes

Internally, tcframe uses ulimit to limit the time and memory used when running the solution. Unfortunately, there is no easy way to restrict memory limit on OS X, so the memory limit will be always ignored when using this feature on OS X.

Tutorials

Here, you can find case studies and best practices on how to write your spec files. It is expected that you have already read the getting started guide before reading through the tutorials.

Tutorial 1: Best Pair

In this tutorial, you will learn how to write a generator for a simple yet tricky problem, called Best Pair. We will focus on the general idea of how to come up with a strong set of test cases.

Here is the complete problem statement:


Best Pair
Time Limit: 1 second
Memory Limit: 64 MB

Description
You are given an array A consisting of N integers. What is the maximum product (multiplication) of any pair of integers in A?

Input Format
The first line contains a single integer N. The next line contains N space-separated elements of A.

Output Format
A single line containing the maximum product.

Sample Input
4
4 -2 3 1

Sample Output
12

Constraints
2 ≤ N ≤ 100,000
-1,000,000 ≤ A[i] ≤ 1,000,000


Cool, let’s now start writing generator for this problem. The conventional steps to do this are:

  1. Prepare the problem package.
  2. Write the solution.
  3. Write the problem spec.
  4. Write the test spec.

We will tackle each step in more details below.

Note

The complete source files for this tutorial can also be found here.


Preparing problem package

First, we need to come up with a slug for this problem. Let’s call it best-pair.

Now, create a directory best-pair in your system. For example, create it in your home directory (~/best-pair). We will then store all files related to this problem there.


Writing solution

Although the solution can actually be written any time during this process, we recommend doing it before writing the spec. Why? Sometimes, after (trying) to write the solution, you will realize that:

  • Some constraints make the problem impossible to solve.
  • You find a much simpler solution that makes the problem too easy and not suitable for you contest.
  • The problem is actually impossible to solve.

Thus, you will save your time from writing the spec if the problem is actually invalid as explained above.

Anyway, let’s now solve this problem. The solution is simple: it is the maximum of the following:

  • product of two largest non-negative elements
  • product of two smallest negative elements
  • (tricky) product of the largest negative element and the smallest positive element

Here is a sample C++ implementation of the above idea. It is not the fastest solution, but should suffice for the purposes of this tutorial.

best-pair/solution.cpp:

#include <bits/stdc++.h>
using namespace std;

int N;
vector<long long> pos;
vector<long long> neg;

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        long long x;
        cin >> x;
        if (x >= 0) {
            pos.push_back(x);
        } else {
            neg.push_back(x);
        }
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());

    long long res = LLONG_MIN;
    if (pos.size() >= 2) {
        res = max(res, pos[pos.size()-1] * pos[pos.size()-2]);
    }
    if (neg.size() >= 2) {
        res = max(res, neg[0] * neg[1]);
    }
    if (!neg.empty() && !pos.empty()) {
        res = max(res, neg[neg.size()-1] * pos[0]);
    }

    cout << res << endl;
}

Writing problem spec

The following is a problem spec that is derived directly from the problem statement. Note that we are using a private method eachElementBetween() to represent the constraint -1,000,000 ≤ A[i] ≤ 1,000,000. Everything else should be straightforward.

best-pair/spec.cpp:

#include <bits/stdc++.h>
#include <tcframe/spec.hpp>

using namespace std;
using namespace tcframe;

class ProblemSpec : public BaseProblemSpec {
protected:
    int N;
    vector<long long> A;
    long long res;

    void InputFormat() {
        LINE(N);
        LINE(A % SIZE(N));
    }

    void OutputFormat() {
        LINE(res);
    }

    void GradingConfig() {
        TimeLimit(1);
        MemoryLimit(64);
    }

    void Constraints() {
        CONS(2 <= N && N <= 100000);
        CONS(eachElementBetween(A, -1000000, 1000000));
    }

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

Writing test spec

This is the most challenging part!

First, write the sample test cases as written in the problem statement as follows. As an advice, sample test cases should not reveal all trickiness of the problem. In the sample below, the answer is the most obvious case: the product of two largest non-negative elements of A.

best-pair/spec.cpp (continued):

class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    void SampleTestCase1() {
        Input({
            "4",
            "4 -2 3 1"
        });
        Output({
            "12"
        });
    }
};

Then, let’s move on to the actual, official test cases. Firstly, we will implement the BeforeTestCase() method to initialize the vector A before every test case, as follows.

void BeforeTestCase() {
    A.clear();
}

Next, the actual test cases. We should come up with a good set of test cases that does both the following:

  • accepting correct solutions, and
  • rejecting incorrect solutions (important!)

Recall that the solution we’ve written above considers 3 different cases. Let’s write a test case that covers each case.

  1. The answer is the product of two largest non-negative elements

    CASE(N = 5, A = {-2, -1, 2, 3, 0});

  2. The answer is the product of two smallest negative elements

    CASE(N = 5, A = {3, 4, -1, -3, -5});

  3. The answer is the product of the largest negative element and the smallest positive element

    CASE(N = 2, A = {2, -1});

    Note that the above case is only possible with N = 2.

There are also several cases for which the answer has some interesting properties, as follows.

  1. The answer is 0

    This is the case when everything but one is zero, or everything is zero.

    CASE(N = 4, A = {0, 2, 0, 0});

    CASE(N = 4, A = {0, 0, 0, 0});

  2. The answer is the maximum possible answer

    This will reject solutions that do not use 64-bit integers.

    CASE(N = 3, A = {1000000, -1, 1000000});

  3. The answer is the minimum possible answer

    This will reject solutions that do not use 64-bit integers as well.

    CASE(N = 2, A = {-1000000, 1000000});

    Note that (3) and (6) will reject solutions which initialize the answer to 0 (instead of a very small negative integer).

So far, we have considered various cases for which the answer has some properties. Let’s now consider cases for which the input itself has some interesting properties.

  1. All elements are positive/negative

    This will reject solutions which do not properly handle empty collections for positive/negative elements.

    CASE(N = 4, A = {1, 2, 3, 4});

    CASE(N = 4, A = {-1, -2, -3, -4});

  2. All elements are zero

    This can probably reject solutions which separate zeroes for some reasons (it’s actually unnecessary).

    This is already covered by (4).

  3. N = 2

    This is the smallest possible value for N. Already covered by (3) and (6).

  4. Random values for elements of A

    It’s always good idea to include randomized input to the test data when the input space is very large (which should be true for most problems).

    The randomized elements of A can be generated using a private function, as follows:

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

    (Note that at the beginning of the above method, N will have been set to a value from CASE(), and A will have been cleared by BeforeTestCase().)

    The above is good enough for this problem. However, it is nicer if we can somehow “tune” some properties of the randomization. For example, we can have parameters denoting the number of desired positive and negative numbers in A:

    void randomElements(int numPos, int numNeg) {
        assert(numPos + numNeg <= N);
    
        for (int i = 0; i < numPos; i++) {
            A.push_back(rnd.nextInt(1, 1000000));
        }
        for (int i = 0; i < numNeg; i++) {
            A.push_back(rnd.nextInt(-1000000, -1));
        }
        for (int i = 0; i < N-numPos-numNeg; i++) {
            A.push_back(0);
        }
    
        rnd.shuffle(A.begin(), A.end());
    }
    

    Again, the above tuning is not really necessary for this problem, as most tricky cases have been covered by previous hand-made test cases. However, for the purpose of learning, we will still use the tuning.

    It is not the only tuning that we can do. Other options include:

    • Tuning the range of possible values of the randomized element. For example, if we want the elements to be randomized between just 1 and 100.
    • Same as above, but also tuning the percentage of the tuned range. For example, if we want the elements to be totally randomized, except a quarter of them, which should be between 1 and 100.
    • etc.

    All right, now use this function in CASE(), with various arguments to it (and various values for N), for example as follows.

    CASE(N = 10, randomElements(5, 5));

    CASE(N = 100, randomElements(20, 50));

    CASE(N = 1000, randomElements(300, 300));

    CASE(N = 10000, randomElements(2500, 6000));

  5. N = 100000

    The maximum value of N. This will reject solutions that use array with size less than 100,000.

    CASE(N = 100000, randomElements(50000, 50000));

    CASE(N = 100000, randomElements(10000, 80000));

    CASE(N = 100000, randomElements(80000, 10000));

There are possibly some other cases that we can explore, but for now, this set of test cases should be strong enough for our problem!


Putting it all together

Here is the complete spec file for our Best Pair problem.

#include <bits/stdc++.h>
#include <tcframe/spec.hpp>

using namespace std;
using namespace tcframe;

class ProblemSpec : public BaseProblemSpec {
protected:
    int N;
    vector<long long> A;
    long long res;

    void InputFormat() {
        LINE(N);
        LINE(A % SIZE(N));
    }

    void OutputFormat() {
        LINE(res);
    }

    void GradingConfig() {
        TimeLimit(1);
        MemoryLimit(64);
    }

    void Constraints() {
        CONS(2 <= N && N <= 100000);
        CONS(eachElementBetween(A, -1000000, 1000000));
    }

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

class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    void SampleTestCase1() {
        Input({
            "4",
            "4 -2 3 1"
        });
        Output({
            "12"
        });
    }

    void BeforeTestCase() {
        A.clear();
    }

    void TestCases() {
        // The answer is the product of two largest non-negative elements
        CASE(N = 5, A = {-2, -1, 2, 3, 0});

        // The answer is the product of two smallest negative elements
        // The smallest possible value for N
        CASE(N = 5, A = {3, 4, -1, -3, -5});

        // The answer is the product of the largest negative element and the smallest positive element
        CASE(N = 2, A = {2, -1});

        // The answer is 0
        CASE(N = 4, A = {0, 2, 0, 0});
        CASE(N = 4, A = {0, 0, 0, 0});

        // The answer is the maximum possible answer
        CASE(N = 3, A = {1000000, -1, 1000000});

        // The answer is the minimum possible answer
        CASE(N = 2, A = {-1000000, 1000000});

        // All elements are positive/negative
        CASE(N = 4, A = {1, 2, 3, 4});
        CASE(N = 4, A = {-1, -2, -3, -4});

        // Random values for elements of A
        CASE(N = 10, randomElements(5, 5));
        CASE(N = 100, randomElements(20, 50));
        CASE(N = 1000, randomElements(300, 300));
        CASE(N = 10000, randomElements(2500, 6000));

        // The maximum value of N
        CASE(N = 100000, randomElements(50000, 50000));
        CASE(N = 100000, randomElements(10000, 80000));
        CASE(N = 100000, randomElements(80000, 10000));
    }

private:
    void randomElements(int numPos, int numNeg) {
        assert(numPos + numNeg <= N);

        for (int i = 0; i < numPos; i++) {
            A.push_back(rnd.nextInt(1, 1000000));
        }
        for (int i = 0; i < numNeg; i++) {
            A.push_back(rnd.nextInt(-1000000, -1));
        }
        for (int i = 0; i < N-numPos-numNeg; i++) {
            A.push_back(0);
        }

        rnd.shuffle(A.begin(), A.end());
    }
};

That’s it! The complete source files for this tutorial can also be found here.

Tutorial 2: Minimum Spanning Tree

In this tutorial, you will learn how to write a generator for a more complicated problem, called Minimum Spanning Tree with test groups. We will focus on the general idea of using test groups in tcframe.

Here is the complete problem statement:


Minimum Spanning Tree
Time Limit: 1 second
Memory Limit: 64 MB

Description
Given a weighted, connected graph G consisting of N nodes and M edges. The nodes are numbered from 0 to N - 1. You need to choose N - 1 out of those M edges such that the graph remains connected if we only consider the chosen edges. What is the minimum possible sum of the weight of the chosen edges?

Input Format
The first line contains two integers N and M separated by a space.
M lines follow. Each line contains three integers U, V, and W separated by a space, representing an edge connecting node U and V with weight W.

Output Format
A single line containing the minimum possible sum of the weight of the chosen edges.

Sample Input
3 3
0 1 2
1 2 3
2 0 4

Sample Output
5

Constraints for all subtasks
2 ≤ N ≤ 100,000
N - 1 ≤ M ≤ 100,000
0 ≤ U, V < N
1 ≤ W ≤ 1,000
The graph is connected
There is no edge connecting a node to itself

Subtask 1 (20 points)
M ≤ 20

Subtask 2 (30 points)
All W are equal

Subtask 3 (50 points)
No additional constraints


Since the steps of preparing the problem package and writing the solution are similar to the previous tutorial, we will not cover those steps in this tutorial. Instead, we will focus on writing the problem spec and test spec. Let’s use minimum-spanning-tree as the slug for this problem.


Writing problem spec

The following is a problem spec that is derived directly from the problem statement. We are using the same private method eachElementBetween() from the previous tutorial. We are adding another private method allAreEqual(). We are also adding several private methods for checking graph properties, namely noSelfLoop() (self loop is an edge connecting a node to itself) and isConnected(). These methods are very modular and we can always reuse them for another problem. However, note that the methods assume the nodes of the graph are 0-based, and several minor changes are needed if the nodes are 1-based.

Let’s focus on the syntax differences compared to the first tutorial. Note that we are using the method Constraints() to include the global constraints that applies to every subtask, and we are using SubtaskX() to include the constraints that apply to only those subtasks. Since Subtask3() does not have any additional constraints that are not included in the global constraints, we can simply just leave the method empty.

minimum-spanning-tree/spec.cpp:

#include <bits/stdc++.h>
#include <tcframe/spec.hpp>

using namespace std;
using namespace tcframe;

class ProblemSpec : public BaseProblemSpec {
protected:
    int N, M;
    vector<int> U, V, W;
    int res;

    void InputFormat() {
        LINE(N, M);
        LINES(U, V, W) % SIZE(M);
    }

    void OutputFormat() {
        LINE(res);
    }

    void GradingConfig() {
        TimeLimit(1);
        MemoryLimit(64);
    }

    void Constraints() {
        CONS(2 <= N && N <= 100000);
        CONS(N - 1 <= M && M <= 100000);
        CONS(eachElementBetween(U, 0, N - 1));
        CONS(eachElementBetween(V, 0, N - 1));
        CONS(eachElementBetween(W, 1, 1000));
        CONS(noSelfLoop(U, V));
        CONS(isConnected(N, U, V));
    }

    void Subtask1() {
        Points(20);

        CONS(M <= 20);
    }

    void Subtask2() {
        Points(30);

        CONS(allAreEqual(W));
    }

    void Subtask3() {
        Points(50);
    }

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

    bool allAreEqual(const vector<int>& v) {
        for (int x : v) {
            if (x != v[0]) {
                return false;
            }
        }
        return true;
    }

    bool noSelfLoop(const vector<int>& u, const vector<int>& v) {
        for (int i = 0; i < u.size(); i++) {
            if (u[i] == v[i]) {
                return false;
            }
        }
        return true;
    }

    bool isConnected(int n, const vector<int>& u, const vector<int>& v) {
        vector<bool> isVisited(n);
        vector<vector<int>> adj(n);
        for (int i = 0; i < u.size(); i++) {
            adj[u[i]].push_back(v[i]);
            adj[v[i]].push_back(u[i]);
        }
        int numNodesVisited = 0;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            if (isVisited[now]) {
                continue;
            }
            isVisited[now] = true;
            ++numNodesVisited;
            for (int v : adj[now]) {
                q.push(v);
            }
        }
        return numNodesVisited == n;
    }
};

Writing test spec

The first difference in the TestSpec class compared to the first tutorial is in the sample test cases declaration. We need to declare which subtasks will have this sample test case as one of their test cases. For the sample test case in the problem above, since M ≤ 20 and not all W are equal, then the sample test case will be included in subtask 1 and subtask 3.

minimum-spanning-tree/spec.cpp (continued):

class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    void SampleTestCase1() {
        Subtasks({1, 3});
        Input({
            "3 3",
            "0 1 2",
            "1 2 3",
            "2 0 4"
        });
        Output({
            "5"
        });
    }
};

The BeforeTestCase() has the same syntax compared to the previous tutorial. However, here we need to clear more vectors before every test case.

void BeforeTestCase() {
    U.clear();
    V.clear();
    W.clear();
}

Before creating the actual test cases, let us create the private helper methods that will help us in creating the actual test cases later. Similar to the private helper methods in ProblemSpec, these methods are very modular and we can always reuse them for another problem.

void randomWeight(int m, vector<int>& w, int minW = 1, int maxW = 1000) {
    for (int i = 0; i < m; i++) {
        w.push_back(rnd.nextInt(minW, maxW));
    }
}

void renumber(int n, vector<int>& u, vector<int>& v) {
    vector<int> permutation;
    for (int i = 0; i < n; i++) {
        permutation.push_back(i);
    }
    rnd.shuffle(permutation.begin(), permutation.end());
    for (int i = 0; i < u.size(); i++) {
        u[i] = permutation[u[i]];
        v[i] = permutation[v[i]];
    }
}

void randomTree(int n, vector<int>& u, vector<int>& v) {
    for (int i = 1; i < n; i++) {
        u.push_back(i);
        v.push_back(rnd.nextInt(0, i - 1));
    }
    renumber(n, u, v);
}

void randomGraph(int n, int m, vector<int>& u, vector<int>& v) {
    randomTree(n, u, v);
    while (u.size() < m) {
        int newU = rnd.nextInt(0, N - 2);
        int newV = rnd.nextInt(newU + 1, N - 1);
        u.push_back(newU);
        v.push_back(newV);
    }
}

Now, let us move on to the creation test cases itself. The actual test cases for a problem involving test groups are challenging. The first step is to draw the Venn diagram of the subtasks.

The properties of the subtasks of the above problem are :

  1. All test cases in subtask 1 and subtask 2 are also in subtask 3, and subtask 3 contains some other test cases that are neither in subtask 1 nor subtask 2.
  2. Some test cases are in both subtask 1 and subtask 2, and there are also test cases that are in subtask 1 but not in subtask 2, and there are also test cases that are in subtask 2 but not in subtask 2.

Therefore, the Venn diagram looks like this

_images/tutorial_2-venn_diagram.png

We need to define a test group for each of the regions in the Venn diagram. Therefore, we will have four test groups. Let us number it from 1 to 4 in the same order as the diagram above. Therefore, the four test groups will have the following constraints in addition to the global constraints:

  1. M ≤ 20 and all W are equal
  2. M ≤ 20 and not all W are equal
  3. M > 20 and all W are equal
  4. M > 20 and not all W are equal

For example, the test cases for the first test group can be something like this

void TestGroup1() {
    Subtasks({1, 2, 3});

    CASE(N = 2, M = 1, U = {0}, V = {1}, W = {1});
    CASE(N = 21, M = 20, randomTree(N, U, V), W.assign(M, 1000));
    CASE(N = 20, M = 20, randomGraph(N, M, U, V), W.assign(M, 1000));

    for (int i = 0; i < 5; i++) {
        CASE(N = rnd.nextInt(2, 21),
             M = rnd.nextInt(N - 1, 20),
             randomGraph(N, M, U, V),
             W.assign(M, rnd.nextInt(1, 1000)));
    }
}

It is a good practice to include the smallest case (M = 1) and the largest case (M = 20) satisfying the test group constraints. Since this test group is also included in subtask 2, we also need to make sure that all W are equal.

The second test group can be something like this

void TestGroup2() {
    Subtasks({1, 3});

    // We manually create a small test case where greedily choosing
    // the first N - 1 edges with smallest weight will create a cycle.
    CASE(N = 4, M = 4,
         U = {0, 1, 2, 0},
         V = {1, 2, 0, 3},
         W = {1, 1, 1, 2});

    CASE(N = 2, M = 2, U = {0, 1}, V = {1, 0}, W = {1, 2});
    CASE(N = 21, M = 20, randomTree(N, U, V), randomWeight(M, W));

    for (int i = 0; i < 5; i++) {
        CASE(N = rnd.nextInt(2, 21),
             M = rnd.nextInt(N - 1, 20),
             randomGraph(N, M, U, V),
             randomWeight(M, W));
    }
}

Since this test group is not included in subtask 2, it must not be the case that W are equal for all elements. Therefore, the smallest case for this test group is M = 2.

The third and fourth test groups can be created in a similar fashion. You can see the complete code containing the test specifications for the next test groups in the following section.


Putting it all together

Here is the complete spec file for our Minimum Spanning Tree problem.

#include <bits/stdc++.h>
#include <tcframe/spec.hpp>

using namespace std;
using namespace tcframe;

class ProblemSpec : public BaseProblemSpec {
protected:
    int N, M;
    vector<int> U, V, W;
    int res;

    void InputFormat() {
        LINE(N, M);
        LINES(U, V, W) % SIZE(M);
    }

    void OutputFormat() {
        LINE(res);
    }

    void GradingConfig() {
        TimeLimit(1);
        MemoryLimit(64);
    }

    void Constraints() {
        CONS(2 <= N && N <= 100000);
        CONS(N - 1 <= M && M <= 100000);
        CONS(eachElementBetween(U, 0, N - 1));
        CONS(eachElementBetween(V, 0, N - 1));
        CONS(eachElementBetween(W, 1, 1000));
        CONS(noSelfLoop(U, V));
        CONS(isConnected(N, U, V));
    }

    void Subtask1() {
        Points(20);

        CONS(M <= 20);
    }

    void Subtask2() {
        Points(30);

        CONS(allAreEqual(W));
    }

    void Subtask3() {
        Points(50);
    }

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

    bool allAreEqual(const vector<int>& v) {
        for (int x : v) {
            if (x != v[0]) {
                return false;
            }
        }
        return true;
    }

    bool noSelfLoop(const vector<int>& u, const vector<int>& v) {
        for (int i = 0; i < u.size(); i++) {
            if (u[i] == v[i]) {
                return false;
            }
        }
        return true;
    }

    bool isConnected(int n, const vector<int>& u, const vector<int>& v) {
        vector<bool> isVisited(n);
        vector<vector<int>> adj(n);
        for (int i = 0; i < u.size(); i++) {
            adj[u[i]].push_back(v[i]);
            adj[v[i]].push_back(u[i]);
        }
        int numNodesVisited = 0;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            if (isVisited[now]) {
                continue;
            }
            isVisited[now] = true;
            ++numNodesVisited;
            for (int v : adj[now]) {
                q.push(v);
            }
        }
        return numNodesVisited == n;
    }
};

class TestSpec : public BaseTestSpec<ProblemSpec> {
protected:
    void SampleTestCase1() {
        Subtasks({1, 3});
        Input({
            "3 3",
            "0 1 2",
            "1 2 3",
            "2 0 4"
        });
        Output({
            "5"
        });
    }

    void BeforeTestCase() {
        U.clear();
        V.clear();
        W.clear();
    }

    void TestGroup1() {
        Subtasks({1, 2, 3});

        CASE(N = 2, M = 1, U = {0}, V = {1}, W = {1});
        CASE(N = 21, M = 20, randomTree(N, U, V), W.assign(M, 1000));
        CASE(N = 20, M = 20, randomGraph(N, M, U, V), W.assign(M, 1000));

        for (int i = 0; i < 5; i++) {
            CASE(N = rnd.nextInt(2, 21),
                 M = rnd.nextInt(N - 1, 20),
                 randomGraph(N, M, U, V),
                 W.assign(M, rnd.nextInt(1, 1000)));
        }
    }

    void TestGroup2() {
        Subtasks({1, 3});

        // We manually create a small test case where greedily choosing
        // the first N - 1 edges with smallest weight will create a cycle.
        CASE(N = 4, M = 4,
             U = {0, 1, 2, 0},
             V = {1, 2, 0, 3},
             W = {1, 1, 1, 2});

        CASE(N = 2, M = 2, U = {0, 1}, V = {1, 0}, W = {1, 2});
        CASE(N = 21, M = 20, randomTree(N, U, V), randomWeight(M, W));

        for (int i = 0; i < 5; i++) {
            CASE(N = rnd.nextInt(2, 21),
                 M = rnd.nextInt(N - 1, 20),
                 randomGraph(N, M, U, V),
                 randomWeight(M, W));
        }
    }

    void TestGroup3() {
        Subtasks({2, 3});

        CASE(N = 2, M = 21, randomGraph(N, M, U, V), W.assign(M, rnd.nextInt(1, 1000)));
        CASE(N = 100000, M = 99999, randomGraph(N, M, U, V), W.assign(M, 1000));
        CASE(N = 100000, M = 100000, randomGraph(N, M, U, V), W.assign(M, 1000));

        for (int i = 0; i < 5; i++) {
            CASE(N = rnd.nextInt(2, 100000),
                 M = rnd.nextInt(max(N - 1, 21), 100000),
                 randomGraph(N, M, U, V),
                 W.assign(M, rnd.nextInt(1, 1000)));
        }
    }

    void TestGroup4() {
        Subtasks({3});

        CASE(N = 2, M = 21, randomGraph(N, M, U, V), randomWeight(M, W));
        CASE(N = 100000, M = 99999, randomGraph(N, M, U, V), randomWeight(M, W));
        CASE(N = 100000, M = 100000, randomGraph(N, M, U, V), randomWeight(M, W));

        for (int i = 0; i < 5; i++) {
            CASE(N = rnd.nextInt(2, 100000),
                 M = rnd.nextInt(max(N - 1, 21), 100000),
                 randomGraph(N, M, U, V),
                 randomWeight(M, W));
        }
    }

private:
    void randomWeight(int m, vector<int>& w, int minW = 1, int maxW = 1000) {
        for (int i = 0; i < m; i++) {
            w.push_back(rnd.nextInt(minW, maxW));
        }
    }

    void renumber(int n, vector<int>& u, vector<int>& v) {
        vector<int> permutation;
        for (int i = 0; i < n; i++) {
            permutation.push_back(i);
        }
        rnd.shuffle(permutation.begin(), permutation.end());
        for (int i = 0; i < u.size(); i++) {
            u[i] = permutation[u[i]];
            v[i] = permutation[v[i]];
        }
    }

    void randomTree(int n, vector<int>& u, vector<int>& v) {
        for (int i = 1; i < n; i++) {
            u.push_back(i);
            v.push_back(rnd.nextInt(0, i - 1));
        }
        renumber(n, u, v);
    }

    void randomGraph(int n, int m, vector<int>& u, vector<int>& v) {
        randomTree(n, u, v);
        while (u.size() < m) {
            int newU = rnd.nextInt(0, N - 2);
            int newV = rnd.nextInt(newU + 1, N - 1);
            u.push_back(newU);
            v.push_back(newV);
        }
    }
};

That’s it! The complete source files for this tutorial can also be found here.

API Reference


Problem spec

ProblemSpec must inherit tcframe::BaseProblemSpec:

class ProblemSpec : public BaseProblemSpec {};

Except for private helper functions, every member of ProblemSpec listed below must be protected.


Input/output variables

Defined as instance member variables of ProblemSpec, which will be referenced in other methods of ProblemSpec and TestSpec.

There are three supported types of variables:

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. Arrays (T[]) are not supported.
Matrix
std::vector<std::vector<T>>, where T is a scalar type as defined above. 2D arrays (T[][]) are not supported.

Example:

class ProblemSpec : public BaseProblemSpec {
protected:
    int A, B;
    vector<int> parent;
    vector<vector<int>> values;
};

Input/output formats
virtual void InputFormat() = 0;

Defines the input format. It is mandatory.

virtual void BeforeOutputFormat() {}

Executed right before the produced output is validated against the output format(s). See BeforeOutputFormat() for more details.

virtual void OutputFormat() {}

virtual void OutputFormat1() {}
virtual void OutputFormat2() {}
// ...
virtual void OutputFormat5() {}

Defines the possible output format(s). If there is only one output format, only OutputFormat() can be specified, otherwise multiple OutputFormatX() should be specified.

Defining format

The following macros are exposed to define input/output formats:

EMPTY_LINE()

Defines an empty line.

RAW_LINE(string variable name)

Defines a line of raw string. The variable must be of std::string type.

Example:

void InputFormat() {
    RAW_LINE(S);
}

With S = “Hello, world!”, the above format will produce:

Hello, world!
RAW_LINES(vector of string variable name)
RAW_LINES(vector of string variable name) % SIZE(number of elements)

Defines multiple lines, each consisting of raw string. The variable must be of std::vector<std::string> type.

If the size is not given, then this must be the last segment in the I/O format.

Example:

void InputFormat() {
    RAW_LINES(X) % SIZE(2);
    RAW_LINES(Y);
}

With X = {“Hello, world!”, “Happy new year.”}, Y = {“lorem”, “ipsum”, “dolor sit amet”}, the above format will produce:

Hello, world!
Happy new year.
lorem
ipsum
dolor sit amet
LINE(comma-separated elements)

Defines a single line containing space-separated scalar or vector variables. In case of vector variables, the elements are separated by spaces as well.

element is one of:

  • <scalar variable name>.
  • <vector variable name> % SIZE(<number of elements>). The number of elements can be a constant or a scalar variable.
  • <vector variable name>. Here, the number of elements is unspecified. This kind of element must occur last in a line segment, if any. Elements will be considered until new line is found.

Example:

void InputFormat() {
    LINE(N);
    LINE(A % SIZE(3), B);
    LINE(M, C % SIZE(M));
}

With N = 2, A = {1, 2, 3}, B = {100, 200, 300, 400}, M = 2, C = {7, 8}, the above format will produce:

2
1 2 3 100 200 300 400
2 7 8
LINES(comma-separated vector/matrix variable names)
LINES(comma-separated vector/matrix variable names) % SIZE(number of elements)

Defines multiple lines, each consisting of space-separated elements of given vector/matrix variables.

If the size is not given, this must be the last segment in the I/O format.

Example:

void InputFormat() {
    LINES(V) % SIZE(2);
    LINES(X, Y) % SIZE(N);
    LINES(Z);
}

With V = {1, 2}, X = {100, 110, 120}, Y = {200, 210, 220} N = 3, Z = {1, 2, 3, 4} the above format will produce:

1
2
100 200
110 210
120 220
1
2
3
4

If a matrix variable is given, it must occur as the last argument, and the number of rows must match with the number of elements of the other vector variables (if any). It is not required that each row of the matrix consists of the same number of columns.

Example:

void InputFormat() {
    LINES(op, data) % SIZE(2);
}

With op = {“UPDATE”, “QUERY”}, data = {{3, 5}, {7}}, the above format will produce:

UPDATE 3 5
QUERY 7
GRID(matrix variable name) % SIZE(number of rows, number of columns)

Defines a grid consisting elements of a given matrix variable. If the given matrix variable is of type char, the elements in each row is not space-separated, otherwise they are space-separated.

Example:

void InputFormat() {
    GRID(G) % SIZE(2, 2);
    GRID(H) % SIZE(R, C);
}

With G = {{‘a’, ‘b’}, {‘c’, ‘d’}}, H = {{1, 2, 3}, {4, 5, 6}}, R = 2, C = 3, the above format will produce:

ab
cd
1 2 3
4 5 6

Problem styles
virtual void StyleConfig() {}

Defines the options to enable for problem styles. The following methods are exposed:

BatchEvaluator()

Declares that the problem uses batch evaluator.

InteractiveEvaluator()

Declares that the problem uses interactive evaluator.

CustomScorer()

Declares that the problem needs a custom scorer.

NoOutput()

Declares that the problem does not need test case output files.

See Problem Styles for more details.

Example:

void StyleConfig() {
    CustomScorer();
    NoOutput();
}

Constraints and subtasks
virtual void MultipleTestCasesConstraints() {}

Defines the constraints to be imposed to the multiple test cases counter.

virtual void Constraints() {}

Defines the constraints to be imposed to the input/output variables.

virtual void Subtask1() {}
virtual void Subtask2() {}
// ...
virtual void Subtask25() {}

Defines the constraints to be imposed to the input/output variables for each subtask (up to 25).

Macros/methods

CONS(predicate)

Defines a constraint. predicate is a boolean expression, whose value must be completely determined by the values of the input variables (only).

Points(double points)

Sets the points assigned to a subtask. If not specified, the default is 0. Only available in SubtaskX() s.

Examples:

void MultipleTestCasesConstraints() {
    CONS(1 <= T && T <= 20);
}
void Constraints() {
    CONS(A <= B && B <= 1000);
    CONS(graphDoesNotHaveCycles());
}
void Subtask1() {
    Points(70);

    CONS(A <= B && B <= 1000);
    CONS(graphDoesNotHaveCycles());
}

Multiple test cases config
virtual void MultipleTestCasesConfig() {}

Defines the config for multiple test cases per file problems. The following methods are exposed:

Counter(int &var)

Sets the input variable that will hold the number of test cases in a file.

OutputPrefix(std::string prefix)

Sets the prefix to be prepended to the output of each test case. It can include %d, which will be replaced by the actual test case number (1-based).

Example:

void MultipleTestCasesConfig() {
    Counter(T);
    OutputPrefix("Case #%d: ");
}

Grading config
virtual void GradingConfig() {}

Defines the config for local grading. The following methods are exposed:

TimeLimit(int timeLimitInSeconds)

Sets the time limit in seconds. If not specified, the default value is 2 seconds.

MemoryLimit(int memoryLimitInMegabytes)

Sets the memory limit in MB. If not specified, the default value is 64 MB.

Example:

void GradingConfig() {
    TimeLimit(3);
    MemoryLimit(256);
}

Test spec

TestSpec must inherit tcframe::BaseTestSpec<ProblemSpec>:

class TestSpec : public BaseTestSpec<ProblemSpec> {};

Except for private helper functions, every member of TestSpec listed below must be protected.


Sample test cases
virtual void SampleTestCase1() {}
virtual void SampleTestCase2() {}
// ...
virtual void SampleTestCase25() {}

Defines the sample test cases (up to 25). The following methods are exposed:

Subtasks(std::set<int> subtaskNumbers)

Assigns the current sample test case to a set of subtasks, if the problem has subtasks. If used, this should be the first call in a sample test case.

Input(std::vector<std::string> lines)

Defines the input as exact literal string, given as list of lines.

Output(std::vector<std::string> lines)

Defines the input as exact literal string, given as list of lines. It is optional; if not specified, the solution will be run against the sample input to produce the corresponding sample output.

Example:

void SampleTestCase1() {
    Input({
        "4 6",
        "a b c"
    });
    Output({
        "10"
    });
}

Test cases and test groups
virtual void TestCases() {}

Defines the test cases.

virtual void TestGroup1() {}
virtual void TestGroup2() {}
// ...
virtual void TestGroup25() {}

Defines the test cases on each test group (up to 25). The following method is exposed:

Subtasks(std::set<int> subtaskNumbers)

Assigns the current test group to a set of subtasks. This should be the first call in a test group.

void TestGroup1() {
    Subtasks({1, 3});

    // test case definitions follow
}

Defining test cases

The following macro is exposed to define test cases:

CASE(comma-separated statements)

Defines a test case.

statement should be one of:

  • assignment to an input variables
  • private method call that assigns values to one or more input variables

Example:

void TestCases() {
    CASE(N = 42, M = 100, randomArray());
    CASE(N = 1000, M = 1000, randomArray());
    CASE(randomEqualNandM(), randomArray());
}

Test case lifecycle
virtual void BeforeTestCase() {}
virtual void AfterTestCase() {}

Hook up additional logic to run during in a test case lifecycle.

For each test case, the following things will happen in order:

  1. BeforeTestCase() is executed.
  2. The assignments/method calls inside CASE() are executed.
  3. AfterTestCase() is executed.
  4. Input variable values are printed according to the input format.

Random number generator

BaseTestSpec exposes a random number generator object rnd that can be utilized to define test cases. The following methods are available on it:

int nextInt(int minNum, int maxNum)

Returns a uniformly distributed random integer (int) between minNum and maxNum, inclusive.

int nextInt(int maxNumEx)

Returns a uniformly distributed random integer (int) between 0 and maxNumEx - 1, inclusive.

long long nextLongLong(long long minNum, long long maxNum)

Returns a uniformly distributed random integer (long long) between minNum and maxNum, inclusive.

long long nextLongLong(long long maxNumEx)

Returns a uniformly distributed random integer (long long) between 0 and maxNumEx - 1, inclusive.

double nextDouble(double minNum, double maxNum)

Returns a uniformly distributed random real number (double) between minNum and maxNum, inclusive.

double nextDouble(double maxNum)

Returns a uniformly distributed random real number (double) between 0 and maxNum, inclusive.

void shuffle(std::RandomAccessIterator first, std::RandomAccessIterator last)

Randomly shuffles the elements in [first, last). Use this instead of std::random_shuffle().


Runner program

A runner is the compiled version of a spec file, and is capable of two things:

Test cases generation
./runner [options]
--output=<dir>

The output directory to which the test cases will be generated. Default: tc.

--solution=<command>

The solution command to use for generating output files. Default: ./solution.

--scorer=<command>

The custom scorer command to use for checking sample output strings in problem spec class. Default: ./scorer.

--seed=<seed>

The seed for random number generator rnd in the test spec. Default: 0.

Local grading
./runner grade [options]
--output=<dir>

The output directory from which the generated test cases will be read. Default: tc.

--solution=<command>

The solution command to grade. Default: ./solution.

--scorer=<command>

The custom scorer command to use. Default: ./scorer.

--communicator=<command>

The communicator command to use. Default: ./communicator.

--time-limit=<time-limit-in-seconds>

Overrides the time limit specified by TimeLimit() in grading config.

--memory-limit=<memory-limit-in-megabytes>

Overrides the memory limit specified by MemoryLimit() in grading config.

--no-time-limit

Unsets the time limit specified by TimeLimit() in grading config.

--no-memory-limit

Unsets the memory limit specified by MemoryLimit() in grading config.

--brief

Makes the output of the local grading concise by only showing the verdicts.

Release Notes

1.6.0

September 17, 2017

Bugfixes
  • Fixed a bug where tcframe crashed when grading spec with multiple test cases mode, which has no sample test cases.
  • Fixed a bug where a LINE() with only jagged vector contained an extra leading space.
  • Fixed a bug where a LINES() with empty vectors contained extra spaces.
Enhancements
  • Disallow specifying SIZE() after LINE() and RAW_LINE() instead of silently ignoring it.

1.5.0

July 16, 2017

Bugfixes
  • Fixed a bug where the spec file cannot be compiled when its absolute path contains spaces.
New features
  • It is also possible to specify additional compilation flags, by setting the $TCFRAME_CXX_FLAGS environment variable.

1.4.0

May 29, 2017

New features
  • Interactive problems are now supported. See Problem Styles for more details.
  • It is now possible to assign points to subtasks. See Subtasks for more details.
  • It is now possible to specify more than one output formats. See Multiple output formats for more details.
  • It is now possible for scorers to specify partial points, by outputting OK\n<points>\n. See Scorer for more details.
  • Local grading now supports additional --brief argument to make the output concise. See Local grading for more details.

1.3.0

February 10, 2017

New features
  • Subtask IDs specified by Subtasks() in TestCases() or TestGroupX() are now validated. It is an error now if you specify non-existing subtasks.
  • BeforeOutputFormat() can be used to set the value of output variables that depend on input variables. See BeforeOutputFormat() for more details.

1.2.1

January 29, 2017

Bugfixes
  • Fixed a regression when I/O format segments do not pick up correct sizes if the sizes contain expressions that contain I/O variables. The value of the variables were evaluated the first time they were read.

    For example, if you declare SIZE(N - 1), it would always evaluate to SIZE(-1) (N = 0), which is incorrect. It is now fixed.

    Note that if the expression contains only a single variable (e.g. SIZE(N)), it is not affected and has always been correct.

1.2.0

December 16, 2016

Bugfixes
  • Fixed a regression when the final verdict of local grading of problems without subtasks is always AC.
New features
  • It is now possible to write a custom program that checks whether the contestant’s output is correct (instead of just comparing it with the official output). This is called custom scorer program.
  • It is now possible not to generate test case output (.out) files.

See Problem Styles for details on how to enable the above options.

1.1.0

December 4, 2016

New features
  • It is now possible to omit SIZE() for a LINES() segment, as long as it is the last segment in an I/O format.
  • Brand new segments: RAW_LINE() and RAW_LINES(), which accept strings containing whitespaces.
Enhancements
  • I/O format errors after a vector/matrix now have the last indices reported in the error message. For example,

    Before:

    Expected: <newline> after 'D'
    

    Now:

    Expected: <newline> after 'D[1]'
    

1.0.1

November 28, 2016

Bugfixes
  • Fixed a regression when I/O format segments do not pick up correct sizes taken from I/O variables.
  • Fixed a regression when std::string cannot be used as variable type.

1.0.0

November 27, 2016

Note

See the migration guide from 0.x at the bottom of this page.

First stable release. Almost a complete rewrite from 0.x. Focusing on syntax improvements and conceptual refinements.

BREAKING CHANGES
  • Minimum GCC version is now 4.8.
  • The source file of a runner program is now conceptually called “spec file”, and is called spec.cpp instead of runner.cpp.
  • A spec file now includes <tcframe/spec.hpp> instead of <tcframe/runner.hpp>.
  • main() function in a spec file is not needed and must be removed.
  • Problem specification is now called a “problem spec”, and its class is ProblemSpec instead of Problem. It now inherits BaseProblemSpec.
  • Generator specification is now called a “test spec”, and its class is TestSpec instead of Generator. It now inherits BaseTestSpec.
  • The container directory of a spec file is now conceptually called “problem package directory”.
  • The slug for a problem is now taken from the name of the problem package directory, and cannot be overridden via problem spec or command-line option.
  • Config() in test spec is removed, so it is not possible to e.g. specify the solution command and test cases output directory in test spec.
  • Config() in problem spec is split into GradingConfig() and MultipleTestCasesConfig().
  • setTimeLimit() and setMemoryLimit in problem spec’s Config() are now TimeLimit() and MemoryLimit() in GradingConfig().
  • setMultipleTestCasesCount() in problem spec’s Config() is now Counter() in MultipleTestCasesConfig().
  • assignToSubtasks() in test groups is now Subtasks().
  • Individual sample test cases now live in their own methods, SampleTestCaseX() where X is sample test case number.
  • SAMPLE_CASE() is split into multiple calls: Subtasks(), Input(), and Output().
  • FinalizeInput() is renamed to AfterTestCase().
  • “Submission simulation” is now conceptually called “local grading”.
  • ./runner submit is now ./runner grade.
  • --brief option for local grading is removed until there is clear use case for it.
  • --slug option is removed.
  • --solution-command option is simplified to --solution.
  • --tc-dir option is renamed to --output.
New features
  • tcframe helper script is introduced. It currently has 2 commands: tcframe build, which compile a spec file into a runner program, and tcframe version, which prints current tcframe version.
  • A summary is printed after generation/grading, which shows whether or not there are failing test cases.
  • It is now possible to specify the literal output for sample test cases, by calling Output() inside SampleTestCaseX().
  • BeforeTestCase() to complement the new AfterTestCase(), which can be used to initialize input variables before each test case.
  • For problems with subtasks, Constraints() can be used to specify global constraints that apply to every subtask.
  • In ICPC-style multiple test cases in a file problems, it is now possible to specify a prefix that will be prepended to every output, by calling OutputPrefix() (e.g. OutputPrefix("Case #%d ");).
Enhancements
  • Maximum X for TestGroupX(), SubtaskX() (and the new SampleTestCaseX()) is now 25.
  • If there are errors in I/O format, previously the error was shown in every test case, resulting in spammy output. Now, it is reported only once before the test cases are evaluated.
Bugfixes
  • When using multiple test groups in ICPC-style multiple test cases in a file problems, it was erroneously required to call assignToSubtasks({-1}). Now, it is not required.
  • In e.g. this input segment LINE(A % SIZE(3), B), when B is not a supported type, tcframe reported the error as Variable type of `%` unsatisfied... due to a tokenization bug. It is now fixed.
Project development
  • Repository moved to https://github.com/tcframe/tcframe.
  • (Almost) every class now lives on its own file.
  • Rewrite almost everything with better testability in mind. Now, we have decent unit tests.
  • Use Google Test and Google Mock for unit tests.
  • Add basic end-to-end tests for generation and local grading.

MIGRATION GUIDE

First, “install” the tcframe CLI utility; see Installation for more details.

Then, apply the following for each runner.cpp you want to migrate.

spec.cpp
  • Rename runner.cpp to spec.cpp.

  • Include <tcframe/spec.hpp> instead of "tcframe/runner.hpp".

  • Completely remove main() function.

  • Change the following two classes

    class Problem : public BaseProblem {};
    class Generator : public BaseGenerator<Problem> {};
    

    to:

    class ProblemSpec : public BaseProblemSpec {};
    class TestSpec : public BaseTestSpec<ProblemSpec> {};
    
ProblemSpec
  • Remove setSlug() from Config(). The slug is now inferred from the containing (problem package) directory. See Problem package for more details.

  • Change the following:

    void Config() {
        setMultipleTestCasesCount(T);
        setTimeLimit(2);
        setMemoryLimit(64);
    }
    

    to:

    void MultipleTestCasesConfig() {
        Counter(T);
    }
    
    void GradingConfig() {
        TimeLimit(2);
        MemoryLimit(64);
    }
    
TestSpec
  • Completely remove Config() – the options in it should now be specified via command-line options instead.
  • Change assignToSubtasks() to Subtasks().
  • Change FinalizeInput() to AfterTestCase().
  • Split SampleTestCases() into multiple SampleTestCaseX(). See Test cases for more details.
After migration

You should now be able to run tcframe build to compile your new spec file into runner program.

The following are new in 1.0.0 that are recommended to do:

  • Put all input variable initializations in BeforeTestCase() instead of repeating them in private helper methods. See Test case lifecycle for more details.
  • Put all global problem constraints in Constraints() instead of repeating them in all SubtaskX()s, if your problem has subtasks.
  • Include Output() in sample test case definitions, so that you are sure you are typing the output correctly in the problem statement by only looking at the spec file (no need to check with the actual produced output file).

0.7.0

March 9, 2016

New features
  • Allow omitting OutputFormat() and disable output format checking.
  • Support jagged vector as the last input variable in a LINES() segment.
Project development

0.6.0

February 8, 2016

BREAKING CHANGES
  • Rename --porcelain to --brief.
New features
  • Support vector of any length as input/output format.
Project development
  • Ignore build files in .gitignore.

0.5.0

August 4, 2015

New features
  • Implement simple random number generator convenient wrapper.
  • Support ICPC-style problem (multiple test cases per file).
Project development
  • Change code coverage service from Coveralls to Codecov.
  • Add .gitignore.

0.4.0

June 28, 2015

Focusing on submission simulation feature and code refactor.

New features
  • Submission simulation feature. One can test submitting solution without online judge.
  • Time limit + memory limit for submission simulation. Uses ulimit.
Bugfixes
  • Porcelain output in submission feature sometimes always true.
  • Solution/submission killed by signal prints the signal message in wrong place.

0.3.0

March 29, 2015

Focusing on output variables/format and clearer docs.

New features
  • Support output variables and format.
  • I/O format methods are now called before every test case, in preparation for supporting more complex formats.
  • Lower down GCC version. Now the minimum version is 4.7.
Project development
  • Apply MIT license.
  • Add quite neat API reference.

0.2.0

March 13, 2015

This version contains most of the functionalities required for generating test cases in real world.

New features
  • Support scalar variables of types other than int (char, long long, std::string, etc.).
  • Support vector and matrix variables.
  • Support for lines and grid segments.
  • Implement convenience macros for specifying I/O segments.
  • Support sample test cases as literal lines of strings.
  • Check and report invalid input format.
  • Check and report failed solution execution.
  • Add intermediate method that can modify input variables before being output.
  • Increase limit of subtasks and test groups to 10.
Project development
  • Host documentation at Read the Docs.
  • Change build system to CMake.
  • Change extensions of header files to .hpp.
  • Add code coverage reporting using Coveralls.io.

0.1.0

February 8, 2015

Initial prototype version. This version contains only the core functionalities of the framework.

Initial features
  • Can declare input variables. Only integers are supported at the moment.
  • Can specify input format. Only single-line variables are supported at the moment.
  • Can specify constraints, with or without subtasks.
  • Can specify test cases, with or without test groups. Sample test cases are not supported yet.
  • Can check each test case whether it satisfies the constraints/subtasks it is assigned to.
  • Can generate input files.
  • Can run solution on the generated input files for producing output files.