Why is memset causing problem despite being used on built-in types?

Question

I am very new to C++ and was making a submission to this problem on Codeforces and suddenly found that using memset() was causing Wrong answer to one of the test cases.

Here is the test case:

Input:
4 4
3 3 3 5
Participant's output
NO
Jury's answer
YES
1 2 3 4 
Checker comment
wrong answer Jury has the answer but the participant hasn't

Here is the code:

#include<iostream>
using namespace std;


int check_if_painted[5010][5010];
int input_array[5010];
int main(){

    int n,k;
    cin>>n>>k;

    int occurence_count[n];//Keeps track of the total no. of occurences of an element in the input_array.
    memset(occurence_count,0,sizeof(occurence_count));
    /*
    The following loop checks if the occurrence of a particular 
    element is not more than k. If the occurence>k the "NO" is printed and program ends.
    */
    for (int i = 0; i < n; ++i)
    {
        cin>>input_array[i];
        ++occurence_count[input_array[i]];
        if(occurence_count[input_array[i]]>k){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES\n";


    /*
    The following loop uses the array check_if_painted as a counter to check if the particular 
    occurrence of an element has been painted with a colour from 1 to k or not. 
    If some previous occurrence of this particular element has been painted with f%k+1, 
    then f is incremented until we encounter any value(of `f%k+1`) from 1 to k that hasn't been 
    used yet to colour and then we colour this element with that value by printing it.
    */
    int f=0;//
    /*
    f is a global value which increments to a very large value but f%k+1 is used 
    to restrict it within the 1 to k limit(both inclusive). So, we are able to check 
    if any previous occurrence of the current element has already been coloured with the value f%k+1 or not.  
    which essentially is 1 to k.
    */ 
    for(int i=0;i<n;++i){
        while(check_if_painted[input_array[i]][f%k+1]>0){
            ++f;
        }
        cout<<f%k+1<<" ";
        ++check_if_painted[input_array[i]][f%k+1];
        ++f;
    }
    return 0;
}

But, when I tried the below code, It was accepted successfully.

#include<iostream>
using namespace std;


int check_if_painted[5010][5010];
int input_array[5010];
int occurence_count[5010];
int main(){

    int n,k;
    cin>>n>>k;




    for (int i = 0; i < n; ++i)
    {
        cin>>input_array[i];
        ++occurence_count[input_array[i]];
        if(occurence_count[input_array[i]]>k){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES\n";



    int f=0;

    for(int i=0;i<n;++i){
        while(check_if_painted[input_array[i]][f%k+1]>0){
            ++f;
        }
        cout<<f%k+1<<" ";
        ++check_if_painted[input_array[i]][f%k+1];
        ++f;
    }
    return 0;
}

From this post on SO, I found that memset works well on built-in types. So, why is it causing the problem in my case when it has been used on an int array which is a default type.

Also, I've also read that std::fill() is better alternative and read in this post that memset is a dangerous function, then why is it still in use?

Answer 1

This doesn't have anything to do with memset. Your code is going outside the boundaries of your array, plain and simple.

In your input case you have n = 4 and k = 4, so occurrence_count is 4 elements long (its valid indexes go from 0 to 3 inclusive). Then, you do

    cin>>input_array[i];
    ++occurence_count[input_array[i]];

Given that the last value is 4, you are ultimately doing ++occurence_count[4], which goes out of the boundaries of your array. This is undefined behavior, which in your case manifests as incrementing memory not belonging to that array, which most probably doesn't start to 0 and messes up the later check.

The problem is not seen in your second code snippet, as you make occurence_count 5010 elements big and zero-inizialized by default as it is a global variable.

Now, if you are going to count occurrences of array values, of course sizing the occurrences array to be as big as the number of elements is wrong - that's the count of numbers you are going to read (and it would be fine to size input_array), not the maximum value you can read. Given that the array element values are from 1 to 5000, the occurrences array must be either sized 5001 (keeping values as they are), or sized 5000 (decrementing the values you read by 1 to index such array).

(In general, be careful as all indexes in the problem text are 1 based, while indexes in C++ are 0 based; you risk off-by-one errors if you reason with the problem indexes and then use them as C indexes, unless you over-size arrays by one and ignore the 0-th element).

---

Finally, some extra remarks:

• if you compile with enough warnings enabled or with a recent enough compiler, it'll rightly complain as memset is not defined or that it is being implicitly defined (with an incorrect prototype, BTW); you should #include <string.h> to use memset;

• as @Nicol Bolas went to a great length to explain in his answer, you are using VLAs (variable length arrays) when declaring a local array with size known only at runtime (int occurence_count[n]).

  VLAs aren't standard C++, so they aren't well specified, several compilers don't support them and, in general, are problematic in a number of ways (mostly, you shouldn't really allocate an unknown amount of data on the stack, which is generally small);

  You should probably avoid them in favor of std::vector or, given that the problem provides you an upper limit of both colors and elements (5000), just static arrays.