ADTRI - Editorial

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

4 Likes

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?

@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

@dragonemperor refer to this Fermat's theorem on sums of two squares - Wikipedia
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

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

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

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

my sieve solution CodeChef: Practical coding for everyone

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:

@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 CodeChef: Practical coding for everyone

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.

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

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.

I observed the pythagorean triplets as 4k+1 (pattern) during the contest and solved the problem. CodeChef: Practical coding for everyone
But what is the logic behind 4k+1 . Any mathematical proof?

@avidcoder Refer to these two links 1. Pythagorean triple - Wikipedia
2. Fermat's theorem on sums of two squares - Wikipedia

@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.

Proof of this Fermat’s theorem can be found here

hell, i did the same and get tle in last subtask. using java fast I/O. from fast I/O i mean Buffered reader and writer something like that. :frowning:
very tight time limit :frowning:

also i have O(sqrt(n)) complexity for prime factorization and checking that (n-1) % 4 == 0 or not…

time limit should be more flexible… I think :frowning:

i did exactly same but still getting TLE in last subtask . i am using python and tried everything to reduce time .please help anyone.here is my solution CodeChef: Practical coding for everyone

@avidcoder the proof deals with concepts of congruences, residues and quadratic fields. I have read this proof in the book ‘an introduction to number theory’ by g.h hardy and the proof is very easy to understand if you know about congruences and residues.