ADTRI - Editorial

editorial
, , , ,
1

Problem Link

Practice

Contest

Difficulty

Easy

Pre-requisites

Basic math

Problem

Given an equilateral triangle having length of each side as an integer N. Is it possible to alter one of its’ sides such that the height drawn to the altered side has integral length and the altered side has an even integer length?

Explanation

Let’s recall the formula for calculating of length of the height of an isosceles triangle. If the length of the height is h, the length of the altered side is b, then h = sqrt(N2-b2/4). Then, h2=N2-b2/4. Let’s denote b/2 by c and, since b should be even, c should be integer. Then, we get h2=N2-c2. This is the same as N2=h2+c2. According to the statement, h and c should be integer.

Now, the problem is: given an integer N. Find out, whether it is possible to represent N2 as a sum of two integer numbers’ squares or not.

How to get 10 points

Let’s iterate through possible values of h, there are O(N) possible values of h. Then, let’s check, if N2-h2 is a square of an integer number.

The total complexity of such a solution is O(TN) and it is capable only of solving the first subtask.

How to get 100 points

It is a well known fact that N can be represented as a sum of two perfect squares if and only if N is dividible by a prime of the form (4k+1), where k is an integer number.

So, let’s find all the prime numbers not exceeding the maximal value of N. Then, let’s pick all the prime numbers that give 1 modulo 4 and for each of them, mark all the numbers that are divisible by them and doesn’t exceed the maximal possible value of N (say, MAX_N).

It takes MAX_N/P operations to mark all the integers that are divisible by P. Let’s estimate the total number of the operations that we will make.

Since not every number is a prime of the form (4k+1), we can safely assume that the total number of operations won’t exceed \sum_{P=1}^N \frac{N}{P} that won’t exceed O(T+MAX_N log MAX_N).

This solution gets 100 points.

Setter’s Solution

Can be found here

Tester’s Solution

Can be found here

3 Likes
2

Can you please explain how to get this formula : prime factor must be of form 4k+1 ? I came up with it using my own logic but the logic was wrong. I somehow, by mistake, got the formula and solved it. I need to know how I could have derived it. Can you give some pointers or links?

3

Thank you for the link. But I know this already. Based on this I derived my formula. But for above question, for given side, say n, we need to check if n^2 is of the form a^2+b^2. n^2 cannot be a prime. Where does this prime factor thing come from?

4

@dragonemperor
It’s euclid’s theorem. We know for any m and n(there are some conditions),the 3rd arm of pythagorean triples will be (m^2+n^2). If you look closely, N always will be the 3rd arm of pythagorean triples of a right angle.

1 Like
5

I got it. Thank you.

6

@dragonemperor refer to this https://en.wikipedia.org/wiki/Fermat’s_theorem_on_sums_of_two_squares
It comes from the same theorem! When we check if a number can be written as sum of two squares, we check if it has a prime factor of the form 4k+1. So it doesnt matter whether it is N^2 or N as N^2 will have a factor N which maybe prime of form 4k+1.

1 Like
7

Another Approach is to find all primitive pythagoereian triplets using euclid’s method and then prime factorizing ‘N’ and seeing if any prime factor is a part of a primitive pythagoereian triplet.

https://www.codechef.com/viewsolution/8311061

1 Like
8

Just sieve it
https://www.codechef.com/viewsolution/8350431

9

Precomputation…
Since we know that the n (given length) will always be the hypotenuse.If we pre-compute all the pythagorian triplet till the maximum value of n then we can easily check whether there is a pythagorian triplet of length equal to n or not. Thus this can be done in O(1) time… to check whether pythagorian triplet exist for given ‘n’ or not…

https://www.codechef.com/viewsolution/8526052

1 Like
10

my sieve solution https://www.codechef.com/viewsolution/8398080

11

I tried to do that method,but got WA. Now I know why,I wasn’t marking multiples -- -- :stuck_out_tongue:

12

here is my solution. I have done the same thing as mentioned in the editorial above. However, am stuck at 40 points. Someone plz help. :slight_smile:

13

@agarwl96 some suggestions. use printf scanf instead of cin cout. also in second loop to avoid checking modulo 4 everytime, start iterating from 5 and every 4th element from there (i=5,i+=4). should reduce some time https://www.codechef.com/viewsolution/8532091

14

Using cin/cout with fast I/O gave TLE for the last sub-task : 40 points

However, using scanf/printf for the otherwise same code got accepted : 100 points

Not cool.

15

ohk! I got that. Got 100 points. Thank you @atulshanbhag :slight_smile:

16

haha your 100 points dont count now :stuck_out_tongue: anyway upvote instead of thanking. thanks

17

I also thought of the same solution, but could not implement because of a reason:
8 = 2^2 + 2^2, and 2 is the only prime factor of 8 which doesn’t satisfy 4K+1. Please help me in understanding the concept.

18

I observed the pythagorean triplets as 4k+1 (pattern) during the contest and solved the problem. https://www.codechef.com/viewsolution/8474430
But what is the logic behind 4k+1 . Any mathematical proof?

19

@avidcoder Refer to these two links 1. https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple
2. https://en.wikipedia.org/wiki/Fermat’s_theorem_on_sums_of_two_squares

20

@atulshanbhag No proof in any of those links. I think this condition dont have any proof. We should observe patterns and make assumptions. it is like mathematical induction.