rustam-cpp's blog

Test generator on C++
By rustam-cpp, history, 3 months ago, translation, In English

Hello, CodeForces!

Information

I wrote a test generator on C++. It is very simple, it contains 2 functions: "generate a random number between $$$a$$$ and $$$b$$$, so that this random number is a multiple of $$$k$$$" (function: genint(a, b, k, add), where add is whether to "add" this number to the test) and "generate of a random string". There's something to be written here.

  • Generates a string of random length between $$$a$$$ and $$$b$$$, so that it is a multiple of $$$k$$$.
  • Consisting of the given characters. You can set characters in two ways: write the interval ("a-f", "x-z") or a individual character ("m", "o"). (function: genstr(a, b, k, pattern, add), where pattern is an array of given intervals or individual characters).
Code

Usage

Here is a problem: You are given a string length of $$$n (n \le 10^5)$$$. You need to find the percentage of content of each character that is in the string (your answer will be considered correct if its absolute or relative error won't exceed $$$10^{-5}$$$). Example input and output:

Example

You need to process $$$t$$$ testcases

For us, the competitors, this task is very simple, but for the authors it's necessary to write such tests, in which there will be both border and normal cases. Writing it by hand is a bad option. Especially since $$$n \le 10^5$$$.

With my generator you can make good tests in a few lines:

const int mintestcases = 5;
const int maxtestcases = 8;
const int minlength = 10;
const int maxlength = 20;
for (int i = 0; i < 5; i++) { // generates 5 tests
  string test = "";
  int t = genint(mintestcases, maxtestcases, 1, true);
  test += '\n';
  for (int j = 0; j < t; j++) {
    int n = genint(minlength, maxlength, 5, true);
    test += '\n';
    genstr(n, n, 1, {"a-z"}, true);
    test += '\n';
  }
}
Tests

To make large tests you should increase values: mintestcases, maxtestcases, minlength, maxlength. For pretests you can take 1-2 tests of each "size".

You can generate strings consisting of uppercase letters: genstr(10, 20, 5, {"A-D"}, true), result: DCABACCCABBBBDBD.

You can also generate a string consisting of lowercase and uppercase letters: genstr(10, 20, 5, {"A-D", "a-d"}, true), result: DcaBaccCABBBBDBD.

Conclusion

This generator is also good for stress testing. Generating tests in a task is usually not very difficult. Also it can be used for hacks. You can generate a "maximal" test very easily.

Lucky rounds and high rating to all, bye!

  • Vote: I like it
  • -160
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm having a hard time understanding the purpose of this blog. What's your target audience? Are you teaching author's how to generate testcase?

Also, You used rand() function without setting seed. Without it, every time you run it, this will generate same output. Better to set srand(time(NULL)).

Or even better, use mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());. Learn more about it here.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    "Are you teaching author's how to generate testcase?" — No, I do this: "This generator is also good for stress testing. Generating tests in a task is usually not very difficult. Also it can be used for hacks. You can generate a "maximal" test very easily."

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it +7 Vote: I do not like it

      I've never done hacking, but I believe whole purpose of hacking is to exploit a user's submission. It's often not random. Probably exploiting corner case, trying to get TLE, MLE, RE using deliberate testcases. And those who enjoy hacking, do know what they are doing. It's probably not useful for them either.

      But let's see, what others have to say.

      → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    srand(time(NULL)) — i forget about it =)

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And why do you need a getint() function that generate nums in multiples of k?

    Isn't the following enough? (To generate a number in range)

    mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return l + mt() % (r - l + 1); }
    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In some problems, a number in the input data must be, for example, an even number

      → Reply