Technique to get the test cases where the program is going wrong, during the contest

[asenarmour]

It’s quite frustrating when our code shows wrong answer on verdict where it seems to us completely correct and then we make some test cases but still the story remains same,
now in a order to tackle this situation you have to make a program which generates test cases
here is the link to a youtube vedio which explains this technique
https://www.youtube.com/watch?v=-AcDqd_iT3k&list=PLMCXHnjXnTnsWU7jYp9XCKPW8ayl6D8fb&index=4&t=0s

vedio explain test cases generation in java but the technique can be applied to any language like i applied it in python
i made two functions where the 1st function contains the optimised code and 2nd is the bruteforce and then the code generate some random integers and they are passed to both of the functions and if the output differs then we stop and print the test case where the output is different
i applied this technique to “guddu and his mother” problem from august challenge where i was getting wrong answer and after checking it on randomly generated test cases i was able to get the test case where my optimised program was failing
here is the image which shows my implementation, just in sake of showing important part i have hidden the code of both of the function they are just returning the values after executing the test case

if you find something missing or if you know any other better technique than please let me know your suggestions are welcome

[racsosabe]

Nice, I usually have a BASH script to test a code against a bruteforce or correct one. I usually use mt19937 for generating random testcases and a testlib.h-based code to check if the solution is correct (This Mike Mirzayanov’s library is very useful ). And as you said, run it like 10^4 times to check if the code is very probable to get AC. It also works when we want to hack someone’s solution.

It’s better to have a template beforehand, mine is like this:

• Test.sh - BASH script to test
• Correct.cpp (or whatever language one uses) - Correct code
• Checker.cpp - Solution checker like the ones used in Codeforces
• Gen.cpp (or whatever language one uses) - Random testcase generator
• Sol.cpp - Solution to be tested

It’s really useful to test solutions during a contest, it helps to feel more confident about our solutions

[asenarmour]

Nice thanks for this information🙏

[varada9100]

Bro,please tell for java also

[asenarmour]

I have provided a YouTube link which explains test case generation in java

[varada9100]

Thanks…Really helpful

[iamashutosh_4]

It would be nice if you explain in some more detail how to do so along with some snippets.

[racsosabe]

Well, as I stated before, one must have these files:

• Test.sh (in the photos is x.sh) - BASH script to test
• Correct.cpp - Correct code
• Checker.cpp - Solution checker like the ones used in Codeforces
• Gen.cpp - Random testcase generator
• Sol.cpp (in the photos is Hack.cpp) - Solution to be tested

Now, let’s see the contents of the BASH script:

Thus, for this code, we will test our C++ code called Hack.cpp with the comand ./x.sh 1, for Java code JavaHack.java ./x.sh 2, for Python code pythonHack.py we’ll use ./x.sh 3 (2|3) and for Kotlin code called kotlinHack.kt ./x.sh (anything but 1,2,3)

Code: Testing Script

Now, let’s check out the Generator:

It uses mt19937 seed for the generation of random integers (it works with doubles, too, check documentation ).

Code: Generator Test 2 Code

Now, suppose the answer is 2n, then the correct code must have long long variable n for both tests in order to get AC.

Thus, we have our Correct.cpp code:

I guess it’s not necessary to put that code in here so I’ll skip this one XD

Let’s suppose that our Hack.cpp code is incorrect, because it uses an int variable:

Then, our checker must be able to recognize this error, so it must receive both answers as long long (since it’s the strongest of the two variable types used and also the minimal variable type in which the answer can fit) and compare them directly:

You can read more about checkers in: Checkers with testlib.h

Code: Checker Code

Now let’s test both cases (-10^{18} \leq n \leq 10^{18} and -2\cdot 10^{9} \leq n \leq 2\cdot10^{9}):

It’s easy to notice that Testing 1 must have a soon WA veredict since the probability of getting an overflow value is huge. Compared to that, Testing 2 delays a little because the same probability is not that big for that case.

I hope this helped you

[ashishkr23438]

@racsosabe Any reason why you’ve used timeout 20 in the file x.sh? Won’t it be faster if this command is omitted? Or will it cause any errors in the program?

[i_64]

I’d like to add the use of assert statements to get an idea about the inputs, or how big “T”(no. of test cases) is. It has helped me twice in this long.

[racsosabe]

It’s just to ensure that the program doesn’t get TLE in your own computer (I use 20 because my computer is not very modern XD if you have a computer that works like the usual judges’ servers just use 3 or 2)

[godlevi]

Why is that video unlisted though?