Let us first describe a
SimpleFunction
:SimpleFunction( string A,string B ){ int answer = 0; for( int dig = 1; dig <= 9; dig++ ){ if(string A contains digit dig and string B contains digit dig){ answer = answer * 10 + dig; } return answer; }
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, but still time out in last case; therefore, I had to study the code in C++ using self-defined hashing function. I also wrote a C# solution using the same ideas, and passed all test cases, no more timeout. Here is the code link.
I am looking for advice on code style, object-oriented programming, hash function insights, self-defined hash function comparison to a C# Dictionary
class.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace SimpleFunction_StudyCode
{
class Program
{
public static int DIGITS = 10;
public static int NO_BASKETS = 2;
public static int NUMBER_DIGITS = 1000;
public static int[][][] hashingResults = new int[NO_BASKETS][][]; // 2, 1000, 10 - 80KB
internal class QueryData
{
public int n1, n2;
public string[] numbers1, numbers2;
}
static void Main(string[] args)
{
ProcessSimpleFunction();
//RunSampleTestcase();
}
public static void RunSampleTestcase()
{
IList<QueryData> input = new List<QueryData>();
QueryData one = new QueryData();
one.n1 = 2;
one.n2 = 2;
one.numbers1 = new string[] {"234526", "8345" };
one.numbers2 = new string[] {"333564", "98847675" };
input.Add(one);
IList<string> result = CalculateProbabilty(input);
Debug.Assert(result[0].CompareTo("0.750") == 0);
}
public static void ProcessSimpleFunction()
{
IList<QueryData> input = ProcessInput();
IList<string> result = CalculateProbabilty(input);
foreach (string s in result)
Console.WriteLine(s);
return;
}
/*
* 1. calculate even number's count
* 2. calculate probability
* 3. convert to string - a decimal data type with 3 decimals
* 4. put the return in a list
*/
public static IList<string> CalculateProbabilty(IList<QueryData> input)
{
IList<string> output = new List<string>();
if (input == null || input.Count == 0)
{
output.Add(0.ToString("N3"));
return output;
}
HashingResults_Declaration();
foreach(QueryData data in input)
{
HashingResults_Initialization();
int n1 = data.n1;
int n2 = data.n2;
for (int i = 0; i < n1; i++)
{
char[] current = data.numbers1[i].ToCharArray();
Hash(current, i, 0);
}
for (int i = 0; i < n2; i++)
{
char[] current = data.numbers2[i].ToCharArray();
Hash(current, i, 1);
}
long count = 0;
for (int i = 0; i < n1; i++)
{
for (int j = 0; j < n2; j++)
{
count += CheckNumberIsEven(i, j);
}
}
float probability = (float)((float)(count) / (float)(n1 * n2));
output.Add(probability.ToString("N3"));
}
return output;
}
/*
* return: IList<QueryData>
*/
private static IList<QueryData> ProcessInput()
{
int queries = Convert.ToInt32(Console.ReadLine());
IList<QueryData> input = new List<QueryData>();
while (queries > 0)
{
QueryData data = new QueryData();
int[] baskets = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
data.n1 = baskets[0];
data.n2 = baskets[1];
data.numbers1 = new string[data.n1];
data.numbers2 = new string[data.n2];
for (int i = 0; i < data.n1; i++)
{
data.numbers1[i] = Console.ReadLine();
}
for (int i = 0; i < data.n2; i++)
{
data.numbers2[i] = Console.ReadLine();
}
input.Add(data);
queries--;
}
return input;
}
/*
* hashing function will be applied to the data, the result is a jagged array called hashingResults
* hashing results:
* int[NO_BASKETS][][]; // 2, 1000, 10 - 80KB
*/
private static void HashingResults_Declaration()
{
for (int i = 0; i < NO_BASKETS; i++)
{
hashingResults[i] = new int[NUMBER_DIGITS][];
for (int j = 0; j < NUMBER_DIGITS; j++)
{
hashingResults[i][j] = new int[DIGITS];
}
}
}
/*
* hashing results:
* int[NO_BASKETS][][]; // 2, 1000, 10 - 80KB
*/
private static void HashingResults_Initialization()
{
for (int i = 0; i < NO_BASKETS; i++)
{
for (int j = 0; j < NUMBER_DIGITS; j++)
{
for (int k = 0; k < DIGITS; k++)
{
hashingResults[i][j][k] = 0;
}
}
}
}
/*
*
* @cache - char[]
* @nthNumber - each basket has n numbers, n from 0 to N-1
* @serialNo - two baskets, so two values: 0, 1
*
* hash function -
* map data of arbitrary size to data of fixed size
* int[][][] cache = new int[2][][]; // 2, 1000, 10
* size of cache is 2 * 1000 * 10 * 4 bytes = 80KB
*
* '0' ascii value is 48
*/
private static void Hash(char[] cache, int nthNumber, int serialNo)
{
for (int i = 0; i < cache.Length; i++)
{
int digit = cache[i] - 48;
hashingResults[serialNo][nthNumber][digit] = 1;
}
}
/*
* digits from 1 to 9
* return: 1 - even number 0 - odd number
*/
private static int CheckNumberIsEven(int first, int second)
{
int digitValue = 9;
while (digitValue > 0)
{
if (hashingResults[0][first][digitValue] == 1 &&
hashingResults[1][second][digitValue] == 1)
{
break;
}
digitValue--;
}
return (digitValue % 2 == 0)? 1 : 0;
}
}
}
Edit:
After comment from @paparazzi - the solution is hard for follow
In order to understand the algorithm, I had to write down my calculation, and then, people can help me quickly for this hash algorithm, compute all options of dictionary choices before writing code, have some idea of reasonable size of space, continue to reduce the space from around \$2 MB\$ to \$80 KB\$.
For example, use C# Dictionary to construct a key for a simple(N1, N2), assuming that the key is constructed as \$(s1.CompareTo(s2) <= 0) ? (s1 + "-" + s2) : (s2 + "-" + s1)\$, how many possible strings? \$s1\$ represents integer \$N1\$, since \$N1 >= 0\$ and \$n1 <= 1000\$, so the choice is \$9*9*9 + 1 = 730\$, same applies to \$s2\$; therefore, possible key string is \$730 * 730 = 532900\$, assuming that each key string is at most 9 chars, one char uses one byte, so the processing space is \$523900 * 9 = 4823100 Bytes\$ (around \$4.8MB\$).
Actually, the digits's order in integer does not matter when to calculate simple function, therefore, no need to record the order. So, N1 >= 0 and n1 <= 1000, the possible choice \$9*8*7 + 1 = 505\$, the key used in the dictionary can have \$505 * 505 = 255025\$ choices, then \$255025 * 9 = 2295225 Bytes\$ (around \$2.2MB\$), reduce half of the space.
But, in order to be able to make it one second for six test cases, each test case has \$0.16\$ seconds, dictionary size will be good enough around \$4\$ percent of \$2.2MB\$, around \$80K\$.
Here is the solution introduced by the customized hash function - space: hashingResults = new int[NO_BASKETS][][], each basket will have \$1000\$ integer at most, each integer will have array of \$10\$ to store \$0\$ or \$1\$ for digit from \$1\$ to \$9\$, therefore, the hash dictionary size is \$2 * 1000 * 10\$, each one is integer - four bytes, the size is \$80K\$ Bytes. (actually if using bool, then, size at most \$20KB\$.)
For example, \$N1 = 12\$, we order number from \$1\$ to \$1000\$ starting index = \$0\$, so \$12\$ is \$11th\$ number, then \$hashingResults[0][11]\$ is an array: { \$0,1,1,0,0,0,0,0,0,0\$ };
if \$N2 = 122\$, \$121th\$ number in basket two, then the array \$hashingResults[1][121]\$ is an array: { \$0,1,1,0,0,0,0,0,0,0\$ }. As we know, we do not record how many \$2\$ in the number \$122\$, this reduces the space as well. we only record 2 is existing in the number, same as 1. \$121\$ and \$112\$ will hash to same array, the order of distinct digit is no longer needed to save in hashed result.
Also,the space is not so critical since there is \$256MB\$ memory requirement, but calculation of key takes time, more space means more time. My question seems to figure out the target dictionary size, around \$80KB\$, not \$2MB\$, considering all other factors, need help.
Since 3 of [4 numbers in an example] are even, probability is ¾
make my day. \$\endgroup\$