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

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); for Java
Автор ganesh_6, история, 2 года назад, По-английски

What is the alternative to mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); in c++ for Java? Tagging users who use Java for Problem Solving

taran_1407 SecondThread

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

»
2 года назад, # |
← Rev. 5   Проголосовать: нравится -8 Проголосовать: не нравится

well, Java's random number generator from java.util is quite uniform so you can use that. You can use System.currentTimeMillis() as a seed if you want the seed to change everytime you run the code.

I still think you could've found this with a simple search on google, though. No need to ping the Java users (and tourist), too.

upd: I found that you pinged them twice, and thats just too excessive. Please refrain from pinging people publicly unless you ABSOLUTELY (yes, most of the time you don't) have to. I learnt this the hard way and I don't want you to do the same. If you need help from them you can kindly ask them via private message.

→ Ответить
  • »
    »
    2 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    I tried that and it did not work, it gives different value every time as output. SO i asked here. https://pastebin.com/zYPUTvz1

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      It using different values every time is the entire point of what people are trying to do with seeding their random number generator with the time. People do that so that others can't hack them with an adversarial test cases where they get unlucky with the random numbers they choose. In order for someone to hack you, they'd have to correctly guess the millisecond that your code would run. (you can seed it off nanotime if you want them to have to guess the nanosecond, which is practically impossible)

      To answer your question, new Random() in java defaults to being based of the clock, which means it'll have this different-every-time behavior by default. This is the equivalent.

      If you don't want it be be different every time, you can seed your Random off a constant like Random rand = new Random(5);.

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

Java solution and editorial to https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/A2/solution

Finally solved it and got AC. Thanks to taran_1407 for explaining his approach (I used his approach to solve this) and clearing all my doubts with patience. Thanks to hihihizaru for explaining the editorial approach and an example on creating our own hash function. The editorial approach/one given by you does not work in java because there would be hash collisions while calculating the right_sum-left_sum of the given range and also there would be collisions while using Long in Segment/BIT.

Note/Knowlege share: "Random().nextLong() is almost equivalent to mt19937 as I know" — Taranpreet Singh

Approach: Same as explained below by hihihizaru but instead of creating hash like that we can use Random.nextInt() method. Please see the submission here: https://pastebin.com/FSg9Yq83 . "The Implementation of Random is pretty well distributed. I used higher number of random number mapping as instead of going with 64-bit range, My numbers were distributed in range of int, 32 bit numbers, leading to collision probability across 10^6 queries to be 1-(1-10^(-3))^(10^6) ~ , which could realistically fail. So I used 10 randomizations to achieve better success probability." — Taranpreet Singh

Note: Here Yes, by hash collision, I mean the same one as mentioned in the editorial "garbage value mapping back to h(A)".

If I had used 64 bit range, I probably would have needed only 2 hash functions, or even 1 might have sufficed. If i used Random().nextLong() instead of randInt(), it's almost equivalent to mt19937 as I know.

My idea behind using 32 bit range was that I didn't want values in segment tree/BIT to overflow 64 bit range and potentially cause collision. If you notice, any value in my segment tree wouldnt exceed N*2^32 < 10^15, so overflow won't happen.

Ofcourse, you can simply let overflow happen and use 64 bit numbers as used in editorial, but I preferred mine.

Finally, Thanks to SecondThread. Although he could not help me in providing code editorial or help me resolve my issue in solving this in Java. He explained about Random numbers and using seed to get same set of random numbers every time and how people use seed to not make others hack their code, see the discussion here: https://codeforces.net/blog/entry/107359

Note: I am sharing this journey to help people who could not solve this/ inspire that we should leave a problem unsolved instead learn and solved it. It teaches a lot. You may be a Newbie but if you are still a newbie after couple of years then it's your mistake

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

    Thanks for sharing your learnings

    A couple of points though
    1. The approach shared in editorial using 64 bit overflow can work in java, only I haven't used 64 bit modulo hash yet, specifically due to unavailability of Unsigned long data type (I know binary remains same, but I prefer not to use). The overflow due to summing N values when taken mod, would still end up as a random garbage value, so overflow is not a bit issue.
    2. On mt19937, my point was only from their usage in competitions. There's a lot of theoretical content available on RNGs, their distribution, period etc, which may significantly differ for Random.nextLong() vs mt19937.
    3. The number 10 is just a value I chose here. By continuing above probabilistic analysis, we can determine minimum number of hash to make failure probability < some small limit. Its a tradeoff between time taken to run your solution vs success probability.

    → Ответить