Test Generation Plan

Some tips for writing test generation plans:

Every problem submission must be accompanied by test data, an integral part of which is the test generation plan.

You should provide test generator program that you use during test generation of your test data.

It should be such that anyone can reproduce the whole test data using this plan. It is observed that sometimes the problem setters write a test generation program and then change some constants in it and run it to generate different test data and then they forget what constants were used to arrive at the given data. In such a scenario, it is suggested to write program that takes parameters. However, if you take these parameters from the command line and then run it multiple times with several sets of parameters, the list of all used sets of parameters should be provided. A better way will be to write just one program that generates all input and output files at once and also validate their correctness.

If you use random test generation then, it is suggested to use https://code.google.com/p/testlib/ for rand() function or some self-written random class. Using srand(time(NULL)) is bad. Since it does not allow to reproduce the same test file later.

You should try and figure out several solutions (alternative, slow or wrong) to your problem and in your test generation plan you should mention which of them are failed for which test data. This is non-trivial and is only suggested so that it helps the tester in his testing process.

For some problems the slow (not optimal) or wrong solution is obvious and the key part of your test plan should be to fail all its implementations. This should be done while submitting the problem and not left for the testing process to start as it may take a lot of time to investigate and figure out how to generate such test data and delay the contest schedule.

Some examples of test generation plans:

For Problem SALARY, you can find the test data along with the test generation plan:

0.in - T=100. For each test: n=random(1,100), W[i]=random(0,10000). The output file is here.

1.in - T=100. For each test: n=100, W[i]=10000, except one W[i] which is equal to 0 (for example, set W[rand()%n]=0 after all W[i] is generated). The output file is here

2.in - T=100. For each test: n=random(99,100), W[i]=random(9900,10000), except one W[i] which is equal to random(0,1) (choose i0=rand()%n and set W[i0]=rand()%2). The output file is here

3.in - T=100, but we have several groups of tests
- tests 1-9 : n=random(1,100), W[0]=random(0,10000), W[i]=W[0] for 0<i<n (So all W[i] are equal).
- test 10 : n=100, W[i]=10000 (the maximal test)
- tests 11-20 : n=random(1,5), W[i]=random(0,3)
- tests 21-30 : n=random(1,10), W[i]=random(0,10)
- tests 31-40 : n=random(90,100), W[i]=random(0,1)
- tests 41-50 : n=random(90,100), W[i]=random(9999,10000)
- tests 51-59 : n=random(90,100), W[i]=random(0,1) or random(9999,10000)
- test 60 : n=100, W[i]=random(0,1) but one W[i]=random(9999,10000)
- tests 61-70 : n=random(90,100), W[i]=random(0,1) or random(9999,10000) or random(0,10000)
- tests 71-75 : n=random(90,100), W[i]=0 or 10000
- tests 76-80 : n=random(90,100), W[i]=10000 or random(0,10000)
- tests 81-85 : n=random(90,100), W[i]=0 or random(0,10000)
- tests 86-100 : n=random(2,100), k=random(2,n) is chosen,
k distinct random integers from 0 to 10000 is chosen, then each W[i] is set to be one this integers at random. The output file is here.

4.in (Does not exist, but could be added) T=10. For each test: N=random(1,10) W[i]=random(0,10) (small test).

For Problem DIVPRO, you can find the test data along with the test generation plan:

0.in - contains all 318,666 pairs (L,V) with non zero answer and V!=0, and all pairs with V=0. The output file is here.

1.in - contains 320,000 instances of L=random(35,36), V=0. The output file is here.

2.in - contains 320,000 instances of L=random(1,36), V=random(0,10^18-1). The output file is here.

3.in - contains 320,000 instances of L=random(35,36), V = 3^36. Reasonable Max-test for O(log V) calculation of (n2, n3, n5, n7) and also test with maximal possible size. The output file is here.

4.in - T=320,000. It should contain all 66060 numbers V of the form 2^n2 * 3^n3 * 5^n5 * 7^n7 < 10^18 (backtracking could be used to generate them). For each V we could use several values of L (about 5). Two of these values should be 35 and 36. Other values could be random. The output file is here.

5.in - T=320,000. L=random(35,36), V is random of the form 2^n2 * 3^n3 * 5^n5 * 7^n7 and V < 1e9. The output file is here.

6.in - T=320,000. L=random(35,36), V is random of the form 2^n2 * 3^n3 * 5^n5 * 7^n7 and V < 1e3. The output file is here.

7.in - T=320,000. L=random(35,36), V = 0, 1, 2, ..., 319,999. The output file is here.

8.in - T=320,000. L=random(1,30), V for i-th test is generated as follows. Let P[i] be i-th prime > 7 (they could be generated using sieve up to 5e6). Take V to be some random V for which answer for the pair (V, L) is non-zero and replace it by V+random(1,1e6)*P[i]. This special case will fail the solution with hashing V modulo prime if the check table[V%P].first == V will be absent. The cool thing that all reasonable possible choices of P will be failed by one test. The output file is here.

9.in - T=320,000. At first (L, V) is random feasible pair among 318,666 + 36 pairs (36 for V=0). And then V is replaced by V+random(-1,1) (but we ensure that V satisfies constraints). This test could probably fail some inaccurate solutions with binary search for searching V. The output file is here.

10.in - contains 320,000 instances of L=30, V = 2^54 * 7 (another max test for O(log V) calculation of (n2, n3, n5, n7) but since division by 2 is faster than by 3, test 3.in is better). The output file is here.

The generator program for the same is here.

For Problem CAKEDOOM, you can find the test generation plan below:

1st group: All possible arrays for
K=1, 1<=N<=5 (2+4+8+16+32=62 tests in all)
K=2, 1<=N<=6 (3+9+27+81+243+729=1092 tests in all)
K=3, 1<=N<=5 (4+16+64+256+1024=1364 tests in all)
K=4, 1<=N<=4 (5+25+125+625=780 tests in all)

2nd group: 600 tests of the form
K=2;
N=2*random(4,50);
S="0101...01" or "1010...10"
Then replace some random number of digits by question marks. Namely, Choose M=random(0,N), then for array p: p[i]=i, make random_shuffle(p,p+N) and put question marks for p[0], p[1], ..., p[M-1]. (so here the replacement is always possible)

3rd group: 600 tests of the form like in the second group but in the end for some random number of positions we replace the character there by the wrong digit according to the original choice of S. These positions should be chosen like in the second group but their number should be L=random(0,N/10)+1 (so here the replacement is always impossible)

4th group: 600 tests of the form
K=2;
N=2*random(4,50)-1;
S="0101...01?" or "1010...10?"
Then replace some random number of digits by question marks (see second group). (so here the replacement is always impossible but wrong dealing with first and last characters can lead to WA)

5th group: 2000 completely random tests:
K=random(1,10);
N=random(1,100);
each character in the string is random from the set {?,0,1,...,K-1} (most of these tests will be useless and trivial but in any case we need some random tests)

6th group: 2000 tests of the form
K=random(3,10);
N=random(1,100);
S is created as follows
S[0]=random(0,K-1)
Then S[i]=random(0,K-1) not equal to S[i-1] (1<=i<N-1)
Finally S[N-1]=random(0,K-1) not equal to S[0] and S[N-2]
(For example you can use cycle
for(;s[i]=rand()%k, s[i]==s[i-1];); for 1<=i<=n-2
and
for(;s[n-1]=rand()%k, s[n-1]==s[0] || s[n-1]==s[n-2];); for 1<=i<=n-2
)
but be careful with small values of n (n-2 can be negative for n=1) Now S is a good array. So next let's add some "?". This should be done in the same way like for the second group.

Finally, 7th group should be the same as the sixth one but in the end we should change some small random number of digits to made the string incorrect. It means that you should choose some digit that has digit neighbor and replace it by this neighbor.
Like ???012?? --> ???002??, or ???112??

So we will have about 11000 tests in total which can be divided into 11 test files. You can for example store all these tests in some array then make its random_shuffle and write into appropriate number of files.

But it's not the end. We need some test on maximal performance. Namely,
12-th test file should have 1000 tests of the form like in the second group but for all tests N=100
13-th test file should have 1000 tests with N=100 and
each test randomly is like in the second group or like in the third group
14-th test file should have 1000 tests with N=100 like in the 6-th group
15-th test file should have 1000 tests with N=100 randomly like in the 6-th group or in 7-th group.