We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Curious to know how it works to compute million pythagorean triplets within the time limit. I've been using Euclid's formula, but that m += 1, n += 2 is supposedly killing it. It takes almost 5 seconds to generate triplets up to (with most of the time spent on finding the valid primitive triplets), let alone .
Perhaps it is because of the upper bound you mentioned? I don't know where that 1.1*sqrt(M) comes from, the bound I used was a while-loop with condition m**2 - (m-1)**2 <= M. When I look closely, this condition is unnecessarily loose, as it does not take into account the fact that either a >= b or b >= a should be true, while and .
EDIT: I tried using this upper bound, and got WA for Test Cases #3 through #9.
EDIT 2: Tried with sqrt(3*M) and it works. Even sqrt(2*M) did not work, where it was missing some pairs like m=917, n=218. Maybe the difference is due to the way I handled the triples, as I append whenever a >= b_plus_c / 2 + b_plus_c % 2 or b_plus_c >= a / 2 + a % 2.
I'm quite sure that this condition would fail again for much larger input. The naming here is quite confusing, as b_plus_c >= a / 2 + a % 2 in fact means b >= a_plus_c / 2 + a_plus_c % 2, but I just handle them all in one place.
EDIT 3: By the way, I find it interesting that no one mentioned another key insight involved in solving this problem, that is to visualise the unfolding of the 3D box. At the beginning, I was trying to solve the equation and find the derivative of it to look for a minimum, thinking about how this problem is supposed to be 35% difficulty.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #86: Cuboid route
You are viewing a single comment's thread. Return to all comments →
Curious to know how it works to compute million pythagorean triplets within the time limit. I've been using Euclid's formula, but that
m += 1
,n += 2
is supposedly killing it. It takes almost 5 seconds to generate triplets up to (with most of the time spent on finding the valid primitive triplets), let alone .Perhaps it is because of the upper bound you mentioned? I don't know where that
1.1*sqrt(M)
comes from, the bound I used was a while-loop with conditionm**2 - (m-1)**2 <= M
. When I look closely, this condition is unnecessarily loose, as it does not take into account the fact that eithera >= b
orb >= a
should be true, while and .EDIT: I tried using this upper bound, and got WA for Test Cases #3 through #9.
EDIT 2: Tried with
sqrt(3*M)
and it works. Evensqrt(2*M)
did not work, where it was missing some pairs likem=917, n=218
. Maybe the difference is due to the way I handled the triples, as I append whenevera >= b_plus_c / 2 + b_plus_c % 2
orb_plus_c >= a / 2 + a % 2
.I'm quite sure that this condition would fail again for much larger input. The naming here is quite confusing, as
b_plus_c >= a / 2 + a % 2
in fact meansb >= a_plus_c / 2 + a_plus_c % 2
, but I just handle them all in one place.EDIT 3: By the way, I find it interesting that no one mentioned another key insight involved in solving this problem, that is to visualise the unfolding of the 3D box. At the beginning, I was trying to solve the equation and find the derivative of it to look for a minimum, thinking about how this problem is supposed to be 35% difficulty.