SDSQUARE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

SIMPLE

PREREQUISITES:

High school maths

PROBLEM:

Calculate the number of perfect squares between a and b which do not contain any digit other than 0, 1, 4 and 9. Constraint: 1<= a <= b <= 1010

QUICK EXPLANATION:

There are very few perfect squares satisfying the requirement, precalculating all such squares is simple.

EXPLANATION:

The constraint on the value of b is 1010. This implies, we need to test the squares of all integers less than or equal to 10^5. Following pseudo code captures the essence of precalculating all needed squares:

PrecomputeSquares
{
	idx = 0
	for i = 1 to 10^5
	{
		x = i*i
		if x does not contain any digit other than 0,1,4,9
			squares[++idx] = x
	}
}

Once we have calculated these squares; for each test case, count the number of squares falling in the range specified by the test case. We can use binary search to count these squares like this:

lower_bound(squares.begin(), squares.end(), b+1) - lower_bound(squares.begin(), squares.end(), a);

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Tester’s solution can be found here and here

2 Likes
2

I went on to generate the numbers containing only the digits 0,1,4 and 9, and simultaneously calculated whether or not it was a perfect square. Stored it if it was. Just answered the query based on a simple lookup.

http://www.codechef.com/viewsolution/2931829

1 Like
3

Actually, there are so few such numbers (just 120) that binary search is not even necessary. See http://www.codechef.com/viewsolution/2976638 (AC in 0.00 s)

1 Like
4

First i pre calculated all the answers with O(sqrt(n)) complexity and then stored all the numbers in an array.Then i made a linear search and found the count.:slight_smile:
The total size of the array was only 120 elements…:slight_smile:

5

Why do the authors of these problems use int64 instead of long? I thought it was same… Please correct me if I’m wrong.
Is it personal opinion??

EDIT:
Okay I feel pretty stupid for asking this question. I missed the typedef long long int64.
Sorry for that. I’m new to competitive programming.

6

भाई इतना माथा मारने की तो जरुरत ही नहीं थी |

2 Likes
7

why WA

  /*
   Ramesh Chandra 12 Sep 2015
    Adhoc
  */
  #include<bits/stdc++.h>
  using namespace std;

  #define read(x) scanf("%lld",&x)
  #define write(x) printf("%lld\n",x)

  int main(){


      long long int t,A,B,ans,i,check;
      read(t);
      // 1 00 00 00 00 00
      int preComputedSquares[100001];
      preComputedSquares[0]=1;

      for(int i=1;i<=100000;i++){

           check=i*i;
           bool flag=true;

           while(check && flag){

                int rem=check%10;

                if(rem==0 || rem==1 || rem==4 || rem==9);
                else flag=false;
                check/=10;
            }
            preComputedSquares[i]=preComputedSquares[i-1]+flag;
        }

        while(t--){

            scanf("%lld%lld",&A,&B);
             long long int L=sqrt(A-1),R=sqrt(B);
             ans=preComputedSquares[R]-preComputedSquares[L];
              write(ans);
         }
        return 0;
   }