Cerinta completa

You are given a sequence of integers a1,a2,a3…..an. You are free to replace any integer with any other positive integer. How many integers must be replaced to make the resulting sequence strictly increasing?

Input Format
The first line of the test case contains an integer – the number of entries in the sequence.
The next line contains space separated integers where the integer is .

Output Format
Output the minimal number of integers that should be replaced to make the sequence strictly increasing.

Constraints

Sample Input #00

3
4 10 20

Sample Output #00

0

Sample Input #01

6
1 7 10 2 20 22

Sample Output #01

1

Sample Input #02

5
1 2 2 3 4

Sample Output #02

3

Explanation
In the first sample input, we need not replace anything, hence the output is 0.
In the second sample input, we can replace 2 with any integer between 11 and 19 to make the sequence strictly increasing, hence the output is 1.
In the third sample input, we can obtain 1, 2, 3, 4, 5 by changing the last three elements of the sequence.

Limbajul de programare folosit: cpp

Cod:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> tails;
    tails.reserve(n);

    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        long long b = a - i;
        if (b < 0) continue;

        auto it = upper_bound(tails.begin(), tails.end(), b); // LNDS on b
        if (it == tails.end()) {
            tails.push_back(b);
        } else {
            *it = b;
        }
    }

    cout << (n - (int)tails.size()) << '\n';
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464645879

Link challenge: https://www.hackerrank.com/challenges/modify-the-sequence/problem

Modify The Sequence