LTM40CD - Editorial

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY

PREREQUISITES:

basic math and geometry

PROBLEM:

For a given integer R, print out all triangles with integer length sides, which has the radius of their inscribed circle equal to R.

QUICK EXPLANATION:

For easier subtasks use explicit iteration over all possible values of triangle sides. For the original constraints, first use simple calculations to reduce the number iterations and then enumerate all triangles.

EXPLANATION:

Let’s assume that in any valid triangle with sides a, b, c, we have a ≥ b ≥c. In solutions to all subtasks, we use the fact that if P = (a + b + c) / 2, then:

R2 = (P - a) * (P - b) * (P - c) / P

It is a basic property of inscribed circle and one can either remember it from math classes or google it.

Subtask 1

In the first subtask, we have R ≤ 3, so one can try to solve the problem by guessing upper bound on a, b, c, iterating over all combinations of them and printing out triangles with sides fulfilling the radius equation. It turns out that for R ≤ 3, the largest side of a valid triangle is 109 for R = 3, so it is possible to iterate over all a, b, c ≤ 200, where 200 can be a random (or not) guess and get accepted for such low constraints.

Subtasks 2 and 3.

For subtasks 2 and 3 more clever methods should be used. Let’s use some math then. The below solution is targeted for the original constraint, however, by missing some of the below analysis, one can came up with a solution passing only constraints in the first and second subtasks.

Just to recall, we have:

a ≥ b ≥ c
P = (a + b + c) / 2

Idea

Let’s define:

X = b + c - a
Y = a + c - b
Z = a + b - c

Then, X + Y + Z = 2 * P.

The idea is to figure out a bound for X as the smallest value among X, Y, Z. This is true, because a is the largest side of a triangle by our assumption.

Bounding X

First, if we take the equation for radius and multiply both sides by P2 , we get:

R2 * P2 = P * (P - a) * (P - b) * (P - c)

Next, observe that:

X = 2 * (P - a)
Y = 2 * (P - b)
Z = 2 * (P - c)

Now, using the fact that X + Y + Z = 2 * P, we can write:

P * X * Y * Z = 8 * P * (P - a) * (P - b) * (P - c) = 8 * R2 * P2 = 4 * R2 * P * (X + Y + P)

After this calculations, we are ready to bound the value of X. Using the fact that X ≤ Y ≤ Z the following holds:

X * X * X / (3 * X) ≤ X * Y * Z / (X + Y + Z) = 4 * R2

The last transition is true because of the above equation P * X * Y * Z = 4 * R2 * P * (X + Y + Z).

Thus, X2 / 3 ≤ 4 * R2, which is equivalent to:

X ≤ 2 * R * sqrt(3)

So in fact X is rather small, which is very nice.

Bounding Y for fixed X

Now, let’s try to define Y, for a fixed X.

Using the analogous method, we can write:

X * Y * Y / (X + Y + Y) ≤ X * Y * Z / (X + Y + Z) = 4 * R2

and from the above equation, it follows that

X * Y * Y - 8 * Y * R2 - 4 * X * R2 ≤ 0,

So for a fixed X, we ca easily iterate over all possible values of Y using the above formula.

Putting it all together

For a fixed X and Y, value of Z can be then computed as:

Z = 4 * R2 * (X + Y) / (X * Y - 4 * R2)

Now, the only remaining thing is to compute values of a, b, c, i.e. the sides of a valid triangle using values of X, Y and Z. For implementation details please refer to setter’s and tester’s solutions.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution will be uploaded soon.
Tester’s solution can be found here.

1 Like

P * X * Y * Z = 8 * P * (P - a) * (P - b) * (P - c) = 8 * R2 * P2 = 4 * R2 * P * (X + Y + P)

The last P is Z …it’s a typo…

Initially it is defined as,
X = b + c - a
Y = a + c - b
Z = a + b - c

How, using these equations we are able to deduce,
X = 2 * (P - a)
Y = 2 * (P - b)
Z = 2 * (P - c)
??

Can’t figure out what I am missing. :frowning:

My bad, I mistook P to be the perimeter, whereas it is used as the semi-perimeter here. Nevermind, got it now! :slight_smile:

X=b+c-a
Y=a+c-b
Z=a+b-c
From the above equations:-
Y+Z = 2*a

Also, X+Y+Z = 2P
So, we get X = 2
(P-a)

Use the fact that X + Y + Z = 2 * P, it is given just below definitions of X, Y, Z and it is based on the definition of P. Is it more clear right now?

I disagree with you marking this problem as easy. I don’t think that it’s easy at all for most contestants to think of the X, Y, Z substitutions, and the wall of math following them.

X * X * X / (3 * X) ≤ X * Y * Z / (X + Y + Z)

How can this be proven?

1 Like

somebody please upvote me , i have questions to ask
thank you
also please tell how constraints are evaluated for x and y and z

2 Likes

1 / (X * X) >= 1 / (X * Y)

1 / (X * X) >= 1 / (Y * Z)

1 / (X * X) >= 1 / (X * Z)

Let’s sum it
3 / (X * X) >= 1 / (X * Y) + 1 / (X * Z) + 1 / (Y * Z)

1 / (X * X * X / (3 * x)) >= 1 / (X * Y * Z / (X + Y + Z)) ->

X * X * X / (3 * X) <= X * Y * Z / (X + Y + Z)

1 Like

Thank you for your response

//