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.
Some people mention speedup from processing rad(a) = 1 separately, but I didn't use that.
For the query part: KD-Tree (2D, augmented with sums) was my first shot - fast, but way to slow for 100k test cases. Sorting the queries and use of 1D Fenwick tree let to following timings in Python3: 2.5s to generate 83519 triples, 3.6s for last test (for Python neewbies like me: complex code works faster inside function than in global scope)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #127: abc-hits
You are viewing a single comment's thread. Return to all comments →
Link to the forum: https://projecteuler.net/thread=127 (you need to solve oryginal problem first)
I've used this hint (not a big spoiler, you need to understand the problem to understand the hint):
rad(abc) = rad(a)*rad(b)*rad(c) < c**1.5 < 100000**1.5
Thus rad(a) < rad(b) < sqrt(100000**1.5) and rad(a) < 100000**1.5 / rad(b)^2.
c is either a+b or abs(a-b)
Some people mention speedup from processing rad(a) = 1 separately, but I didn't use that.
For the query part: KD-Tree (2D, augmented with sums) was my first shot - fast, but way to slow for 100k test cases. Sorting the queries and use of 1D Fenwick tree let to following timings in Python3: 2.5s to generate 83519 triples, 3.6s for last test (for Python neewbies like me: complex code works faster inside function than in global scope)