HashQuality | Topcoder Archive

Problem Statement

Consider the following hash algorithm for sequences of bits (indexes are 0-based):

   function hash(bits)
      set key = 0
      prepend '0' to bits
      for( i = 1 to lengthof(bits)-1 )
         if(bits[i-1]=='0' and bits[i] == '0') key = (key * mults[0] + adds[0]) % size
         if(bits[i-1]=='0' and bits[i] == '1') key = (key * mults[1] + adds[1]) % size
         if(bits[i-1]=='1' and bits[i] == '0') key = (key * mults[2] + adds[2]) % size
         if(bits[i-1]=='1' and bits[i] == '1') key = (key * mults[3] + adds[3]) % size
      end
      return key
   end

The algorithm first prepends the bit '0' to the input sequence, and then iterates over all the bits, starting with the second bit (the first one in the input sequence). key is adjusted according to the problem inputs mults, adds, and size. Your task is to evaluate the quality of this hash function. Considering all possible sequences with between 1 and bits bits, inclusive, find a key that has the most collisions. That is, find a key that is generated most often by the sequences of bits. Your method should return the number of sequences of bits that generate this key.

Definition

Class:: HashQuality
Method:: collisionCount
Parameters:: int, int[], int[], int
Returns:: long
Method signature:: long collisionCount(int bits, int[] mults, int[] adds, int size)
(be sure your method is public)

Constraints

mults and adds will each have exactly 4 elements between 0 and 1000, inclusive.
size will be between 1 and 10,000, inclusive.
bits will be between 1 and 50, inclusive.

Examples

```
1
```
```
{1,2,3,4}
```
```
{1,2,3,4}
```
```
10
```
```
Returns: 1
```
There are two possible sequences: "0" and "1". For the sequence "0", we prepend '0' to get "00". There is only one iteration through the loop, and it changes key from 0 to 1. For the sequence "1", we prepend to get "01". The iteration through the loop changes key from 0 to 2.
```
3
```
```
{1,2,3,4}
```
```
{1,2,3,4}
```
```
10
```
```
Returns: 4
```
The 14 possible sequences hash as follows: bits | key -----+----- 0 | 1 1 | 2 00 | 2 01 | 4 10 | 9 11 | 2 000 | 3 001 | 6 010 | 5 011 | 0 100 | 0 101 | 0 110 | 9 111 | 2 4 of the sequences generate the key 2, so the return is 4.
```
5
```
```
{11,2,13,47}
```
```
{13,23,31,43}
```
```
20
```
```
Returns: 8
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.