Groups of Neighboring Values
National Olympiad — National round (2025 season)
Submission name: sequence.cpp
Problem summary
Split an array into maximal contiguous groups: neighboring elements stay in the same group exactly when their absolute difference is one. Find the group count, maximum group length, and maximum number of distinct values in one group.
Input
N, then N positive integers.
Output
The three requested maxima/counts on one line.
Constraints
1 ≤ N ≤ 100000; 1 ≤ a[i] ≤ 100000.
Worked example
An independently prepared example for this explanation.
Input
11 6 3 4 3 4 3 8 7 6 2 3
Output
4 5 3
Solution analysis
- Start a new group whenever the absolute difference from the previous value is not one. Track its length, minimum and maximum.
- A walk whose steps are ±1 cannot skip an integer between its minimum and maximum: to reach the farther endpoint, it must cross each intermediate value. Therefore its distinct-value count is maximum−minimum+1; no set is needed.
- The sample groups are 6; 3,4,3,4,3; 8,7,6; and 2,3. There are four groups, the longest has five values, and the most distinct values occur in 8,7,6, giving three.
Why it works
The boundary test follows exactly the grouping rule, so the scan identifies all maximal groups. Within each group the unit-step property guarantees its values fill the entire integer interval from minimum to maximum. Maximizing the tracked lengths and interval sizes gives the requested results.
Watch out. Equal neighbors have difference zero and split the group. The longest group and the group with most distinct values need not be the same.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, previous;
cin >> n >> previous;
int groups = 1, length = 1, minimum = previous, maximum = previous;
int bestLength = 1, bestDistinct = 1;
for (int i = 1; i < n; i++) {
int value;
cin >> value;
if (abs(value - previous) != 1) {
groups++;
length = 1;
minimum = value;
maximum = value;
} else {
length++;
minimum = min(minimum, value);
maximum = max(maximum, value);
}
bestLength = max(bestLength, length);
// Unit steps visit every integer between the group minimum and maximum.
bestDistinct = max(bestDistinct, maximum - minimum + 1);
previous = value;
}
cout << groups << ' ' << bestLength << ' ' << bestDistinct << '\n';
}