HackerEarth - SimpleFunction

Problem statement


Let us first describe a SimpleFunction:

SimpleFunction( string A,string B ){

int answer = 0;
for( int dig = 1; dig


So basically this function receives two strings as an input and
returns a value.


Akshara recently gained interest in coding and she came across this interesting question. She had 2 baskets. Each basket contained a
few strings. She wanted to find out what is the probability of
picking up 2 strings, 1st string from the first basket and the 2nd
string from the second basket, such that the value returned from the
Simple function would be an even value.


Since she is not that good at Mathematics, she turns to you for help.
Please help her in solving this problem!


Input: The first line contains an integer \$T\$ denoting the number of test cases. The first line of each test case contains 2
integers \$N1\$ and \$N2\$ denoting the size of first basket and
second basket respectively. This is followed up by \$(N1 + N2)\$
lines. Each line contains a string. The first \$N1\$ string correspond
to the first basket while the remaining to the second basket.


Output:


For each test case output the required probability correct up to 3
decimal places.


Constraints:

• \$1 \le T \le 10\$

• \$1 \le N1, N2 \le 1000\$

• \$1 \le \text{Length of String} \le 1000\$

Every String is composed of digits from [1 - 9]


Sample input

1
2 2
234526
8345
333564
98847675



Sample output

0.750



Explanation


The output of all the combination will be:

Simple(234526,333564) = 3456
Simple(8345,333564) = 345
Simple(8345,98847675) = 458
Simple(234526,98847675) = 456



Since 3 of them are even, probability is \$\frac{3}{4}\$.


Time Limit: 1.0 sec(s) for each input file.


Memory Limit: 256 MB

My introduction of the algorithm:

I used a C# Dictionary` to do memorization to cut time, and also process the input string to the best, bu

(I am under the impression this question justifies three largely independent answer parts: 1) documentation/description of the approach chosen (and the analysis leading to it) 2) problem analysis 3) coding (and maybe 4) asking CR_). I don't quite feel like doing every part justice.)

In the first revision, there was no description of your overall approach; in particular, not in the code presented -

try again, top down as many levels as needed, using what documentation tool support there is for C#. For "everything" in the code, document what it is to accomplish.

If any one description needs more than "one screen" (cannot easily be viewed without scrolling), it (or the entity described) probably is too involved an should be broken down/simplified/shortened. (A "page" of about 65 lines by 80 characters is a lot, a FORTH screen used to have 16*64 (my #1: polymorphism support).)

For lack of documentation, your approach and analysis has to be second guessed from the code. (I will use signature where you used hash (which I imagine different from the use I have seen here).) For each test case (not intending to give iteration through test cases notable attention):


foreach input string of digits

 compute a signature and add to its basket

foreach pair of digit strings from different baskets

 evaluate (a simplification of) SimpleFunction, counting the results

output proportion as required

You noticed that just the last bit of the value of SimpleFunction is used in the described check, and implemented CheckNumberIsEven() using an "early-out" encountering the largest common digit.
Apparently, this uses O(N1 * N2) evaluations of SimpleFunction. (I failed to find an analytical approach promising to be much faster for just shy of a million pairs.)

The evaluation of SimpleFunction better be fast - you seem to plan to cache function results, an do back-of-the-envelope calculations of the resources required.

The impact of memoisation depends on the time taken to (re-)compute a result and to retrieve it, respectively - let's try to make computation fast.

The signatures for the digit strings are the sets of digits used, in a normalised representation. As long as DIGITS is no larger than the number of bits handled in a basic operation, this can be handled as a "bit set", allowing fast intersection (bitwise and), union (or), ….

With nine digit values allowed, there are 29(-1) possible combinations: one could represent the baskets with 2511 10-bit counts, one for each possible set of digits, instead of 21000 9-bit signatures.

To check if SimpleFunction for a pair of signatures would be even, get "the and" representing digits common to both strings, find the highest common digit using Integer.low/highestOneBit() or some such and map to even/odd.

Where is the code documentation?

Everything not in the code will get separated - when code is copied and pasted into a different context, if not before. (Another thing python got right: the doc strings are between essential parts of the code.)

QueryData/ProcessInput(): Dispensable - whenever you can, process as you go.

Giving it a try (with presentational abbr.), in Java for lack of a C# environment:

/** Hacker Earth SimpleFunction.
 * For each test case, output the relative frequency of
 * pairs with an even highest common digit
 */
class Program
    /** (natural) multiplicity with each member */
    static class MultiSet extends java.util.AbstractSet {
        ...
    }

    static final int
        DIGITS = 10,
        EVEN_DIGITS = 0b10101010, // doesn't even (include '0')
        ODD_DIGITS = 0b101010101;
    /** maps each digit's int value to the bit used in digit bit sets */
    static final int DIGIT_BIT[] = new int[DIGITS];
    static {
        for (int i = DIGITS ; -1 digits with basket */
    static void tally(String digits, MultiSet basket) {
        int digit_set = 0;
        for (char d: digits.toCharArray())
            if ('0'  basket_a, 
            MultiSet basket_b) {
        long even = 0, odd = 0;
        for (Map.Entry a:
             basket_a.multiplicity.entrySet())
            for (Map.Entry b:
                 basket_a.multiplicity.entrySet()) {
                long pairs = a.getValue().intValue()
                           * b.getValue().intValue();
                if (NoOddHighestCommonDigit(
                        a.getKey(), b.getKey()))
                    even += pairs;
                else
                    odd += pairs;
            }
        return (double)even / (even + odd);
    }

    public static void main(String[] args) {
        MultiSet basket1 = new MultiSet<>(9),
            basket2 = new MultiSet<>(9);
        tally("234526", basket1);
        tally("8345", basket1);
        tally("333564", basket2);
        tally("98847675", basket2);
        System.out.println(even_proportion(basket1, basket2));
    }
}

StackExchange Code Review Q#151436, answer score: 2