Connection Status:
Competition Arena > SimilarNumberPairs

SimilarNumberPairs

SRM 854 · 2024-04-24 · by misof

SRM 854 · 2024-04-24 · by misof · Math
Class Name: SimilarNumberPairs
Return Type: long
Method Name: count
Arg Types: (int, int, vector<int>, int)
Problem Statement

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)

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
0)
3
2
{112233, 114455, 72255}
47
Returns: 3

Each of the three possible pairs of numbers in A has similarity exactly 2.

1)
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.

2)
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.

3)
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.

4)
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}.

5)
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.

Submissions are judged against all 109 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SimilarNumberPairs with a public method long long count(int N, int S, vector<int> Aprefix, int seed) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous