Can anyone help me in understanding the significance of this line?
Without this line only 40/100 points are shown, rest WA.
Okay I’ve seen many of the solutions and I believe that mine is the fastest there is. Do check my solution if you have time. It ran in 0.16 sec for the biggest test case. I used hashing.
My code:
https://www.codechef.com/viewsolution/29714666
@tmwilliamlin can you please tell why it will work in O(Nsqrt(N)) i guess it should run in O(max.N)(where max is the max in y or x axis) because we are finding prime factors for Y^2 so sqrt(Y^2) will be Y therefore cmplexity will be O(max.N). please correct if i am wrong .
I was trying to Brute Force. I am getting WA on some test cases. ( Ignore TLE on last 4 test cases.)
I want to know where’s the mistake. What am I missing?
https://www.codechef.com/viewsolution/29701079
The error is at line number 27.
if(y[i]>0) ++y_pos;
It should be else if otherwise it would count zero in y_neg also.
1 Like
Has anyone done this using unordered_map ??
It will be less, but the time complexity might still be O(NlogN).
Try
Test case
1
1 1
1
0
Your solution gives RTE.
Hey thanks bud!
Got it solved.
I have a pretty quick solution in Python (link) now; someone might like to try it in C++ and see how it ranks.
This exploits the fact that if x_1 and -x_2 are the points on the x-axis bracketing the hypotenuse, they must have the same odd-exponent prime factors. This is because y_h = r . x_1 and x_2 = r . y_h, giving x_2 = r^2. x_1 and all changes to prime exponents are even.
So I split each number into x_a = q_a.s_a^2, where s_a is the biggest value possible and q_a is thus square-free, with a sieve of greatest square factors. I store these as pairs (q_i,s_i) for positive and negative x and sort by q. I then only compare x_1, x_2 for a possible y_h (or two, +/-) when they have matching q values, and the value of candidate y_h is directly given by y_h = q.s_1.s_2, looked up in a frequency array as above.
1 Like
is it necessary to check for f in negative x? Can we check for f in positive x and (yk^2)/f in negative x?
Tmw orz
Thanks a lot, Man!
I asked few of my friends but they couldn’t figure it out!
1 Like
O(N) is the time complexity for a single Y. If you add this up for all Y, you find that this algorithm runs in O(N^2). In the editorial, I prove that it also runs in O(NsqrtN).
This is because of an optimization I made in the dfs function.
if(i>=pf.size()||x*pf[i][0]>mxN)
The second condition x*pf[i][0]>mxN, says that if multiplying by pf[i] is impossible, then assuming that pf is sorted, multiplying by all other pf[j] (j>i) is impossible, so it stops recursing.
1 Like
If you switch the positive/negative then it should be fine.
Hi @tmwilliamlin i am waiting for your editorial of Expected Change. Please post that as it has new concept which i am not aware of inverse modulo etc
It has been posted already
@tmwilliamlin Usually editorial link is on problem page. I am not seeing link on problem page CodeChef: Practical coding for everyone . In case you have spare time, kindly share that link with me. Thanks