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

subscriber Hacking during Contests
Автор vkditya0997, история, 9 лет назад, По-английски

Recently,

I have seen subscriber 's youtube channel, It is very useful and I thank all the coders who upload their screencasts and helping for the community.

Interesting thing is,
He uses some C++ code to generate random test cases to test his solution and to hack some other's solution
I would like to hear some tips on how to generate random test cases in C++ ?

Yeah , rand() function can be used but shows same integer every time after it's execution.
So, It would be interesting, If some of the coders in this community share their tips on how to generate those test cases.

and also I can see that Far Manager Editor is pretty Powerful!, How to use it?
Any similar Editor on Linux Ubuntu ?

I even like to see tourist coding during codeforces/topcoder/codechef rounds.

Hope that he notices this post and uploads screen cast as Petr, Egor, subscriber, many others ... does :)

Thanks everyone!!
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

srand(time(NULL)); -_-

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Do not. It will be reinitialized once a second only. Rather painful discovery, especially if you try using that for stress testing.

    Cheat sheet for x86 (assuming GCC):

    long long x;
asm("rdtsc" : "=A"(x));
srand(x);

    One can also try reading bytes from /dev/urandom on Linux and initialize generator with first several bytes.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
#include <stdlib.h>
#include <time.h>

srand(time(0)); int x=rand();

Now you can random any integer you like, marking the range using modular division

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Yeah , rand() function can be used but shows same integer every time after it's execution.

Without calling srand(...) or if you call srand(x) with the same x, the rand() function will be generating the same random sequence on every execution. It's actually pretty useful property which allows you to re-generate the same test case when you re-run the program (e.g. if you want to debug your solution). So you can still generate a test case even without calling srand(...) and you should use srand(...) only if you want to reset the random sequence.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

By the way, Codeforces requires your generator to be predictable (as far as I know), that is, it should print same output regardless of current time, i.e. you should use fixed random seed.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    This rule can't be held because in other way every right hash solution could have been easily hacked. It would have been nonsense.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      1. Codeforces does require test generators to generate tests reproducibly, as per point 29 here.

      2. Codeforces does not require solutions to generate answers reproducibly.

      3. Yes, solutions using reproducible hashing can be hacked in a contest.

      → Ответить