2 remove unnecessary sentence
source | link

I can see many possible approaches, but let me outline one approach that I think might be effective and might give reasonable accuracy with a reasonable amount of effort. It uses Monte Carlo simulation, independence, and linearity of expectation. I'm going to break it down into bite-sized pieces, by identifying a set of smaller subproblems and explaining how to solve each subproblem, then showing how to combine those solutions to the subproblems to solve the original programming contest problem.

Subproblem 1. Given two circles $C,C'$ in the square, determine whether they intersect.

Solution 1. Let $C$ be centered at the point $(x,y)$ and have radius $r$, and $C'$ be centered at $(x',y')$ with radius $r'$. Note that the two circles overlap if and only if the distance between the two centers is at most $r+r'$, i.e., if and only if $(x-x')^2 + (y-y')^2 \le (r+r')^2$. This condition is easy to test, as a function of $x,y,r,x',y',r'$.

Subproblem 2. Suppose the first circle is given by $C$. Compute the probability $p(C)$ that the second circle will not intersect $C$, as a function of $C$.

Solution 2. Let $C$ be centered at the point $(x,y)$ and have radius $r$. We will use Monte Carlo simulation. In particular, perform 10,000 trials, where in each trial, we randomly drop the second circle $C'$ and test whether $C,C'$ intersect (using solution 1 above to test for an intersection). Count the number of trials where they do not intersect and divide by 10,000; that is your estimate of $p(C)$. (It may be possible to solve this subproblem analytically, by solving a three-dimensional integral; however, that does not sound fun. Monte Carlo simulation is easier.)

Subproblem 3. Suppose the first circle is given by $C$. Compute the probability $p'(C)$ that none of the remaining $N-1$ circles will intersect $C$, as a function of $C$.

Solution 3. Note that, by independence, $p'(C) = p(C) \times \cdots \times p(C) = p(C)^{N-1}$. This is easy to compute.

Subproblem 4. Compute the probability $q_1$ that, if you drop $N$ circles randomly, none of the last $N-1$ circles has any intersection with the first circle.

Solution 4. Note that, if we let $C$ be a random variable, we have $q_1 = E[p'(C)]$, where the expectation is taken over $C$. Use Monte Carlo simulation. Perform 10,000 trials, where in each trial you randomly choose a circle $C$, then you compute $p'(C)$ (using solution 3). Average the results over all of the trials. That is your estimate of the probability $q_1$.

Subproblem 5. Compute the probability $q_i$ that, if you drop $N$ circles randomly, the $i$th circle has no intersection with any of the other $N-1$ circles.

Solution 5. By symmetry, $q_i = q_1$, so solution 4 already provides the answer.

The original problem. Compute the expected number of circles that have no intersection with any other circle, if you drop $N$ circles randomly.

Solution. By linearity of expectation, this is $q_1+q_2+\cdots+q_N$. By solution 5, this is $N \times q_1$. Now use solution 4 to compute $q_1$, and you have your answer to the original problem.

I can see many possible approaches, but let me outline one approach that I think might be effective and might give reasonable accuracy with a reasonable amount of effort. It uses Monte Carlo simulation, independence, and linearity of expectation. I'm going to break it down into bite-sized pieces, by identifying a set of smaller subproblems and explaining how to solve each subproblem, then showing how to combine those solutions to the subproblems to solve the original programming contest problem.

Subproblem 1. Given two circles $C,C'$ in the square, determine whether they intersect.

Solution 1. Let $C$ be centered at the point $(x,y)$ and have radius $r$, and $C'$ be centered at $(x',y')$ with radius $r'$. Note that the two circles overlap if and only if the distance between the two centers is at most $r+r'$, i.e., if and only if $(x-x')^2 + (y-y')^2 \le (r+r')^2$. This condition is easy to test, as a function of $x,y,r,x',y',r'$.

Subproblem 2. Suppose the first circle is given by $C$. Compute the probability $p(C)$ that the second circle will not intersect $C$, as a function of $C$.

Solution 2. Let $C$ be centered at the point $(x,y)$ and have radius $r$. We will use Monte Carlo simulation. In particular, perform 10,000 trials, where in each trial, we randomly drop the second circle $C'$ and test whether $C,C'$ intersect (using solution 1 above to test for an intersection). Count the number of trials where they do not intersect and divide by 10,000; that is your estimate of $p(C)$. (It may be possible to solve this subproblem analytically, by solving a three-dimensional integral; however, that does not sound fun. Monte Carlo simulation is easier.)

Subproblem 3. Suppose the first circle is given by $C$. Compute the probability $p'(C)$ that none of the remaining $N-1$ circles will intersect $C$, as a function of $C$.

Solution 3. Note that, by independence, $p'(C) = p(C) \times \cdots \times p(C) = p(C)^{N-1}$. This is easy to compute.

Subproblem 4. Compute the probability $q_1$ that, if you drop $N$ circles randomly, none of the last $N-1$ circles has any intersection with the first circle.

Solution 4. Note that, if we let $C$ be a random variable, we have $q_1 = E[p'(C)]$, where the expectation is taken over $C$. Use Monte Carlo simulation. Perform 10,000 trials, where in each trial you randomly choose a circle $C$, then you compute $p'(C)$ (using solution 3). Average the results over all of the trials. That is your estimate of the probability $q_1$.

Subproblem 5. Compute the probability $q_i$ that, if you drop $N$ circles randomly, the $i$th circle has no intersection with any of the other $N-1$ circles.

Solution 5. By symmetry, $q_i = q_1$, so solution 4 already provides the answer.

The original problem. Compute the expected number of circles that have no intersection with any other circle, if you drop $N$ circles randomly.

Solution. By linearity of expectation, this is $q_1+q_2+\cdots+q_N$. By solution 5, this is $N \times q_1$. Now use solution 4 to compute $q_1$, and you have your answer to the original problem.

I can see many possible approaches, but let me outline one approach that I think might be effective and might give reasonable accuracy with a reasonable amount of effort. It uses Monte Carlo simulation, independence, and linearity of expectation. I'm going to break it down into bite-sized pieces, by identifying a set of smaller subproblems and explaining how to solve each subproblem, then showing how to combine those solutions to the subproblems to solve the original programming contest problem.

Subproblem 1. Given two circles $C,C'$ in the square, determine whether they intersect.

Solution 1. Let $C$ be centered at the point $(x,y)$ and have radius $r$, and $C'$ be centered at $(x',y')$ with radius $r'$. Note that the two circles overlap if and only if the distance between the two centers is at most $r+r'$, i.e., if and only if $(x-x')^2 + (y-y')^2 \le (r+r')^2$. This condition is easy to test, as a function of $x,y,r,x',y',r'$.

Subproblem 2. Suppose the first circle is given by $C$. Compute the probability $p(C)$ that the second circle will not intersect $C$, as a function of $C$.

Solution 2. We will use Monte Carlo simulation. In particular, perform 10,000 trials, where in each trial, we randomly drop the second circle $C'$ and test whether $C,C'$ intersect (using solution 1 above to test for an intersection). Count the number of trials where they do not intersect and divide by 10,000; that is your estimate of $p(C)$. (It may be possible to solve this subproblem analytically, by solving a three-dimensional integral; however, that does not sound fun. Monte Carlo simulation is easier.)

Subproblem 3. Suppose the first circle is given by $C$. Compute the probability $p'(C)$ that none of the remaining $N-1$ circles will intersect $C$, as a function of $C$.

Solution 3. Note that, by independence, $p'(C) = p(C) \times \cdots \times p(C) = p(C)^{N-1}$. This is easy to compute.

Subproblem 4. Compute the probability $q_1$ that, if you drop $N$ circles randomly, none of the last $N-1$ circles has any intersection with the first circle.

Solution 4. Note that, if we let $C$ be a random variable, we have $q_1 = E[p'(C)]$, where the expectation is taken over $C$. Use Monte Carlo simulation. Perform 10,000 trials, where in each trial you randomly choose a circle $C$, then you compute $p'(C)$ (using solution 3). Average the results over all of the trials. That is your estimate of the probability $q_1$.

Subproblem 5. Compute the probability $q_i$ that, if you drop $N$ circles randomly, the $i$th circle has no intersection with any of the other $N-1$ circles.

Solution 5. By symmetry, $q_i = q_1$, so solution 4 already provides the answer.

The original problem. Compute the expected number of circles that have no intersection with any other circle, if you drop $N$ circles randomly.

Solution. By linearity of expectation, this is $q_1+q_2+\cdots+q_N$. By solution 5, this is $N \times q_1$. Now use solution 4 to compute $q_1$, and you have your answer to the original problem.

1
source | link

I can see many possible approaches, but let me outline one approach that I think might be effective and might give reasonable accuracy with a reasonable amount of effort. It uses Monte Carlo simulation, independence, and linearity of expectation. I'm going to break it down into bite-sized pieces, by identifying a set of smaller subproblems and explaining how to solve each subproblem, then showing how to combine those solutions to the subproblems to solve the original programming contest problem.

Subproblem 1. Given two circles $C,C'$ in the square, determine whether they intersect.

Solution 1. Let $C$ be centered at the point $(x,y)$ and have radius $r$, and $C'$ be centered at $(x',y')$ with radius $r'$. Note that the two circles overlap if and only if the distance between the two centers is at most $r+r'$, i.e., if and only if $(x-x')^2 + (y-y')^2 \le (r+r')^2$. This condition is easy to test, as a function of $x,y,r,x',y',r'$.

Subproblem 2. Suppose the first circle is given by $C$. Compute the probability $p(C)$ that the second circle will not intersect $C$, as a function of $C$.

Solution 2. Let $C$ be centered at the point $(x,y)$ and have radius $r$. We will use Monte Carlo simulation. In particular, perform 10,000 trials, where in each trial, we randomly drop the second circle $C'$ and test whether $C,C'$ intersect (using solution 1 above to test for an intersection). Count the number of trials where they do not intersect and divide by 10,000; that is your estimate of $p(C)$. (It may be possible to solve this subproblem analytically, by solving a three-dimensional integral; however, that does not sound fun. Monte Carlo simulation is easier.)

Subproblem 3. Suppose the first circle is given by $C$. Compute the probability $p'(C)$ that none of the remaining $N-1$ circles will intersect $C$, as a function of $C$.

Solution 3. Note that, by independence, $p'(C) = p(C) \times \cdots \times p(C) = p(C)^{N-1}$. This is easy to compute.

Subproblem 4. Compute the probability $q_1$ that, if you drop $N$ circles randomly, none of the last $N-1$ circles has any intersection with the first circle.

Solution 4. Note that, if we let $C$ be a random variable, we have $q_1 = E[p'(C)]$, where the expectation is taken over $C$. Use Monte Carlo simulation. Perform 10,000 trials, where in each trial you randomly choose a circle $C$, then you compute $p'(C)$ (using solution 3). Average the results over all of the trials. That is your estimate of the probability $q_1$.

Subproblem 5. Compute the probability $q_i$ that, if you drop $N$ circles randomly, the $i$th circle has no intersection with any of the other $N-1$ circles.

Solution 5. By symmetry, $q_i = q_1$, so solution 4 already provides the answer.

The original problem. Compute the expected number of circles that have no intersection with any other circle, if you drop $N$ circles randomly.

Solution. By linearity of expectation, this is $q_1+q_2+\cdots+q_N$. By solution 5, this is $N \times q_1$. Now use solution 4 to compute $q_1$, and you have your answer to the original problem.