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:)
Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).
Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).
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}$$$.
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,idxis suspicious, to pickidx, 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.Your first pick based on
idxis 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.
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.