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

×

TAPOINT - editorial

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

This question is marked "community wiki".

asked 18 Sep '16, 15:50

tuananh93's gravatar image

5★tuananh93
116613
accept rate: 0%

edited 19 Sep '16, 00:28

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 19 Sep '16, 00:33

nidzulandz's gravatar image

6★nidzulandz
15318
accept rate: 0%

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

link

answered 19 Sep '16, 01:15

include_sajal's gravatar image

4★include_sajal
1716
accept rate: 0%

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

link

answered 03 Jan '17, 20:13

prakhariitd's gravatar image

6★prakhariitd
1.1k211
accept rate: 10%

edited 03 Jan '17, 20:15

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
×2,657
×890
×647
×42
×6

question asked: 18 Sep '16, 15:50

question was seen: 2,648 times

last updated: 03 Jan '17, 20:15