Random Test Case Generation with Constraints

The Anatomy of a Test Case Generator

A test case generator is a program that prints a valid problem input to standard output. For most competitive programming problems, this involves a specific format. A common structure involves a number of test cases, T, followed by the data for each case.

Your generator's job is to create data that not only fits this format but also respects all the constraints mentioned in the problem statement, such as the range of N, the values of array elements, or the structure of a graph.

The Common Pitfall: Why rand() is Not Your Friend

When faced with generating random numbers, the first function that might come to mind for a C++ programmer is rand(). However, using rand() for serious competitive programming is a significant mistake that can lead to ineffective tests and hard-to-diagnose failures.

The reasons are technical but critically important. The following blog post on Codeforces by Neal Wu, a legendary competitive programmer, is considered essential reading on this topic. It demonstrates precisely why rand() is inadequate.

The examples in the article are not just theoretical. Failing to generate numbers across the entire required range for a problem means your stress test will never create the very test cases that might break your code. As a future Codeforces Expert, you need tools that are reliable and robust.

The Modern C++ Solution: <random> and mt19937

Fortunately, modern C++ (C++11 and later) provides a far superior suite of tools in the <random> header. The cornerstone of this library is the mt19937 generator.

mt19937 stands for "Mersenne Twister 19937". It's a high-quality pseudo-random number generator with excellent statistical properties and a massive period (the number of values it generates before repeating), making it ideal for our purposes.

Let's return to the same article to see how to use it correctly.

Here is a basic template for generating a random integer between L and R, inclusive:

#include <iostream>
#include <random>
#include <chrono>

int main() {
    // Initialize the random number generator with a time-based seed
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    // Define the range [L, R]
    int L = 1;
    int R = 100;

    // Create a uniform distribution and generate a number
    uniform_int_distribution<int> dist(L, R);
    int random_number = dist(rng);

    std::cout << random_number << std::endl;

    return 0;
}

This is a robust and correct way to generate random numbers in C++. However, for the specific task of writing generators in competitive programming, there is an even more convenient tool.

The Specialist's Tool: testlib.h

While mt19937 is excellent, writing the seeding and distribution code every time can be cumbersome. More importantly, subtle differences in compiler implementations of <random> can still lead to different outputs on different machines. For maximum reproducibility, the competitive programming community has developed a specialized header file: testlib.h.

testlib.h is a single-file C++ library, created by Codeforces founder Mike Mirzayanov, that is the de-facto standard for creating tests for programming contest problems. It wraps mt19937 with a simpler interface and guarantees that your generator will produce the exact same output for a given seed, regardless of the compiler or operating system.

Writing a Practical Generator with testlib.h

Let's synthesize this into a complete example. Suppose we need to generate tests for the following problem:

Problem: You are given an integer T, the number of test cases. For each test case, you are given an integer N and K. You then receive an array A of N integers. Constraints:

• $1\le T\le 10$
• $1\le N\le 2\cdot 10^5$
• $-10^9\le K\le 10^9$
• $-10^9\le A_i\le 10^9$
• The sum of N over all test cases does not exceed $2\cdot 10^5$.

Here is a complete generator.cpp using testlib.h. You would first need to download the testlib.h file and place it in the same directory as your generator.

#include "testlib.h"
#include <iostream>
#include <vector>
#include <numeric>

int main(int argc, char* argv[]) {
    // Initialize testlib's random generator.
    // The seed is determined by the command-line arguments.
    // To get different outputs, run `./generator 1`, `./generator 2`, etc.
    registerGen(argc, argv, 1);

    // Number of test cases
    int T = rnd.next(1, 10);
    std::cout << T << std::endl;

    // Constraint for sum of N
    int total_n_limit = 200000;
    std::vector<int> n_values;

    // A simple way to generate N values that respect the sum constraint
    // (There are more complex ways to do this, but this is a start)
    for(int t = 0; t < T && total_n_limit > 0; ++t) {
        int n = rnd.next(1, total_n_limit / (T - t)); // Distribute remaining N's
        total_n_limit -= n;
        n_values.push_back(n);
    }
    
    // Shuffle the generated N values to make them appear more random
    shuffle(n_values.begin(), n_values.end());

    // Generate each test case
    for (int n : n_values) {
        // Generate N and K
        long long k = rnd.next(-1000000000LL, 1000000000LL);
        std::cout << n << " " << k << std::endl;

        // Generate the array A
        for (int i = 0; i < n; ++i) {
            long long val = rnd.next(-1000000000LL, 1000000000LL);
            // Print space before all but the first element
            std::cout << val << (i == n - 1 ? "" : " ");
        }
        std::cout << std::endl;
    }

    return 0;
}

This program, when compiled and run, will print a complete, valid set of test cases to the console, which we can then redirect into a file or pipe directly to our solutions.

Conclusion

You have now learned the professional-grade approach to generating test cases for competitive programming problems. This is a skill that separates advanced programmers from beginners. It allows you to move beyond the few sample cases provided in a problem and create a robust testing environment for your own code.

Key Takeaways:

• A test case generator is a program that outputs random, valid problem inputs according to specified constraints.
• Standard C++ rand() is unsuitable for this task due to its limited range, biases, and poor statistical properties.
• The modern C++ approach uses mt19937 from the <random> header, seeded with a high-precision clock, and paired with distribution objects like uniform_int_distribution.
• testlib.h is the standard tool in the competitive programming community. It simplifies the process and guarantees cross-platform reproducibility, making it the recommended choice.

In our next lesson, we will complete our stress-testing toolkit. You will learn how to write a simple script (e.g., a Bash script on Linux/macOS or a batch file on Windows) that automates the entire loop: running the generator, feeding its output to both your optimized and naive solutions, comparing their results, and stopping immediately when a discrepancy is found.