How are test cases generated? - Codeforces

→ Pay attention

Before contest
Good Bye 2024: 2025 is NEAR
3 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	155
8	Dominater069	154
9	awoo	153
10	luogu_official	152

View all →

→ Find user

→ Recent actions

Detailed →

NeverMa573r's blog

How are test cases generated?

By NeverMa573r, history, 17 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
17 months ago
2

Comments

Comments (2)

Write comment?

»

17 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

»

17 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