A Strip with Two Colors
National Olympiad — National round (2018 season)
Submission name: strip.cpp
Problem summary
Find the longest contiguous segment of a colored strip that uses at most two distinct colors. If several have maximum length, choose the one with the smallest starting position.
Input
n, then n integer color labels.
Output
The 1-based starting position and length of the chosen segment.
Constraints
1 ≤ n ≤ 100000; 1 ≤ color label ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
5 1 1 1 1 1
Output
1 5
Solution analysis
- Maintain a window [left,right] and a frequency table for the colors in it. Extend right one cell at a time and increase the number of distinct colors when its previous frequency was zero.
- While more than two colors remain, remove cells from the left. Stop shrinking as soon as the window is valid. It is then the longest valid segment ending at this right endpoint. Update the answer only for a strictly greater length.
- For 1 1 1 3 2 2 2, the windows 1 1 1 3 and 3 2 2 2 both have length 4. Keeping the first winner returns start 1. In the third sample, cells 4 through 9 use only colors 1 and 3, giving start 4 and length 6.
Why it works
Before adding a new right endpoint, all starts before left were already invalid. Adding another cell cannot make them valid. Removing leftmost cells until at most two colors remain therefore finds the earliest valid start for that endpoint, and hence its longest segment. Checking every endpoint finds a global optimum; strict improvement preserves the earliest maximum.
Watch out. The requirement is at most two colors, so one-color segments are valid. Decrease the distinct count only when a frequency reaches zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> colors(n);
for (int &color : colors) {
cin >> color;
}
vector<int> frequency(10001, 0);
int left = 0;
int distinct = 0;
int bestStart = 0;
int bestLength = 0;
for (int right = 0; right < n; ++right) {
if (frequency[colors[right]] == 0) {
++distinct;
}
++frequency[colors[right]];
// Shrink only until the window has at most two distinct colors.
while (distinct > 2) {
--frequency[colors[left]];
if (frequency[colors[left]] == 0) {
--distinct;
}
++left;
}
int length = right - left + 1;
if (length > bestLength) {
bestLength = length;
bestStart = left;
}
}
cout << bestStart + 1 << ' ' << bestLength << '\n';
}