Naithani's blog

Best way to pick index in array randomly in C++?
By Naithani, history, 4 years ago, In English

Hello Codeforces, I was solving the problem, and I got the right idea, but there was a problem with choosing the index randomly using uniform_int_distribution<int>.

sol1: This gives me WA at test case 32 because I was trying to pick index directly.

sol2: Now, at this time I pick randomly with lower_bound, and it worked.

Is there any better way to choose index uniformly and randomly?

Thanks in advance:)

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).

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

Your first solution is wrong on a testcase with two squares with different sizes, say $$$a<b$$$. Your solution will pick a point in the first square with probability $$$\frac 12$$$ instead of $$$\frac{a^2}{a^2+b^2}$$$.

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

    In my first solution, my first pick is based on the index idx, and if I get this right then rest of the portion is same in both sol1 and sol2. That means, idx is suspicious, to pick idx, I'm using random number generator between [0, n-1] which doesn't depend on the size of rectangles. Then, how you can say, it depends on the size of the square/rectangles.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your first pick based on idx is wrong. Your first pick should be biased based upon areas as ivan stated.

      If there are two rectangles/squares with different sizes. One has more integer coordinates as compared to the other so a point that is finally picked is more likely to be situated in the rectangle with the bigger area.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So, you mean to say that my pick should depend on the area of the rectangle. But in my code, it just picks randomly any index without any dependency of area.

        → Reply