Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

Автор Naithani, история, 4 года назад, По-английски

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:)

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

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

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

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

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

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

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}$$$.

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

    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.

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

      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.

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

        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.