Substrings Containing a Marked Letter
Autumn Tournament (2011)
Submission name: substring.cpp
Problem summary
A length-n string consists of two letters a at positions p and q and b everywhere else. Count contiguous substrings containing at least one a, modulo 123456789.
Input
n p q, with positions numbered from 1.
Output
The required count modulo 123456789.
Constraints
1 < n < 1000000; 1 ≤ p < q ≤ n.
Worked example
Original statement sample.
Input
7 2 5
Output
21
Solution analysis
- There are T(n)=n(n+1)/2 nonempty substrings in total: choose a left endpoint and then any right endpoint at or after it. Counting the complement is easier than treating substrings that contain the first a, the second a, or both separately.
- A substring with no a must lie wholly in one of the three b-only gaps. Their lengths are p−1, q−p−1 and n−q. Subtract T of each gap from T(n), then take the stated modulus. The actual string does not need to be constructed.
- For n=7,p=2,q=5, all substrings total 28. The gaps have lengths 1,2,2 and contain 1+3+3=7 all-b substrings. The required answer is 28−7=21.
Why it works
Every substring either contains a marked letter or lies in exactly one maximal b-only gap. These cases are disjoint and exhaustive. Subtracting the counts for the three gaps therefore leaves exactly the requested substrings.
Watch out. Count positions from 1 and allow empty gaps, whose triangular count is zero. Use long long before multiplying n(n+1); a 32-bit intermediate can overflow. Count substrings by positions, not distinct resulting text strings.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
long long triangular(long long length){
return length*(length+1)/2;
}
int main(){
long long n;
long long p;
long long q;
cin>>n>>p>>q;
const long long modulus=123456789;
// Remove substrings wholly inside one of the three unmarked gaps.
long long answer=triangular(n)-triangular(p-1)-triangular(q-p-1)-triangular(n-q);
cout<<answer%modulus<<'\n';
}