You are not logged in. Please login at www.codechef.com to post your questions!

×

CHNGFUNC - Editorial

PROBLEM LINK

Practice
Contest

CONTEST PANEL

Author: Prateek Gupta
Tester: Praveen Dhinwa
Editorialist: Prateek Gupta

DIFFICULTY

Easy-Medium

PRE-REQUISITES

Math, Number Theory

PROBLEM

Find the number of integral pairs $(x,\ y)$ such that ($x^{2}\ +\ y$) is a perfect square where $x$ varies from $[1,\ A]$ and $y$ varies from $[1,\ B]$.

EXPLANATION

Let us iterate over both the approaches for smaller and bigger constraints.

Approach for A, B $≤$ 10^3

Here, we can easily do a brute force to check for each pair $(x, y)$ such that $x\ ≤\ A$ and $y\ ≤\ B$ and see if that pair fits into the equation. Let us see the pseudo code for this brute approach.

ans = 0

for x = 1 to A
    for y = 1 to B
       if ( perfect_square(x*x + y) ) ans = ans + 1

print(ans)

Overall complexity for this solution will be O(A*B) which is at-most $10^{6}$ operations in worst case scenario. But, this solution is too slow for the bigger constraints where we will need to think little differently.

Approach for A, B $≤$ 10^6

Let $F(x, y) = k$ where $k$ is any integer.

$$\implies x^{2} + y = k$$

Now, according to the question, $k$ should be a perfect square.

$$\implies k = p^{2}$$ $$\implies x^{2} + y = p^{2}$$

Converting the above equation into more simpler form, it can be re-written as $$y = p^{2} - x^{2}$$ $$OR$$ $$y = (p + x)(p - x)$$
Hence, $y$ can be written as a product of two integers i.e $(p + x)$ and $(p - x)$. It is now easier to formulate the solution based on this.

Since, $y$ $\in$ $[1, B]$, for each such y, we can find it's divisors {$m_{i}, y/m_{i}$} and try to match it with $(p + x)$ and $(p - x)$. More formally, $$p + x = m_{i}$$ $$p - x = y/m_{i}$$

The above two equations can be solved to get the value of $p$ and $x$. Both $p$ and $x$ obtained should be integral values and $x$ should $\in$ range $[1, A]$. Since, you will need to iterate over all divisors of each $y$ from $1$ to $B$, $O(B*sqrt(B))$ will turn out to be a little slow in the given time limit. The best way out here is to precompute the divisors using Sieve of Eratosthenes.

Let us now have a look at the pseudo code.

precompute(B)
{
     for i = 1 to B
         j = i
         while j <= B
            divisors[j].push_back(i)
            j = j + i

}

However, this is still a little slow to get fit within the time limit. The above algorithm takes $O(B*log(logB))$ time for pre-computation.The sieve implementation to store the divisors for each number can be optimized further to achieve best possible results. We do not really need to iterate uptill $B$ to precompute the divisors upto $B$. Infact, iterating till $sqrt(B)$ is sufficient. Why? You might think that we can miss divisors $>$ $sqrt(B)$ for some numbers. But, you will never miss those since you will always have a divisor $≤$ $sqrt(B)$ from which you can always find it's counterpart by dividing the divisor from the number itself.

Now, let us have a look at the pseudo code to make things clear.

precompute(B)
{
         for i = 1 to sqrt(B)
             j = i
             while j <= B
                 divisors[j].push_back(i)
                 if ( j/i != i && j/i > sqrtB ) divisors[j].push_back(j/i)
                 j = j + i

}

This allows us to achieve the complexity of $O(sqrtB*log(logB))$. Now, you can put the value of $m_{i}$, once as $divisor[y][i]$ and $y/divisor[y][i]$ next, in the above equation to find if there exist possible valid values of $p$ and $x$. You go on doing this for each $divisor[y][i]$ and for each $y$ from $1$ to $B$.

For more and precise details on the implementation, please refer to the setter's or tester's solution

SOLUTIONS

Author's solution can be found here.
Tester's solution can be found here.

asked 10 Jul '17, 21:11

prateekg603's gravatar image

5★prateekg603
20421123
accept rate: 0%

edited 24 Jul '17, 00:33

admin's gravatar image

0★admin ♦♦
19.5k348496536


Actually there is also a O(A) solution: for each $a$ between 1 and A, you find how many integers say $c_a$ between $\sqrt{a^2+1} $and $ \sqrt{a^2+B}$. The answer is $\sum_{a=1}^{A}c_a$.

link

answered 24 Jul '17, 00:39

phben's gravatar image

6★phben
1493
accept rate: 9%

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

(24 Jul '17, 15:48) dpraveen ♦♦4★

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

(24 Jul '17, 16:00) vijju123 ♦5★

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

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 - https://www.codechef.com/viewsolution/14658471

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

link

answered 24 Jul '17, 15:08

rohan_bose95's gravatar image

5★rohan_bose95
60215
accept rate: 8%

can you tell me the complexity of your solution?

(27 Jul '17, 21:02) akki284★

Nice question. Took a while to figure it out. But then it became one of the best submissions. I did it as follows with much less code but very efficient.

#include <stdio.h>
#define gc getchar_unlocked
 
int rin() { char c = gc(); while(c<'0' || c>'9') c = gc(); int ret = 0; while(c>='0' && c<='9') { ret = 10 * ret + c - 48; c = gc(); } return ret; }
int main() {
    int A = rin(), B = rin(),x,y, ans = 0,i, a, flag = 0;

    for(a = 1;;a++){
        flag = 0;
        for(x =1;x<=A;x++){
            y = 2*a*x + a*a;
            if(y<=B) ans++, flag = 1;
            else {
                break;
            }
        }
        if(!flag) break;
    }
    printf("%d\n", ans);
 
    return 0;
}
link

answered 24 Jul '17, 00:32

sun_d's gravatar image

3★sun_d
1275
accept rate: 13%

@phben exactly!!

The editorial's solution seems a bit complicated. There is a beautiful O(A) solution possible if we use concepts of A.P. and quadritic equation!!

My code for reference-

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

Image of derivation-

alt text

link

answered 24 Jul '17, 00:41

vijju123's gravatar image

5★vijju123 ♦
14.5k11855
accept rate: 18%

edited 24 Jul '17, 00:52

When you notice you got WA just because of int instead of long long ;_;

link

answered 24 Jul '17, 00:48

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

edited 24 Jul '17, 00:49

Many of the solutions whose time complexity is O(a*b) have been accepted.They have been given partial points. All the solutions to this questions should be rejudged.

link

answered 24 Jul '17, 12:15

swap_49's gravatar image

1★swap_49
111
accept rate: 0%

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

link

answered 24 Jul '17, 17:27

rohan_bose95's gravatar image

5★rohan_bose95
60215
accept rate: 8%

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

link

answered 25 Jul '17, 11:34

sidd845's gravatar image

3★sidd845
254
accept rate: 0%

Can anybody please explain that how the time complexity of last algorithm given in the editorial is $\sqrt{B}$lg(lg(B))?

I came up with the following analysis for time complexity: $\sum_{i=1}^{\sqrt{B}}\frac{B}{i} = B$log($\sqrt{B}$)

Can somebody please explain?

link

answered 24 Jul '17, 11:21

shubamg's gravatar image

5★shubamg
11
accept rate: 0%

edited 24 Jul '17, 11:22

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

(25 Jul '17, 20:20) phben6★

Can anybody point out what is wrong with my approach??

Since we have to make $x^2+y$ as a perfect square, so, we can write $y=(n^2-1)x^2$ where $n>=2$. We try to find out that for a particular value of $x^2$, how many $n^2-1$ terms are possible or can say how many $n$ are possible. Since maximum value of $y$ is $B$, so, $n=\sqrt{B/{x^2}+1}-1$. ($B/x^2$ is real number division not integer division) Here $n$ has $-1$ term because $n$ starts from $2$ not from $1$.So, for each value of $x^2$ we try to find no. of values of $y$.
Here is my code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>

#define pb push_back
using namespace std;

int main() {
ios_base::sync_with_stdio(0);
    long long a,b,i,ans=0;
    cin>>a>>b;
    for(i=1;i<=a;i++)
        ans+=(long long)sqrt(((double)b/(i*i))+1)-1;
    cout<<ans<<"\n";
        return 0;
        }
link

answered 24 Jul '17, 13:20

chan55555's gravatar image

2★chan55555
364
accept rate: 6%

edited 24 Jul '17, 16:27

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= (nn-1)x [where n is integer] but it forms a square.

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

(24 Jul '17, 16:24) vijju123 ♦5★

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

(24 Jul '17, 16:24) chan555552★

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

(24 Jul '17, 17:02) chan555552★

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

Here is link to the solution : https://www.codechef.com/viewsolution/14654083

link

answered 24 Jul '17, 23:43

chunky_2808's gravatar image

3★chunky_2808
1538
accept rate: 4%

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

link

answered 25 Jul '17, 13:24

debanjandhar12's gravatar image

4★debanjandhar12
32
accept rate: 0%

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);      
}
}
link

answered 25 Jul '17, 20:02

jaydeepbm00's gravatar image

2★jaydeepbm00
1
accept rate: 0%

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

link

answered 26 Jul '17, 22:32

jjthomson's gravatar image

3★jjthomson
111
accept rate: 0%

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

link

answered 26 Jul '17, 22:32

jjthomson's gravatar image

3★jjthomson
111
accept rate: 0%

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

link

answered 27 Jul '17, 21:44

shadow10's gravatar image

3★shadow10
112
accept rate: 0%

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??????

link

answered 29 Jul '17, 04:14

supriyanta's gravatar image

1★supriyanta
11
accept rate: 0%

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 ??????

link
This answer is marked "community wiki".

answered 29 Jul '17, 04:16

supriyanta's gravatar image

1★supriyanta
11
accept rate: 0%

i think this one is easy and simple to understand my solution which i tried after contest Time complexity: O(A) https://www.codechef.com/viewsolution/14762782

link

answered 02 Aug '17, 23:50

indra_123's gravatar image

4★indra_123
1
accept rate: 0%

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 : https://www.codechef.com/viewsolution/17996226

link

answered 31 Mar, 16:50

devarshi09's gravatar image

5★devarshi09
303
accept rate: 0%

edited 31 Mar, 16:51

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,047
×1,572
×1,116
×598
×56
×6

question asked: 10 Jul '17, 21:11

question was seen: 2,403 times

last updated: 31 Mar, 16:51