Блог пользователя xiaruize

Problem with C++ compilers of Codeforces
Автор xiaruize, история, 3 месяца назад, По-английски

I used random_device in order to generate a random number in this code.

On my own Windows, Ubuntu Virtual Machine and WSL, this code can generate different random numbers each time, but on Codeforces it generates the same number every time, so this gives people a way to hack your submission even if xor-hashing is in the formal editorial and the possibility of coincidence in hashing is nearly impossible.

I submitted the same code in C++20 and C++23, got Accepted. So I am wondering that is this problem only for C++17 or just nobody know the number of random_device in C++20 and C++23, so that they are not able to make a hack.

I suppose this problem should be fixed in order to avoid more solutions being hacked because of unawareness of a fixed 'random' number.

Or any other way to generate random numbers is suggested?

p.s. I tried $$$40000$$$ times on my PC and got all correct.

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

From the docs:

std::random_device may be implemented in terms of an implementation-defined pseudo-random number engine if a non-deterministic source (e.g. a hardware device) is not available to the implementation. In this case each std::random_device object may generate the same number sequence.
...
A notable implementation where std::random_device is deterministic in old versions of MinGW-w64 (bug 338, fixed since GCC 9.2). The latest MinGW-w64 versions can be downloaded from GCC with the MCF thread model."

random_device just is not what you can really rely on.

Better use something like current time as seed.

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
→ Ответить