Hey! In the last contest I was getting TLE on a problem, I thought my solution was not optimal, now I tried to solve it but using a loop to clear all elements of the array instead of "memset" -which I was using- and I got AC!! So which one is better ??
UPD: found that the TLE then using "memset" was because there was a mistake with the size of the array (which I don't know why I got TLE not RTE or something like that!!). But anyway, the time for the solution when using a "for" loop is like " 156 ms ", while it is " 1294 ms " when using "memset !!!
your loop resets values in range [0, n], but memset one resets the whole array which is very large.
Auto comment: topic has been updated by aza-zil (previous revision, new revision, compare).
Change
To:
Is there any significant difference between i) memset ( ctrN , 0 , sizeof ctrN ) ; and ii) memset ( ctrN , 0 , n * sizeof(ll) ) ; // assuming n is size of the array ctrN
In ii) you need to know that variable n is a size of array and ll is a type of element. In i) you can know nothing. No difference in runtime because third parameter just number, equal to num of bytes we need to set.
I'm always using
std::fill(all(arr), 0);
in code with#define all(x) std::begin(x), std::end(x)
. For this example, with Ofast runtime is same, but std::fill more generic and can be applied forstd::vector
with same runtime and forstd::array
with same runtime.For array on stack there is a bug on codeforces, because stack limited by 256 MB even for problems with memory limit 512 MB, 768 MB, 1024 MB, but vector allocates memory on heap and works well.
This code in codeforces custom invocation gets RE with stack overflow:
This code works well:
FYI:
Basically, use memset if you're calling it on big arrays a few times and you're setting the same value for each byte. Use a for loop if you're not setting the same value for each byte (don't use memset to set an int to 0xFF00FF00) or if you're using it very often on smaller arrays. Use a templated for loop if you can afford a fixed nice value of $$$n$$$.