cppAcademy
FROM LEARNING TO COMPETING

Beginner.
Your first challenges.

Bulgarian Informatics Group E · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad tasks and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group E also includes challenging national-level problems. Years follow Arena’s competition-season labels. Source clarifications are noted on affected tasks.
GROUP E2009 · EasyArrays & sequences

Circular Peaks and Valleys

National Olympiad — Regional round (2009 season)

Submission name: pickval.cpp

Solve in Editor →

Problem summary

A sequence lies around a circle. A peak is strictly greater than both neighbors; a valley is strictly smaller than both. Count each type, including comparisons across the last-to-first boundary.

Input

Positive integers, one per line, followed by a terminating 0.

Output

The peak count and valley count, separated by a space.

Constraints

At least four values; each is less than 1,000,000. No upper bound on the sequence length is stated.

Worked example

An independently prepared example for this explanation.

Input

4
3
7
2
0

Output

2 2

Solution analysis

  1. Store the values without the terminating zero. At index i, the left neighbor is (i + n − 1) mod n and the right neighbor is (i + 1) mod n.
  2. Use strict comparisons against both neighbors. Equal adjacent values prevent either a peak or a valley at that position.
  3. In the circle 4, 3, 7, 2, values 4 and 7 are peaks, while 3 and 2 are valleys. The value 4 must be compared with 2 as well as 3.

Why it works

For every position the modular indices identify exactly its two circular neighbors. The two tests are precisely the definitions of peak and valley. Each position is visited once, so both totals are correct.

Complexity: O(n) time and O(n) extra space.

Watch out. Do not include the terminating zero. Ordinary linear endpoints miss circular extrema; comparisons must be strict.

Commented C++17 solution

An independently written complete program with standard headers.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> values;
    int value;
    while (cin >> value && value != 0) {
        values.push_back(value);
    }
    int n = static_cast<int>(values.size());
    int peaks = 0;
    int valleys = 0;
    for (int i = 0; i < n; i++) {
        // Wrap both neighbors across the circular boundary.
        int left = values[(i + n - 1) % n];
        int right = values[(i + 1) % n];
        if (values[i] > left && values[i] > right) {
            peaks++;
        }
        if (values[i] < left && values[i] < right) {
            valleys++;
        }
    }
    cout << peaks << ' ' << valleys << '\n';
}

Source: Arena Olimpiici ↗