Below is the problem statement for '

Problem

-------

Little John likes palindromes, and thinks them to be fair (which is a fancy word for nice). A palindrome is just an integer that reads the same backwards and forwards - so 6, 11 and 121 are all palindromes, while 10, 12, 223 and 2244 are not (even though 010=10, we don't consider leading zeroes when determining whether a number is a palindrome).

He recently became interested in squares as well, and formed the definition of a fair and square number - it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are fair and square (being palindromes and squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are not fair and square: 16 is not a palindrome, 22 is not a square, and while 676 is a palindrome and a square number, it is the square of 26, which is not a palindrome.

Now he wants to search for bigger fair and square numbers. Your task is, given an interval Little John is searching through, to tell him how many fair and square numbers are there in the interval, so he knows when he has found them all.

Solving this problem

--------------------

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has 1 Small input and 2 Large inputs. Once you have solved the Small input, you will be able to download any of the two Large inputs. As usual, you will be able to retry the Small input (with a time penalty), while you will get only one chance at each of the Large inputs.

Input

-----

The first line of the input gives the number of test cases, T. T lines follow. Each line contains two integers, A and B - the endpoints of the interval Little John is looking at.

Output

------

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of fair and square numbers greater than or equal to A and smaller than or equal to B.

Limits

------

Small dataset

-------------

1 ≤ T ≤ 100.

1 ≤ A ≤ B ≤ 1000.

First large dataset

-------------------

1 ≤ T ≤ 10000.

1 ≤ A ≤ B ≤ 1014.

Second large dataset

--------------------

1 ≤ T ≤ 1000.

1 ≤ A ≤ B ≤ 10100.

Sample Input

------------

3

1 4

10 120

100 1000

Output

------

Case #1: 2

Case #2: 0

Case #3: 2

The above problem statement says that given 2 numbers (min and max), we have to find the number of 'Fair and Square' numbers in that range (min --> max). For a number to be "Fair And Square", it should be a perfect square, a palindrome and it's square root should also be a palindrome. For Example: 4 is a palindrome and a perfect square. It's Square-Root 2 is also a palindrome. So, 4 is a "Fair And Square" number.

My idea was to find the Minimum and Maximum 'Perfect Squares' in that range, find Square Roots for those numbers and loop between these 2 square-roots, to find the number of 'Fair and Square' numbers in the given range. When looping between these Square-roots, the square-root is first checked if it is a palindrome or not. If it is a palindrome, it's square is calculated and a check is done to find out, if it is a palindrome or not. If it is a palindrome, the square number is a 'Fair And Square' number.

For the 'Small Input Dataset' of the above problem statement, the logic described above works without any problems and finishes pretty fast. But for large datasets, better algorithms or infrastructure is needed, for the programs to finish within the timeline. So, I decided on using external libraries to handle BIG numbers and also a Off-Heap-Memory framework/library, which persists Java's Map datastructure to disk (which would also help me to avoid Java's OutOfMemory problems). For handling big/large numbers, I decided to use the JScience library, which has "LargeInteger" and convenient methods to find "Square Roots" or do other math. For the Off-Heap-Memory (Disk based storage), there were a couple of options like Berkeley DB, HSQLDB, MapDB, etc...I decided on using MapDB, after I checked it's performance stats and found that to be good enough. Also, it was easy to get started. I used a Maven based project. So, the POM.xml for this project is as below:

And the solution to the above problem statement is as below:

Note that the below solution works for only the 'Small Data Set' and 'Large Dataset - 1', within the given timeline. For 'Large Dataset - 2', you can solve it by creating the 'Fair And Square' cache first, then download the input and solve it. A better solution would be to use a better algorithm, as described in the 'Contest Analysis' section of the GCJ 2013 Qualification Round's Dashboard.

You can also find the source code at: GCJ 2013 - Fair And Square

- GCJ 2014 - 'Deceitful War'
- GCJ 2014 - 'Cookie Clicker Alpha' Problem
- GCJ 2014 - Magic Trick
- GCJ 2013 - Fair And Square
- GCJ 2013 - Tic-Tac-Toe-Tomek
- GCJ 2012 - Recycled Numbers
- GCJ 2012 - Dancing With Googlers
- GCJ 2012 - Speaking In Tongues
- GCJ 2011 - Magicka
- GCJ 2011 - Bot Trust
- GCJ 2010 - Fair Warning
- GCJ 2010 - Snapper Chain
- Odd Man Out - GCJ 2010 (Africa)
- Store Credit - GCJ 2010 (Africa)
- T9Spelling - GCJ 2010 (Africa)
- Reverse Words - GCJ 2010 (Africa)
- All Your Base - GCJ 2009
- Alien Language - GCJ 2009
- Google Code Jam 2008 - Minimum Scalar Product
- GCJ 2008 - Alien Numbers
- Playing With Googol
- Google Billboard Puzzle
- Euler's Number (e) to 10000 digits
- Spiral Walking

- GCJ 2014 - 'Deceitful War'
- GCJ 2014 - 'Cookie Clicker Alpha' Problem
- GCJ 2014 - Magic Trick
- GCJ 2013 - Fair And Square
- GCJ 2013 - Tic-Tac-Toe-Tomek
- GCJ 2012 - Recycled Numbers
- GCJ 2012 - Dancing With Googlers
- GCJ 2012 - Speaking In Tongues
- GCJ 2011 - Magicka
- GCJ 2011 - Bot Trust
- GCJ 2010 - Fair Warning
- GCJ 2010 - Snapper Chain
- Odd Man Out - GCJ 2010 (Africa)
- Store Credit - GCJ 2010 (Africa)
- T9Spelling - GCJ 2010 (Africa)
- Reverse Words - GCJ 2010 (Africa)
- All Your Base - GCJ 2009
- Alien Language - GCJ 2009
- Google Code Jam 2008 - Minimum Scalar Product
- GCJ 2008 - Alien Numbers
- Playing With Googol
- Google Billboard Puzzle
- Euler's Number (e) to 10000 digits
- Spiral Walking

- Recursion Depth - Java
- RESTFul Web Service - Seam Component Injection
- Micro-benchmarking Java Code With Caliper
- JSF & Highcharts (Javascript Chart Library)
- Add 'Syntactic Sugar' With 'Fluent Interface'
- Priority Queue in Java
- Compile Java Files At Runtime
- Missing Number
- Guice - AOP (Aspect Oriented Programming)
- Creating Executable Jar File With Maven Shade Plugin
- Java - Looping Through A Range of BigInteger Values
- Create Your Own Dependency Injection Framework
- Google Guice - Example
- Guice Grapher - Example
- Using Richfaces 'Suggestion Box' As Combo Box
- Hashcode Of A String In Java
- Richfaces - Modal Panel As A Wizard
- Jasper Reports - Thermometer Report
- Jasper Reports - Gantt Chart
- Jasper Reports - Example
- Seam - Load i18n Messages From Database
- Autoboxing In Java & Bug Patterns
- Dont Smack The Stack (Deal With Stack Overflow Exceptions)

The views expressed on this blog are my personal views and do not reflect the views of
my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.