CHNGFUNC - Editorial

editorial
, , , , ,
9

Here is my solution (and its quite simple to understand :slight_smile: ) -

As x^2 + y = p^ 2 thus y = p^2 - x^2 ,for x to be in [1,A] and y in [1,B]. (where p^2 is a perfect square)

As y can’t be zero or negative then, p should be greater than x+1. Thus p can take up any integer from x+1 to infinity such that p^2 - x^2 <= B.

Thus we need to find for each x in [1,A] the number of integral points of p which are greater than or equal to x+1 and satisfies the equation p^2 - x^2 <= B.

Here is my code - CodeChef: Practical coding for everyone

If you like my solution , feel free to give a thumbs up, I need some Karmas . :slight_smile:

9 Likes
10

@chan55555 Here is how i would like to explain the bug in your solution.

As you have assumed y=(n^2 - 1)x^2 … this implies y = (n * x)^2 - (x)^2

i.e x^2 + y = (n * x)^2

Thus according to you the perfect squares can be only those squares whose square roots are multiples of x while there was no such restriction in the problem statement itself. This assumption will leave a lot possible perfect squares whose square roots are not multiples of x. An example would explain this more clearly . if A=4 and B=6 then there would be a case of (x,y) as (2,5) i.e 2^2 + 5 = 9 ., as you can see that the 9 isn’t a multiple of 2 , thus your program wont take 9 into consideration and hence would leave out a possible (x,y) pair , thus the ans produced by your code will be less than (or in some special cases equal to ) the correct answer . The correct answer for A=10000 B=100000 is 291528 but ur code produces 1591 … thus leaving out a lot of possible cases.

I Hope this makes it clear . You can refer to my solution in the comments above.

If you like my comment , feel free to give a thumbs up , I need some Karmas :slight_smile: .

1 Like
11

It can also be done by precomputing all perfect squares and then doing upper bound for each element .

Here is link to the solution : CodeChef: Practical coding for everyone

12

i used binary search for this!
x^2 + y = a^2
=> y = a^2 - x^2;

now , i used binary search to find the upper bound of a (satisfying the constraint on y) and do the same for all x .

my solution got accepted but if anyone thinks any bug in approach then please let me know :slight_smile:

1 Like
13

Wait Wait! The approach actually worked? In my case it didn’t seem to do so. (Yes, I use Java)

The optimal solution is O(A * log B)

https://www.codechef.com/viewsolution/14651473

The other O(a*b) feels kinda unfair tho

14

The editorial solution didnt work fr me… I am gettng TLE…

import java.io.*;   
import java.util.*;
class PerfectFunction {
public static int countSquares(int a, int b){
	Map<Integer,List<Integer>> divisors = precomputeDivisors(b);		
	int count = 0;
	for(int y = 1; y <= b; y++){
		List<Integer> list = divisors.get(y);
		for(int i : list){
			int m = i;
			int n = y/m;
			if(m < n)
				continue;
			float p = (m+n)/2f;
			float x = (m-n)/2f;
			if(((p - (int)p) == 0) && ((n - (int)n) == 0) &&
                                      (x >=1) && (x <= a)){
				count++;		
			}
		}
	}
	return count;
}
public static Map<Integer,List<Integer>> precomputeDivisors(int b){
	Map<Integer,List<Integer>> divisors = new HashMap<>(b+1);
	for(int i = 1; i*i <= b; i++ ){
		for(int j = i; j <= b; j+=i){
			List<Integer> list = divisors.get(j);
			if(list == null){
				list = new ArrayList<>();
				divisors.put(j, list);
			}
			list.add(i);
			if(j/i != i && j/i > Math.sqrt(b))
				list.add(j/i);
		}			
	}
	return divisors;
}
public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int a = scan.nextInt();
	int b = scan.nextInt();
	int count=countSquares(a,b);		
	System.out.println(count);		
}
}
15

i submitted my solution during contest, it throws TLE at that time.
But when i copy pasted my code(exactly same) in practice section it gave me AC.can anyone explain why this happened?
https://www.codechef.com/viewsolution/14675999
https://www.codechef.com/viewsolution/14656596

16

i submitted my solution during contest, it throws TLE at that time.
But when i copy pasted my code(exactly same) in practice section it gave me AC.can anyone explain why this happened?
https://www.codechef.com/viewsolution/14675999
https://www.codechef.com/viewsolution/14656596

17

My solution is a bit different.At first, I pre-computed all squares of numbers up to 10000002.Then for each square number let say x less than A*A,I searched how many square numbers are there in the region x+B.Here is my solution link.link text

18

In #Author’s solution why do we check for (k_plus_x + k_minus_x)%2==0 && (k_plus_x - k_minus_x)%2==0???

19

CHNGFUNC In #Author’s solution why do we check for (k_plus_x + k_minus_x)%2==0 && (k_plus_x - k_minus_x)%2==0 ???

20

i think this one is easy and simple to understand my solution which i tried after contest Time complexity: O(A) CodeChef: Practical coding for everyone

21

I used two pointer technique. First I stored all the squares till the maximum possible perfect square one can get in a vector. Then I used the difference of values of two pointer to check the condition |x^2-y^2|<=b.
My solution : CodeChef: Practical coding for everyone

22

Really neat solution!! My (tester’s) solution is based on the fact that the bound on answer won’t be large.

23

Yup, this approach is really neat. I think its like, less than 10 lines of code (ignoring headers and stuff)

24 
write y=(n2−1)x2y=(n2−1)x2 where n>=2n>=2.

Does this not imply that y HAS to be a integral multiple of x? And its not the case, say for x=2 and y=5. y cannot be expressed as y= (n*n-1)*x [where n is integer] but it forms a square.

It looks like your approach misses out some cases. What do you think?

25

Anyone, please help!! I couldn’t find what’s wrong with my solution.

26

@vijju123 Yeah!! I got it. My solution was only considering the integral value of n but the fractional value of n does also contribute to the answer.
for example your case of x=2 and y=5, n=1.5 does also contribute to the answer.
Thank you for the test case!!

27

\sum_{i=1}^{n}\frac{1}{i}=O(log(n))

28

can you tell me the complexity of your solution?