Proximity
SRM 839 · 2022-09-30 · by misof
Problem Statement
Time limit: 8 seconds
Two numbers are close if their absolute difference does not exceed D.
Given a collection of cards, each containing a number, its proximity score is the number of unordered pairs of cards such that their numbers are close.
For instance, if your cards have the numbers {3, 3, 4, 9, 6} and D = 2, the proximity score is 4: the pair of threes is close to each other, each three is close to the four, and the four is close to the six.
If we had the same collection but D was 6 or more, the proximity score would be 10 as each possible pair of cards would contain two numbers that are close.
You are given a sequence of cards that contain the numbers C[0..N-1] in this order. You are also given a sequence of Q queries. Query i describes one contiguous segment of the card sequence: cards at positions A[i] to B[i], inclusive.
For each query, determine the proximity score of the cards that form the given segment. Return the sum of answers to all queries, modulo 10^9 + 7.
In order to keep the input small, the numbers on the cards and the queries are both pseudorandom. Please use the pseudocode below to generate them. Note that all card numbers will be smaller than M and all queries will be intervals that contain at least L cards.
state = seed
A, B = two arrays of length Q
C = an array of length N
for i = 0 to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
C[i] = state modulo M
for i = 0 to Q-1:
state = (state * 1103515245 + 12345) modulo 2^31
ql = L + (state modulo (N-L+1))
state = (state * 1103515245 + 12345) modulo 2^31
A[i] = state modulo (N-ql+1)
B[i] = A[i] + ql - 1
Notes
- The reference solution does not depend on the input being pseudorandom.
Constraints
- N will be between 1 and 100,000, inclusive.
- Q will be between 1 and 100,000, inclusive.
- D will be between 0 and 100,000, inclusive.
- M will be between 1 and 100,000, inclusive.
- L will be between 1 and N, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
10 5 100 100 1 47 Returns: 27
The numbers on cards: C = {8, 5, 98, 91, 48, 33, 50, 27, 76, 37} The arrays that describe the queries: A = {3, 1, 7, 5, 5} B = {9, 1, 9, 7, 5} As D >= M, it's clear that for each query all possible pairs of cards are close, and thus the proximity score of a collection of x cards is x*(x-1)/2. Hence, our five queries have proximity scores 21, 0, 3, 3, and 0. The sum of all answers is 27.
10 5 100 100 1 42 Returns: 78
Same parameters, different seed. Here the generated arrays look as follows: C = {27, 64, 53, 6, 35, 32, 33, 66, 59, 52} A = {2, 1, 4, 0, 6} B = {7, 4, 7, 9, 9} The answers to queries are 15, 6, 6, 45, and 6, for a total of 78.
10 5 0 100 1 42 Returns: 0
Same arrays as in the previous example, but as now D = 0 and all the values in C are distinct, each query has the answer zero.
10 5 1 100 1 42 Returns: 4
Same arrays as in the previous two examples, but now D = 1. The numbers 32 and 33 are now close, as are the numbers 52 and 53. The queries that contain one or both of these pairs now have positive answers.
99997 99993 0 1 99997 12345 Returns: 999550455
All cards have zeros on them. Each pair of cards is close. Each query is the entire array. The answer to each query is N*(N-1)/2. The correct return value is Q times that, modulo 10^9 + 7.
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Proximity with a public method int count(int N, int Q, int D, int M, int L, int seed) · 69 test cases · 2 s / 256 MB per case