SubstringQueries
SRM 779 · 2020-02-20 · by misof
Problem Statement
You are given a
Consider the following type of query: We are given a positive integer integer X not exceeding the length of T. Consider all (contiguous) substrings of T that have length exactly X. Let Q(X) be the 0-based index in T where the lexicographically smallest among all these strings starts. In case of a tie, Q(X) is the smallest such index.
Let A be the sum of all Q(X), where X goes from 1 to the length of T. Return A modulo 10^18.
Constraints
- S will contain between 1 and 2,500 characters, inclusive.
- Each character in S will be a lowercase English letter ('a'-'z').
- k will be between 1 and 10^9, inclusive.
"aaaaaaaaa" 1 Returns: 0
In case of a tie, Q(X) is always the smallest possible value: in this case, zero.
"zaba" 2 Returns: 7
T = "zabazaba". All of Q(1) through Q(7) are equal to 1. For example, the lexicographically smallest substring of length 4 is "abaz", starting at index 1, so Q(4) = 1. Q(8) is 0.
"acaa" 2 Returns: 10
Q = {0, 2, 2, 2, 2, 2, 0, 0}
"aa" 4 Returns: 0
This is exactly the same T as in Example 0.
"topcoder" 3 Returns: 65
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SubstringQueries with a public method long long solve(string S, int k) · 136 test cases · 2 s / 256 MB per case