Sort 3 Discussions, By:
Please Login in order to post a comment
R > 1 makes this difficult. I can handle n=10^5 when r=1, but when r=1.5 I can only handle n=10^4 before I run out of time. Can someone confirm them solved this without using hardcoded data sets?
I am also interested to know if this one requires hardcoded data sets? Or deep mathematical knowledge about abc-conjecture? (quality bounds obtained through computations...)
This seems to really require stronger thinking than the projecteuler version (which is good). Congrats ! ;)
No "deep" knowledge required, and no hardcoded data sets required. For L=10^5, r=1.5, there are about 90000 triples that satify the abc conditions. You should be able to compute these in < 1s (mine does it in about 100ms). The forum on project euler has some good ideas to help with that. The key to handling large number of test-cases is to avoid recomputing triples altogether, and to avoid having to search through a list of 90k-100k triples to find the ones that satify a given (r,L).
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)
Well, Haskell's built-in read :: String -> Double is quite slow, so I write my own version of reader. After many times of submission I found that the input format does not follow what it should be:
read :: String -> Double
The input r is written with at most 6 decimal digits behind the decimal point.
It confused me for a whole day, and later I just tried to read 8 decimal digits behind the decimal point and that was accepted.
Although the outputs from my code are correct, even then the there is a timeout message when the code is executed?
You only have a limited time to execute your code. That's part of the challenge. You could try to either improve the algorithmic complexity of your code or use different data structures with better access time
No more comments