Hello Codeforces community.
Tl;dr: The script is specifically for Linux and can be used to stress test C++ solutions. It can be easily modified to work with python or java and other operating systems.
First let me tell you what stress testing is if you don't know, Stress testing is technique using which we can run our solution (which we think might fail/is failing) on a number of random test cases and match it's output with the output of a solution which is a brute force solution or accepted solution of someone else.
If you don't know why and when to use stress testing you can use this detailed article on Stress Testing by ADJA.
I want to share my script for stress testing your solution.
Requirements:
1) A solution which we want to test.
2) A brute force solution which gives correct solution.
3) A generator for generating test cases according to the problem.
About script:
Go through the code once, i have added comments and you will understand most of the part. To understand the script all we need is just a things about language bash. So we have three .cpp files:
1) gen.cpp // our cpp solution for generating test cases
2) solution.cpp // our orignial solution
3) brute.cpp // our solution which uses brute force and guaranteed to give correct output
About gen.cpp: For generating test cases you can either use "testlib.h" here (i personally don't use it because it takes 6-7 seconds on average to compile in my pc(idk there might be ways to reduce it) and also i need to remember the methods to generate things.) or write your own since most of the time you just need arrays, strings, trees or simple graphs or simple some integers.
I use the below code for generating test cases most of the times:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define accuracy chrono::steady_clock::now().time_since_epoch().count()
#define rep(i,a,n) for (int i = a; i <= n; ++i)
const int N = 1e6 + 4;
int32_t permutation[N];
mt19937 rng(accuracy);
int rand(int l, int r){
uniform_int_distribution<int> ludo(l, r); return ludo(rng);
}
const int inf = 1LL << 31;
using pii = pair<int,int>;
namespace generator {
string gen_string(int len = 0, bool upperCase = false, int l = 1, int r = 26) {
assert(len >= 0 && len <= 5e6);
string str(len, (upperCase ? 'A' : 'a'));
for (char &ch: str) {
ch += rand(l, r) - 1;
}
return str;
}
vector<int> gen_array(int len = 0, int minRange = 0, int maxRange = inf){
assert(len >= 0 and len <= 5e6);
vector<int> a(len);
for (int &x: a) x = rand(minRange, maxRange);
return a;
}
vector<pair<int, int>> gen_tree(int n = 0){
assert(n >= 0);
vector<pii> res(n ? n - 1 : 0);
// if you like to have bamboo like tree or star like tree uncomment below 8 lines
/*if (rng() % 5 == 0) { // bamboo like tree
for (int i = 1; i < n; ++i) res[i-1] = {i, i + 1};
return res;
}
if (rng() % 7 == 0) { // star tree
for (int i = 2; i <= n; ++i) res[i-2] = {1, i};
return res;
}*/
iota(permutation, permutation + 1 + n, 0);
shuffle(permutation + 1, permutation + 1 + n, rng);
for(int i = 2; i <= n; ++i){
int u = i, v = rand(1 , i-1);
u = permutation[u], v = permutation[v];
res[i-2] = minmax(u, v); // u < v, just for convenience while debugging
}
shuffle(res.begin() , res.end() , rng);
return res;
}
vector<pair<int, int>> simple_graph(int n = 0, int m = 0) {
assert(n > 0 && m >= n);
int max_edges = n * (n - 1) / 2;
assert(m <= max_edges);
vector<pii> res = gen_tree(n);
set<pii> edge(res.begin(), res.end());
for (int i = n; i <= m; ++i) {
while (true) {
int u = rand(1, n), v = rand(1, n);
if (u == v) continue;
auto it = edge.insert(minmax(u, v));
if (it.second) break;
}
}
res.assign(edge.begin(), edge.end());
return res;
}
}
using namespace generator;
template<typename T = int>
ostream& operator<< (ostream &other, const vector<T> &v) {
for (const T &x: v) other << x << ' ';
other << '\n';
return other;
}
ostream& operator<< (ostream &other, const vector<pair<int,int>> &v) {
for (const auto &x: v) other << x.first << ' ' << x.second << '\n';
return other;
}
// comment the just below line if test cases required
#define SINGLE_TEST
const int max_tests = 10;
// complete this function according to the requirements
void generate_test() {
int n = rand(1, 40);
cout << n << '\n';
cout << gen_array(n, 1, 20);
}
signed main() {
srand(accuracy);
int t = 1;
#ifndef SINGLE_TEST
t = rand(1, max_tests), cout << t << '\n';
#endif
while (t--) {
generate_test();
}
}
You can above code too and modify it according to your needs. Just go through the code once and everything is self explanatory(i have added some comments too). Usage of above gen.cpp code:
1) to generate an array call:
gen_array(length_of_array, range_min, range_max);
it will return an array(vector more specifically) with length `length_of_array` and elements in the range `range_min` to `range_max`.
