How are test cases generated? - Codeforces

→ Pay attention

Before contest
Codeforces Round 950 (Div. 3)
43:15:46
Register now »

→ Top rated

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	164
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

NeverMa573r's blog

How are test cases generated?

By NeverMa573r, history, 10 months ago, In English

In English

Just curious, do problem setters create some test cases by hand and then randomly generate the rest or are all the test cases just randomly generated within the bounds of the problem?

+7

NeverMa573r
10 months ago
2

Comments

Comments (2)

Write comment?

»

10 months ago, # |

Vote: I like it

0

Vote: I do not like it

There are different methods to generate a test case. Usually another code is written to generate random numbers within a given constraint and then printed into a file which is uploaded.

But sometimes smaller edge cases are manually written.

→ Reply

»

10 months ago, # |

Vote: I like it

+25

Vote: I do not like it

Some tests are made by hand, however most are randomly generated. This doesn't mean that the tests are completely random, as they would be very weak.

For example, 1784C — Zero Sum Prefixes has 8 distinct test generators.

The one that was used for the most testcases is this one:

Code

#include "testlib.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int NMAX=2e5+5,maxval=1000000000;
int n[NMAX];
set<ll> freq;
bool add_new_element(ll Size){
    double p=(Size==0?1.0:1.0/cbrt(Size));
    return rnd.next(1000000)<=(p*1000000);
}
int main(int argc, char* argv[]){
    registerGen(argc,argv,1);
    int t=atoi(argv[1]+2),sumn=atoi(argv[2]+5),p0=atoi(argv[3]+3),bucket=atoi(argv[4]+7);
    for(int i=0;i<t;i++) n[i]++,sumn--;

    while(sumn>0) n[rnd.next(t)]++,sumn--;

    cout<<t<<'\n';


    for(int i=0;i<t;i++){
        cout<<n[i]<<'\n';
        ll current_prefix_sum=0;
        freq.clear(); freq.insert(0);

        for(int j=0;j<n[i];j++){
            if(!rnd.next(p0)){
                cout<<0<<" \n"[j==n[i]-1];
                freq.clear(); freq.insert(0);
                current_prefix_sum=0;
            }
            else{
                if(freq.size()<bucket && add_new_element(freq.size())){
                    ll curr=rnd.next(-maxval,maxval);
                    current_prefix_sum+=curr;
                    cout<<curr<<" \n"[j==n[i]-1];
                    freq.insert(current_prefix_sum); freq.insert(0);
                }
                else{
                    vector<ll> cnd;
                    for(auto it : freq){
                        if(abs(it-current_prefix_sum)<=maxval && it!=current_prefix_sum)
                            cnd.push_back(it);
                    }
                    ll new_prefix_sum=cnd[rnd.next(cnd.size())];
                    cout<<new_prefix_sum-current_prefix_sum<<" \n"[j==n[i]-1];
                    current_prefix_sum=new_prefix_sum;
                }
            }
        }
    }
    return 0;
}

It takes the number of testcases, the maximum sum of $$$n$$$ across all testcases, the probability of an element being equal to $$$0$$$ and a bucket as parameters.

This generator works based on the intended solution. In each subarray delimited by two zeroes, we can have at most bucket distinct prefix sums. The reasoning for this is that if the bucket size is smaller, the answer will be larger, and vice-versa.

→ Reply