An example would be any problem which requires random numbers of the order 100 000 or greater. Here's one such problem (from local training in Russian, so no public contest link, sorry!):

The jury has a string of 2n letters (1 ≤ n ≤ 100 000), fixed in advance in each test. Of these, exactly n are as, and exactly n are bs. The contestant known only the value of n, and has to find any letter a in the string. For that, the contestant can interactively ask up to 100 questions of the form “what is the letter at position p?”, and the jury gives back the letter. As soon as it is an a, the contestant's solution passes the test.

Sounds simple, right? But the actual number of incorrect attempts is usually considerable, and a good portion of them is the result of using rand() (the judge is using Windows and MinGW / Visual Studio, so the upper bound is 32 767, as explained in the post).

I recall several problems requiring "pick random element" idea, where you can easily get WA if you aren't really picking random element.

Example: you have N lines, no two of them are parallel, you know that there is a point P such that at least N/2 lines pass through that point, your task is to find this point.

You'd want to take random pair of lines and check if their intersection is a solution, right? Sounds like 1/4 chance of guessing it for each try. Or zero chance, if the test has been build in such a way that all "good" lines have IDs larger than 32767 and you don't do any random_shuffle on the input (because why would you?..)

Sure, fair question. While the mediocre results of random_shuffle will often still be good enough for you to pass a problem (case in point: 39639107), one big situation where you really need good randomization in your code is when doing hashing.

When hashing you don't want to use fixed values, as someone can find a hack for your code fairly easily using a collision attack.

If you choose your multiplication base using rand(), you'll be limiting yourself to 32767 possible values which isn't ideal. Worse, if you choose your hashing mod using rand(), you'll be stuck with a very small mod value and extremely prone to collisions on big test cases.

Even if you look for a mod by generating, e.g., 1000000000 + rand() and repeating until prime, this only leaves you with about 1600 primes that you could end up with. It's actually very doable to perform a separate collision attack on each of those primes and concatenate all of the results into a single monster string that breaks this code. Especially so in a contest with an open hacking phase.

Another common practice when using rand() is to do srand(time(NULL)). This is another vulnerability because time(NULL) only changes once per second, making it quite easy to hack again: just run collision attacks for each second in a 60-second range, and then submit the hack in those 60 seconds.

So in summary, you may be able to get away with using rand(). But don't do it. Just use mt19937.

AIM Tech Round 4 Div. 1 B. A lot of solutions with rand()%N and random_shuffle failed on this problem.

Second version is working almost perfectly (though to fully avoid the same effect that makes the first version bad it is better to change it to (rand() * (RAND_MAX + 1) + rand()) % (int)1e6), however the first one is a complete disaster unless you are fine with some results having probability more than 250 times higher than some other results: Simulation here, it times out on ideone, but you can run it locally.

And of course, you need to run code like this only on Windows testing systems (if RAND_MAX  = 2³¹ - 1, both versions are technically undefined behaviour and sometimes yield negative numbers anyway), so you need to also write a platform-dependent ifdef or something like this, increasing the amount of code even more.

Use functions from testlib.h if you create a contest. https://github.com/MikeMirzayanov/testlib

Tagging neal, I_love_Tanya_Romanova, Errichto and Gassa with all respect, hoping to get answer :)

Bad idea

The only advantage is that you can generate long long's now (some places like CF being exception, where rand() returns a number up to 2¹⁶). Disadvantages: smaller cycle (you will quicker get the same values), possibly losing some pseudo-random properties, slower program, you're doing something you don't understand. Read the blogs by neal.

I also got WA because of this. Apparently the MinGW implementation of std::random_device is deterministic, see https://sourceforge.net/p/mingw-w64/bugs/338/.

Go through this.

If you want to generate a random numbers between the range $$$[l,r]$$$, you should use rand()%r+l.

UPD: Really sorry :( I made a huge mistake...

to generate a random numbers between the range [l,r], use rand()%(r-l+1)+l!!

NOT rand()%r+l

By symmetry this is equivalent to the expected distance between two randomly chosen points between 0 and N. If the larger of the two chosen points is $$$x$$$, then the average distance over all choices for the other point will be $$$\displaystyle D(x) = \frac{x}{2}$$$.

We can then integrate over $$$x$$$ to find the answer. We need to know the PDF over $$$x$$$ though: it turns out that the PDF $$$P(x)$$$ should be directly proportional to $$$x$$$ since this is essentially the "number of choices" for the smaller point. So then the PDF is exactly $$$\displaystyle P(x) = \frac{x}{\int_0^N x dx} = \frac{x}{\frac{N^2}{2}}$$$. So then we get:

$$$\displaystyle \int_0^N D(x) P(x) dx = \frac{\int_0^N \frac{x^2}{2} dx}{\frac{N^2}{2}} = \frac{\int_0^N x^2 dx}{N^2} = \frac{\frac{N^3}{3}}{N^2} = \frac{N}{3}.$$$

There should be some nice non-calculus ways to think about this too. One way to visualize it is that we're looking for the "average" height of a triangular pyramid whose base is an $$$N \times N$$$ right triangle and whose height has length $$$N$$$ and is directly above the right angle of the triangle. But based on the formula for volume of a pyramid, the "average" height for any pyramid is just $$$\frac{H}{3}$$$.

As Errichto has already written above, the only advantage of this code is possibility of generating big numbers. The disadvantages are smaller cycle (you will quicker get the same values), possibly losing some pseudo-random properties, slower program. I tetsed the following code in custom test

#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int main(){
    long long sum = 0;
    for (int i = 0; i < 1e8; ++i) {
        sum += rng() / 2;
    }
    cout << sum / (int)1e8;
}

and it was running about 400 ms and printed 1073777492, which is quite near to $$$2^{30}$$$. Changing sum += rng() / 2 to sum += ((rand() << 15) | rand()) ^ ((rand() << 15) | rand()), as you are suggesting, made the program worse. It became 10 times slower (4 seconds) and printed 536866157, so the numbers are much less random.

In fact, xoring rand() ^ rand() can't make more randomized number. Really random numbers (if exist any) are already random and pseudo-random numbers still remain pseudo-random. It just can avoid failing system tests. But if there exists any hack that uses pseudo-random nature of rand(), your solution can also be hacked.

sure

IMO, yes, in a weird way.

time(0) is the integer number of seconds (whole seconds) since Unix epoch, and could be grounded to hack — this has happened before.

duration has a wider range of precision, so theoretically it's already more reliable. But it's even weirder when it comes to chrono::steady_clock... it's not even guaranteed to be measured with relativeness to Unix epoch...