Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing all possible values of p^2+q^2 good? Because they are not too many, and the biggest p^2+q^2 is when p=250 and q=250, in which p^2+q^2 = 125,000. So let's produce all of them.
Now take a look at N, If we brute force over the length of the progression, and start from each possible starting value, and check whether this start with this length can end up an arithmetic progression with N values? There is a little thing we have to be concerned about, after picking starting value and length of the progression, how do we check whether this would end up in a progression with N values?
Suppose the starting value is 13 and the length is 5, we want to know whether 18, 23, 28, 33 are available or not? To do so, when producing all possible p^2+q^2 just mark them in an array, if mark[x] is set to true, then we know that there exist p and q such that p^2+q^2 = x. In this way you can pass the test in the given time limit.
Now take a look at N, If we brute force over the length of the progression, and start from each possible starting value, and check whether this start with this length can end up an arithmetic progression with N values? There is a little thing we have to be concerned about, after picking starting value and length of the progression, how do we check whether this would end up in a progression with N values?
Suppose the starting value is 13 and the length is 5, we want to know whether 18, 23, 28, 33 are available or not? To do so, when producing all possible p^2+q^2 just mark them in an array, if mark[x] is set to true, then we know that there exist p and q such that p^2+q^2 = x. In this way you can pass the test in the given time limit.
I used the method described above with ... python, and did not passed all(6 passed)
ReplyDeleteYes I did to but I used java and timed out on the 7th test case
ReplyDelete