vkditya0997's blog

subscriber Hacking during Contests
By vkditya0997, history, 9 years ago, In English

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!!
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

srand(time(NULL)); -_-

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
#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

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      → Reply