Need Help in solving problem

help
, , , ,
1

Refer to this problem
http://www.codechef.com/problems/SDSQUARE
i have seen the code of some good coder then initialize the most probable ans. in array and then retrieve it…
my question is that is they find all possible solution manuallly and then store in array or something else

long long ar[]={1LL, 4LL,9LL,49LL,100LL,144LL,400LL,441LL,900LL,1444LL,4900LL,9409LL,10000LL,10404LL,11449LL,14400LL,19044LL,40000LL,40401LL,44100LL,44944LL,90000LL,144400LL,419904LL,490000LL,491401LL,904401LL,940900LL,994009LL,1000000LL,1004004LL,1014049LL,1040400LL,1100401LL,1144900LL,1440000LL,1904400LL,1940449LL,4000000LL,4004001LL,4040100LL,4410000LL,4494400LL,9000000LL,9909904LL,9941409LL,11909401LL,14010049LL,14040009LL,14440000LL,19909444LL,40411449LL,41990400LL,49000000LL,49014001LL,49140100LL,49999041LL,90440100LL,94090000LL,94109401LL,99400900LL,99940009LL,100000000LL,100040004LL,100140049LL,100400400LL,101404900LL,101949409LL,104040000LL,104919049LL,110040100LL,111049444LL,114041041LL,114490000LL,144000000LL,190440000LL,194044900LL,400000000LL,400040001LL,400400100LL,404010000LL,404090404LL,409941009LL,414000409LL,414041104LL,441000000LL,449440000LL,490091044LL,900000000LL,990990400LL,991494144LL,994140900LL,1190940100LL,1401004900LL,1404000900LL,1409101444LL,1444000000LL,1449401041LL,1490114404LL,1990944400LL,4014109449LL,4019940409LL,4041144900LL,4199040000LL,4900000000LL,4900140001LL,4901400100LL,4914010000LL,4914991449LL,4941949401LL,4999904100LL,9044010000LL,9409000000LL,9409194001LL,9410940100LL,9900449001LL,9940090000LL,9994000900LL,9999400009LL,10000000000LL};
2

According to me manually it is not possible!!

3

Hmm, he/she must have written a brute-force algorithm, to generate all these values.

Now, since you have all the values generated, you can copy them over to the source code, to build the array. The actual solution submitted can then just proceed with lookups in this array (which turns out quite efficient, compared to trying to find actual answer every time.)

So, to answer your original question, whether they found it manually. They wrote a program to generate these values. I don’t know if that counts as manual or not. :slight_smile:

4

Hi ,
See for this question you need some kind of precomputation.(ie you need to precompute the value outside the loop of test cases). As number of such numbers are low ie 120 so users have computed the value and stored it in the array than it becomes O(1) for each test case . While in the contest I passed O(log 120) per test case . Looping over all numbers from a to b will give you tle.

You can find my code.here

5

You can calculate this values very easily.

As you may have deduced you only need to use these 4 digits(0,1,4,9) to make a number.

Now for length of n digits the count of such numbers can be : 3 x (4^(n-1)).[as the first number can only be 1,4,9 and rest digits can take any of the four values]

As the number of digits is 10 according to constraints in the question,

Total such number can be 4 + sum(3 x 4^(n-1)) = 4^n = 2^20 which is acceptable.

Precompute these number and check whether they are square or not. Keep the perfect square in an array or vector.

Now for each given a,b pair just binary search the array/vector and get the number of elements in the range and you will have your answer.

6

How the values generated is written in source code file i.e in array ??

7

jhori21 my question is that they find the no. using brute force they how they write all these no. is original source code i.e. in array initialization bz manually its very time consuming!!

8

I got ur trick u done in very easy way

int lower=upper_bound(check,check+120,a)-check;

// cout<<lower<<" “<<check[lower]<<endl;
int upper=upper_bound(check,check+120,b)-check;
// cout<<upper<<” "<<check[upper]<<endl;
cout<<upper-lower+1<<endl;

but can’t understand this what’s going on in this

9

Why -check is written ??

10

Hi Chaman it’s good that you have got the solution.

Now answer to your first query:

  1. Writing the numbers in array is very easy. You have to just write a brute force code and print the content in file(may by using fprintf). Now in your code you have to just copy paste the content and paste that in a array .Volia it’s done . :slight_smile: (It’s that easy, you must try it sometime this technique helps).
11
  1. Now the second part why I wrote - check. Actually if you read lower_bound it give iterator now I need just the index so subtracted the location of the array.
    In simple words you are subtracting two memory location to find index.

Hope that helps. :slight_smile:

12

Also, instead of storing the squares, you can store the values who’s square lies in the range [a,b]. I did this, because squares of some values were large and generating through brute force and keeping track was getting little clumpsy… So i Did this manner: http://www.codechef.com/viewsolution/2952319

13

Also, like in such questions when we know there are only 120 numbers, i.e. count which is small to read, compute(think of both space and time complexity here) itself gives the hint that the question needs precomputation. Practise and then you’ll yourself flow with the flow :stuck_out_tongue:

14

Oh, either you can copy-paste from the terminal into your source code, or, you just pipe the output to a file, and then write your program around the data in the file.

15

Thanks a lot :slight_smile:

16

Thanks a lot :slight_smile: