CHEFRAIL - Editorial

editorial
, , , , , ,
25

I used this Find all factors of a Natural Number - GeeksforGeeks
to generate divisors, it also takes O(NrootN)
My solution got TLE after 40 points, can someone suggest why?

26

Did you use fast io ?

27

Yes I did.
https://www.codechef.com/viewsolution/29664661

28

I think Quick Explanation 1 is enough to change 40 point solution to 100.
I was looping through all divisors.

29

Iā€™ll tell you why you got tleā€¦your algo runs basically in nroot(pow(max(arr),2)ā€¦you can see that magnitude of values in array are in range(10^5)ā€¦so, it is not nroot(n)ā€¦if the values would have been in range(10^2)ā€¦it wouldā€™ve not given any tle.

co = pow((*it).first,2);
for(int i=1 ; i<=sqrt(co) ; i++)
look at your code once again

since range of n and values in array are in same orderā€¦we can safely assume that your code is n^2

1 Like
30

so according to you if there are o(n/logn) prime numbers untill number n then it should be possible to find number of prime numbers untill n in time complexity of n/logn ?

31

When did I say that?

My point was given the prime factorization of a number, while trying to generate the divisors of the number using itā€™s factorization you will make a recursion tree with D leaves, if the number has D divisors.

This should take time proportional to D.

Overall for all of them time should be proportional to 10^7

32

For my method, I first divided each x and y array into two, one with the absolute value of the negative values, and the other with the positives. (I handled 0 separately as above).

I then evaluated the largest prime factor of every number, and stored it with the number. For this purpose the prime numbers include 1. I also prepared arrays of values in each of the 4 arrays (-X +X -Y +Y) which had each prime number as its largest factor.

I then worked along the y values. Note that each y-squared can only be divided by an x-value with the same largest prime factor as the y. For each y the steps are

  1. Evaluate y-squared.
  2. Loop through the corresponding array of -X which have the same largest prime factor.
  3. If this divides into Y-squared exactly, evaluate the other factor.
  4. Search through +X by binary search to see if the other factor is on the axis.
  5. Store solutions found, to prevent duplicate solutions in the next steps.
  6. Loop through the corresponding array of +X which have the same largest prime factor.
  7. If this is not already a solution, and divides into Y-squared exactly, evaluate the other factor.
  8. Search through -X by binary search to see if the other factor is on the axis.

I then repeated with X and Y swapped.

You can see my solution at CodeChef: Practical coding for everyone

An improvement which I though of afterwards is to check after steps 3 and 7 if the other factor also has the same largest prime factor, which it often will. If so, we need only to do the binary search at the next step on the corresponding array of values with the same largest prime factor, rather than on the entire array .

33

It can be implemented so that it runs in O(number of factors generated).

1 Like
34

Could anybody please check why my solution gives WA on one test case
codechef.com/viewsolution/29788897
Thanks in advance!

35

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

36

Can anyone help me in understanding the significance of this line?
Without this line only 40/100 points are shown, rest WA.

37

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

38

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

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.