Sort 11 Discussions, By:
Please Login in order to post a comment
Solved this problem in F# using Euclid's formula to generate primitive Pythagorean triplets, for each increasing the triplet count of the appropriate lenghts (ie, multiples of the sum of the triplet values). With some simple DP, one then has all answers precalculated.
Note that this last part is useful in this particular problem, since the number of tests can be high (10^5).
Lazy solution to dumb test cases: precalculate all the counts up to N=5e6 then return the corresponding value for each test case. You really should put more effort (or at least some effort) into reasonable/decent/interesting requirements.
Please give any hints regarding timeouts@tc4-6! A local profiling run on my submission (java.lang, T=10000, N in 4990000..5000000, no input scanning) executes in 2.767 seconds...Tc0-3 pass either (~20 ms).
Scanner -> BufferedReader, List<Integer> -> int, aggergated generation (of the triplets) and evaluation (of results) did it by the end of the day: Congratz 2me, thx anyway 2you
Scanner -> BufferedReader
List<Integer> -> int
you can find my java solution here
Was stuck with the mindset to calculate the primitive triplets of a given perimeter (loop based on the perimeter) one after another, and it was too slow.
Then I swiched to looping on odd and even m and its corresponding n, and even with occasional gcd() does not make it unacceptably slow. The rest is just implementation of precalculation and dynamic programming. Takes more than 2s in Python, though.