You are not logged in. Please login at www.codechef.com to post your questions!

×

KOL16G - Editorial

0
1

PROBLEM LINK:

Practice
Contest

Editorialist: Soumik Sarkar

DIFFICULTY:

HARD

PREREQUISITES:

Binary search, Numerical integration

PROBLEM:

Find the radius of a circle such that the average distance from any point inside the circle to a fixed point $P$ located outside the circle at $d_{min}$ distance from the circumference equals $D_{avg}$.

QUICK EXPLANATION:

The average distance is a monotonously increasing function of the radius. Binary search on the radius to find the value for which average distance is $D_{avg}$. The average distance can be computed through definite integrals whose limits depend on the radius.

EXPLANATION:

It is clear that $D_{avg}$ is a function of the radius $r$ and $d_{min}$. Since $d_{min}$ is constant, it solely depends on $r$. The key observation is that $D_{avg}$ monotonously increases with increase in $r$. Hence it is possible to use binary search on $r$ to get the answer.

But how do we calculate $D_{min}$ for some $r$? Surely we cannot find the distance from each of the infinite points inside the circle to $P$ and take their average...
Actually we can, thanks to calculus! If you are not familiar with calculus, and even if you are, I would love to recommend this Essence of calculus playlist by 3Blue1Brown.

pic1

Consider our circle on the X-Y plane with the center at $(0, 0)$ and radius $r$. The point $P$ is located at $(r+d_{min}, 0)$. Let $f(x, y)$ be the function that returns the distance between the points $(x, y)$ and $P$. So $$f(x, y) = \sqrt{(r+d_{min}-x)^2 + y^2}$$

Now imagine if for every point in the circle we could compute $f(x, y)$ and plot its value as a point above it in 3D space. Then the entire plot would form a surface above the X-Y plane. Then the required $D_{avg}$ is just the average height of a point on this surface. And this is nothing but the volume under the surface divided by the area it covers on the X-Y plane. The latter is just the area of the circle, so the main task is to find the volume.
For example, for $r = 20$ and $d_{min} = 5$, the volume of this structure needs to be calculated.

pic2

The volume under the surface is the double integral of $f$ over the domain of the circle $$\begin{align} V &= \iint_{x^2 + y^2 \le r^2} f(x, y) \,dx \,dy \\ &= \iint_{x^2 + y^2 \le r^2} \sqrt{(r+d_{min}-x)^2 + y^2} \,dx \,dy \end{align}$$

This form doesn't help us, so let us separately integrate over $x$ and $y$. Inside the circle $x$ ranges from $-r$ to $r$. And for a particular $x$, $y$ ranges from $-\sqrt{r^2 - x^2}$ to $\sqrt{r^2 - x^2}$. Notice that $f(x, y) = f(x, -y)$, so to keep things simple we can find the integral over the upper half of the circle only, and double it to get the total volume. Over the upper half only, $y$ ranges from $0$ to $\sqrt{r^2 - x^2}$.

$$V = 2 \int_{-r}^{r} dx \int_{0}^{\sqrt{r^2 - x^2}} \sqrt{(r+d_{min}-x)^2 + y^2} \,dy$$

Let $Y = \sqrt{r^2 - x^2}$ and $a = r+d_{min}-x$. Then by using standard formulae $$\begin{align} V &= 2 \int_{-r}^{r} dx \int_{0}^{Y} \sqrt{a^2 + y^2} \,dy \\ &= 2 \int_{-r}^{r} \left( \frac{Y}{2} \sqrt{a^2 + Y^2} + \frac{a^2}{2} \ln \left| \frac{Y + \sqrt{a^2 + Y^2}}{a} \right| \right) \, dx\\ \end{align}$$

We still have an integration left to perform and it looks terrible already. Luckily, being programmers, we can numerically integrate over $x$. The simplest method is the rectangle method. Better methods such as the trapezoidal rule or Simpson's 1/3 rule can also be used. A sufficiently small size of the intervals should be chosen for the error to be small. Around $10^4$ divisions works fine.

Alternate inner integral (easier)

pic3

As can be seen, integrating the term $\sqrt{(r+d_{min}-x)^2 + y^2}$ is complicated, but there is a smarter way. Consider a curve $C$ which is a circular arc with center $P$. Instead of integrating over vertical lines as before, we can instead perform line integrals along curve such as these from the $x$-axis to the point where it intersects the circumference. Why is this easier? That's because all points on this curve are at the same distance from $P$. Let this distance be $L$, then the line integral is just $L$ times the length of the $C$.

$$L = r + d_{min} - x $$

The angle $\theta$ can be obtained by using the law of cosines. $$\theta = \cos^{-1} \left( \frac{-r^2 + L^2 + (r+d_{min})^2}{2L(r+d_{min})} \right)$$

The length of $C$ is given by $L \theta$. Then the line integral can be obtained as $L^2 \theta$. The rest of the algorithm remains the same. The new integral to be calculated is below where $L$ and $\theta$ are determined by $x$ as shown above. $$\begin{align} V &= 2 \int_{-r}^{r} dx \int_C L \,ds \\ &= 2 \int_{-r}^{r} L^2 \theta \, dx \end{align}$$

Regardless of the integral used, once the volume $V$ is obtained the average distance to $P$ can be calculated as $V / \pi r^2$. Hence now it is possible to binary search over $r$ to find the answer.

Each integration uses $\approx 10^4$ iterations, and there are $\log_2(\varepsilon \cdot D_{avg})$ integrations performed by the binary search procedure where $\varepsilon$ is the acceptable error. So complexity is $\mathcal{O}(10^4 \log(\varepsilon \cdot D_{avg}))$.

EDITORIALIST'S SOLUTION:

Editorialist's solution can be found here.

asked 30 Oct '17, 18:32

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

edited 14 Nov '17, 02:47

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,359
×647
×100
×53
×9

question asked: 30 Oct '17, 18:32

question was seen: 488 times

last updated: 14 Nov '17, 02:47