Mooncrater's blog

By Mooncrater, history, 3 years ago, In English

So one day, after getting so ashamed of reading other's solutions and copying them, instead of trying to find out what's wrong with my code, I decided it's time. There is a video by Errichto related to this topic that I balatantly copied, and suggest others to do too.

So I was trying to solve this problem : 1418D, and after 2 days of thinking, I really felt I knew what to do, and implemented it. It failed on the 3rd test case, as can be seen in this submission.

So I decided to write a basic random test case generator for this, and a brute force version of the program.

Generator:

This is a c++ program, written to generate test cases to be feeded into our solutions. In this problem we need a $$$n$$$ : number of elements in the array initially, $$$q$$$ : number of queries on this array, the $$$n$$$ sized array, and the description of each $$$q$$$ queries. The queries also are restricted in a way that if an operation of type "0" is to be done, then an already present element in the array is to be removed, and if it's of the type "1", then an element not in the array is added to it.

So to generate $$$n$$$ and $$$q$$$ I used (rand()%10)+1 (different in code, but it's okay), to specifically generate arrays of length 1 to 10.

For $$$q$$$ too, I used the same thing. You can choose any number, but choosing small values makes sure that in the case your solution and the brute force solution don't give the same answer, then you can debug easily.

Now for the array, just generate any numbers from 0 to 100. But we can't have repeated numbers here, so I used this while loop :

while((int)p.size()<n)
    {
        int g = rand()%100 ;
        if(st.count(g)==0) p.pb(g),st.insert(g) ;
    }

Where st is a set of integers.

Now we have to generate the queries. You can create a variable operation = rand()%2, and based on it's value, decide which operation is to be performed. Type "0" is easy, as you can simply calculate the index of the element to be removed, by index = rand()%((int)p.size()) ;. Also erase them from our set and the array.

In the type "1", we'll need to generate numbers, until we reach a number which isn't in the array already. Same methodology.

Note : If you don't want your generator to generate the same test case every time (which is obvious), srand(time(NULL)) ; is to be used. Setting random seed, initiated the random function differently, because of which it generates different series of numbers. Here's the full code of the generator :

Code

Now, the Brute Force isn't actually useful in this context. It's, as the name suggests, is a brute force solution of the same problem. So, just to show you, I made a submission where it TLE'd here.

Now the in the case of windows, you can create a .cmd file, to create a program that : generates a test case, saves in a text file, uses the same text file to run on the normal solution and the brute forces solution, captures their output in two different text files, and compares these text files.

Here's the code for this:

GeneratorTrashProblem.exe > generatorTrashProblem.txt 
(TrashProblemBrute.exe < generatorTrashProblem.txt) > BruteResult.txt
(TrashProblem.exe < generatorTrashProblem.txt) > NormalResult.txt
fc BruteResult.txt NormalResult.txt

Remember, that it can be improved by adding a loop, and testing until the outputs aren't same. I am lazy, so please help me by telling me how to do those.

By using this, I was able to generate a test case which caused issue in my solution. So I was able to fix that and get a AC.

This was the minor bug that was causing the issue:

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it
while((int)p.size()<n)
{
    int g = rand()%100 ;
    if(st.count(g)==0) p.pb(g),st.insert(g) ;
}

Isn't creating a vector that stores 1 — 100 and applying random shuffle better?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Umm maybe. How would you do that?

    Edit : Are you saying that the vector be of size 100, and we shuffle it, and we take only the first $$$n$$$ elements in consideration?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      vector<int> vec(100);
      iota(vec.begin(), vec.end(), 0);
      random_shuffle(vec.begin(), vec.end());