TAPOINT - editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Tuấn Anh Trần Đặng
Tester: Kamil Dębowski
Editorialist: Tuấn Anh Trần Đặng

DIFFICULTY:

Medium

PREREQUISITES:

Geometry, Math

Problem

Given a circle and a number K find one point that is with in the circle, not on the circle border and not further than K/100 from the circle border.

Solution

We need to find x and y such that (R - k/100)^2 <= x^2 + y^2 <= R^2. With small R we may try all possible values of x from 1 to R - 1 and find y = the integer part of sqrt(R^2 - x^2). The trick is if R is large enough you will find the solution with x = R - 1. More specifically in this problem, if R is larger than 20000 then the solution would be x = R - 1 and y = integer part of sqrt(R^2 - x^2)

Proof

Let q = the integer part of sqrt(R^2 - (R-1)^2) = sqrt(2*R - 1). We need to proof that when R is large enough the following condition must be true:

  • (R - k/100) ^ 2 < (q^2 + (R - 1)^2) < R^2.

The second part of the inequation is obvious so let’s focus on the first part:

  • (R - k/100)^2 < q^2 + (R - 1)^2

From the definition of q we have that:

abs(q - sqrt(2*R - 1)) <= 1

=> q >= sqrt(2 * R - 1) - 1

=> q^2 >= 2*R - 1 - 2 * sqrt(2 * R - 1) + 1

<=> q^2 >= 2 * R - 2 * sqrt(2 * R - 1)

add (R-1)^2 into both side of the inequations:

q^2 + (R - 1)^2 >= 2 * R - 2 * sqrt(2 * R - 1) + (R - 1)^2

<=> q^2 + (R - 1)^2 >= R^2 - 2 * sqrt(2*R - 1) + 1. (1)

With R is large enough it’s obvious to see that 2 * sqrt(2 * R - 1) + 1< 2 * (k/100) * R + (k/100) ^ 2 (2). Finding how exactly would be the large enough value left as an exercise for you.

From (1) and (2) we have:

with R is large enough:

q^2 + (R - 1)^2 > R^2 - 2 * (k/100) * R + (k/100)^2

<=> q^2 + (R - 1) ^ 2 > (R - k/100)^2 (this is what we need to prove).

Author’s/Tester’s Solutions:

Setter’s solution
Tester’s solution

2 Likes
2

The bad side of this question was that someone could have just iterated 10^6 times from x=R-1 to x=R-1-10^6 so 10^6 * 100 test cases suffices in time, and get solution accepted. Nice maths though :smiley:

3

but the constraints were of the order 10^9 so this could TLE …

4

This problem can also be done by some sort of dfs.

Start form (R,0) and move one point left(to (R-1,0)) and one point up(to (R,1)) and then keep moving like this for all points.

S= ${set of all points that satisfy the given conditions}$

Whichever point you reach check if that point can be the answer.

Don’t go further from point P_{1}, when you reach a point P_{1} from which no point P_{2} \in S can be reached.

This should cover all points, and if no point satisfies the conditions then print -1.

[my solution][1]
[1]: CodeChef: Practical coding for everyone