In this HackerEarth Counting numbers problem solution, A number B is a subset of number A if you can delete some digits from number A to the remaining digits from number B.

You are given an N-digit number X and Xk is the largest K-digit subtype of the number X.

You must answer M queries. Each query consists of two numbers K and L. The answer to the query is the Lth digit of the number Xk.


HackerEarth Counting numbers problem solution


HackerEarth Counting numbers problem solution.

#include <bits/stdc++.h>

using namespace std;

vector<int> pos[10];
vector<int>::iterator p;

int lower_bound(int first, int last, int right, int K, int L) {
while (last - first > 0) {
int m = (first + last) / 2;
if (max(m, K + p[m - 1] - right) < L) {
first = ++m;
} else
last = m;
}
return first;
}

int G(int left, int right, int K, int L) {
for (int i = 9; i >= 0; --i) {
auto min_pos = lower_bound(pos[i].begin(), pos[i].end(), left);
auto max_pos = upper_bound(pos[i].begin(), pos[i].end(), right);
p = min_pos;
int c = max_pos - min_pos;
if (c > 0) {
int t[c+1];
t[1] = max(1, K + p[0] - right);
if (t[1] > L)
return G(left, p[0] - 1, t[1] - 1, L);
t[c] = max(c, K + p[c - 1] - right);
if (t[c] < L)
return G(p[c - 1] + 1, right, K - t[c], L - t[c]);
int j = lower_bound(1, c+1, right, K, L);
t[j] = max(j, K + p[j - 1] - right);
t[j-1] = max(j-1, K + p[j -2] - right);
if (t[j] == L) {
return i;
} else {
return G(p[j - 2] + 1, p[j - 1] - 1, t[j] - t[j - 1] - 1, L - t[j - 1]);
}
}
}
}

int main() {
ios_base::sync_with_stdio(false);

string x;
cin >> x;
int n = x.size();

for (int i = 1; i <= n; ++i)
pos[x[i-1]-'0'].push_back(i);

int m;
cin >> m;
for (int i = 0; i < m; ++i) {
int k, l;
cin >> k >> l;
cout << G(1, n, k, l);
}
cout << "\n";
}