Greedy Validation of Monotonic Sequences

Determining whether an array can be transformed into a non-decreasing sequence under specific modification rules requires a greedy traversal approach. The core condition involves checking adjacent elements and applying a limited increment operation when a descending pair is encountered.

Algorithmic Strategy

Iterate through the sequence from left to right. For each element, compare it with its immediate predecessor. If the current element is strictly smaller, it violates the non-decreasing property. Apply an increment of one to the current element to attempt to satisfy the condition. A common pitfall is ignoring the boundary condition where the gap between the predecessor and the current element exceeds one. A single increment operation cannot bridge a gap of two or more, meaning the sequence must be rejected immediately. Additionally, track the total number of such modifications; exceeding the allowed threshold results in failure.

Implementation

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int num_elements;
    cin >> num_elements;
    
    vector<long long> sequence(num_elements);
    for (int i = 0; i < num_elements; ++i) {
        cin >> sequence[i];
    }

    int adjustment_count = 0;
    bool is_valid = true;

    for (int i = 1; i < num_elements; ++i) {
        if (sequence[i] < sequence[i - 1]) {
            adjustment_count++;
            sequence[i]++; 
            
            if (sequence[i] < sequence[i - 1]) {
                is_valid = false;
                break;
            }
        }
    }

    if (!is_valid || adjustment_count > 1) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }

    return 0;
}