GDINT - Editorial

editorial
,
1

PROBLEM LINK:

Deepavali Code Battle - Good Integers

Author: Om Bindal
Editorialist: Om Bindal

DIFFICULTY:

EASY

PREREQUISITES:

Prefix-sum, Array

EXPLANATION:

Let us call an integer good if it is different from either of A_1, A_2, \dots, A_N.

For each i, find the number of good integers less than or equal to A_i . and record them as C_i.

Then, the K-th smallest good integer can be found as follows:

  • If C_N < K
    • The answer is always greater than A_N. Since every integer greater than A_N is a good integer, the answer is A_N + (K - C_N)ā€‹.
  • If C_N \geq K
    • Find with binary search the minimum i such that C_i \geq K, then the answer is greater than A_{i - 1}.ā€‹ and less than A_i (where we assume A_0 = 0). Since every integer greater than A_{iāˆ’1}ā€‹ and less than A_i. is a good integer, the answer is (A_i - 1) - (C_i - K), that is, C_i - K elements before A_{i - 1}.

The complexity is O(N+QlogN).

SOLUTIONS:

Setter's Solution 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for (auto& x : A) {
        cin >> x;
    }
    vector<long long> low(N);
    for (int i = 0; i < N; ++i) {
        low[i] = A[i] - (i + 1);
    }
    while (Q--) {
        long long K;
        cin >> K;
        const int idx = lower_bound(low.begin(), low.end(), K) - low.begin();
        if (idx == N) {
            cout << A[N - 1] + (K - low[N - 1]) << '\n';
        } else {
            cout << A[idx] - (low[idx] - K + 1) << '\n';
        }
    }
    return 0;
}