Hackerearth "January Easy '17 contest" Simple Function

January 1, 2017

Plan to attend 8:00 - 11:00am hackerearth.com

January Easy '17 contest

Work on the algorithm:

January Clash '2017


- One of 6 algorithms: Simple Function

In contest performance, C# solution, pass test case 1, but timeout all other cases. (9:00am - 11:00am)

C# solution, passed 5 test cases, fail last one. (after the contest, 2+ hours)

Study code C++

Write C# code using the above solution. (Time spent: 4 + hours, completed at 6:37pm)

Code Review Link is here. Julia spent more than one hour on January 3, 2016 to add her calculation of cache size reduction from 2MB to 80KB based on the comment from Paparazzi


January 7, 2016
Continue to do some research on C# Dictionary comparison to self-defined hash function to do pre-processing.

Using Dictionary<string, int>

C# with Dictionary code:

Test result from hackerearth.com:

The time complexity analysis:
function CalculateSumOfEvenNumbers(), inside two loops, function GetLastDigit(...)
is called; inside GetLastDigit() function, there is a HashSet to prevent
duplicate calculation, and then, GetLastDigit() is called; inside GetLastDigit(),
two calls of the function GetDigits(). Actually, we only care about two integer
number, biggest same digit, and we do not care about how many digit inside
each integer. And this approach goes over each digit in the integer.



Self-defined hash function

Comparison to the self-defined hash function - code is here:
The performance:

Time analysis:

For each query, process two baskets of integers,  two separate loops, O(N1 + N2), detail see function ProcessInput(...); For each number, call Hash function to process, any number is at most 4 digits, each digit, only do one calculation to determine the digit from 1 to 9. Just a minus arithmetic calculation. Detail see the function Hash(char[] cache, int nthNumber, int serialNo)

To calculate the even number count, call function CheckNumberIsEven(...) N1 * N2 times, each function call, only need to look up at most 10 times, find a match then break the loop.

So, overall, time complexity is O(N1+N2) + O( N1*N2), is around O(10^6) calculation of CheckNumberIsEven function which includes a few of arithmetic calculations; the self-defined hash function is almost less than 1 percent of time to compare calculation the even number count.

Digits Internal Class

Another C# version, no Dictionary, just use int[10] to store an integer, with digits. No string manipulation to get the substring. Pass all test cases. Code is here.

Performance:

HashedInteger Class

Digits class name is not very meaningful, so HashedInteger class name is chosen to replace Digits.
And also Save API is not clear, add Convert, ConvertAll APIs instead.

The code is here.