SimilarNumberPairs | Topcoder Archive

Problem Statement

All numbers in this problem are non-negative integers smaller than 10^6. For the purpose of this problem they all have as many leading zeros as needed to pad all of them to exactly 6 digits. For example, 47 becomes 000,047.

The similarity between two numbers is calculated by counting the positions at which their digits match. For example:

the similarity between any two equal numbers is 6,
the similarity between 1234 and 2341 is 2 (the two leading zeros in 001,234 match the two leading zeros in 002,341),
the similarity between 123,456 and 333,333 is 1 (both have the digit 3 in the thousands place), and
the similarity between 123,456 and 654,321 is 0.

You are given an array A containing N numbers, and a similarity value S. Count all pairs of elements of A with exactly this similarity.

More formally, count all pairs (i, j) such that 0 <= i < j < N and the similarity between A[i] and A[j] is exactly S.

Return that count.

In order to keep the input small, long arrays A are generated pseudorandomly. Please use the pseudocode below:


L = length(Aprefix)
for i = 0 to L-1:
    A[i] = Aprefix[i]

state = seed
for i = L to N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    A[i] = (state modulo 1000000)

Definition

Class:: SimilarNumberPairs
Method:: count
Parameters:: int, int, int[], int
Returns:: long
Method signature:: long count(int N, int S, int[] Aprefix, int seed)
(be sure your method is public)

Notes

The reference solution does not depend on the input being pseudorandom. It would correctly solve any input of an allowed size.

Constraints

N will be between 2 and 200,000, inclusive.
S will be between 0 and 6, inclusive.
Aprefix will have between 0 and min(N, 200) elements, inclusive.
Each element of Aprefix will be between 0 and 999,999, inclusive.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

```
3
```
```
2
```
```
{112233, 114455, 72255}
```
```
47
```
```
Returns: 3
```
Each of the three possible pairs of numbers in A has similarity exactly 2.
```
7
```
```
6
```
```
{42, 42, 42, 42, 42, 42, 42}
```
```
47
```
```
Returns: 21
```
The array A may contain duplicates. Remember that we are counting pairs of indices.
```
7
```
```
5
```
```
{111111, 111112, 111122, 111222, 112222, 122222, 222222}
```
```
47
```
```
Returns: 6
```
Each pair of consecutive elements of this array has similarity exactly 5. No other pair has similarity exactly 5.
```
7
```
```
3
```
```
{111111, 111112, 111122, 111222, 112222, 122222, 222222}
```
```
47
```
```
Returns: 4
```
Same array, but now we are counting the pairs with similarity 3 instead of 5.
```
10
```
```
1
```
```
{123456, 234567}
```
```
5678
```
```
Returns: 10
```
Watch out for integer overflow when generating the pseudorandom part of A. The full array A you are supposed to generate in this test case looks as follows: {123456, 234567, 772239, 228444, 418021, 730426, 81899, 681800, 348577, 193926}.
```
3
```
```
0
```
```
{123456, 3789, 56789}
```
```
0
```
```
Returns: 1
```
The first and the last element of this A have similarity 0. The middle element has similarity 1 with the first one and similarity 4 with the last one.

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.