CHEFRAIL - Editorial

editorial
, , , , , ,
39

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

40

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
41

Has anyone done this using unordered_map ??

42

It will be less, but the time complexity might still be O(NlogN).

43

Try

Test case 
1
1 1
1
0

Your solution gives RTE.

44

Hey thanks bud!
Got it solved.

45

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
46

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?

47

Tmw orz

48

Thanks a lot, Man!
I asked few of my friends but they couldn’t figure it out!

1 Like
49

@anon72460392 @imrajatmehta

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).

50

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
51

If you switch the positive/negative then it should be fine.

52

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

53

It has been posted already

54

@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

55

@tmwilliamlin I have found it. No need to share now.

56

I am unable to understand explanation 2… Can you please explain it in some easy way so that beginners will understand??? Thanks in advance :slight_smile:

57

If I find all factors of yk and check for xi and xj pair, will that solution work??

58

I have tried a lot to make sure that beginners can understand. If you say that you can’t understand explanation 2, I don’t really know how to help you. Please at least tell me which part of explanation 2 is confusing for you.