In this HackerEarth Retrieve passwords problem A password is a number that is exactly divisible by 9. It is the largest number that can be formed by rearranging all the available digits in a provided range (L, R) inclusive and adding another number of your own choice to this sequence at any position. The password is missing a digit that must be added. You are also given an encrypted number. You are also provided q queries. The queries could be of two types.

Update a digit at a position.
Determine the largest number that is divisible by 9 in the provided range with the mentioned conditions. In the provided mentioned number, print its xth digit.
You must retrieve the password.


HackerEarth Retrieve passwords problem solution


HackerEarth Retrieve passwords problem solution.

#include <bits/stdc++.h>
#//include <ext/pb_ds/assoc_container.hpp>
#//include <ext/pb_ds/tree_policy.hpp>
#//include <ext/pb_ds/detail/standard_policies.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//insert(), find_by_order(), order_of_key()
typedef long long int ll;
typedef unsigned long long int llu;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define ref(i, n) for (int i = 0; i < n; ++i)
#define rer(i, n) for (int i = n; i >= 0; --i)
#define refv(i, n, k) for (int i = k; i <= n; ++i)
#define rerv(i, n, k) for (int i = k; i >= n; --i)
#define fi first
#define pii pair<int, int>
#define piii pair<pii, int>
#define priority_queue_2 priority_queue<int, vector<int>, greater<int>>
#define se second
#define fast1 ios_base::sync_with_stdio(false)
#define fast2 cin.tie(NULL)
inline void pin(int n)
{
    printf("%d\n", n);
}
#define onec(x) __builtin_popcount(x);
#define all(x) x.begin(), x.end()
double PI = acos(-1);
const int inf = 0x3f3f3f3f;
#define sv()         \
    int t;           \
    scanf("%d", &t); \
    while (t--)
#define MOD 1000000007
#define TRACE
#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif

struct node
{
    vector<int> p;
    node()
    {
        p.resize(10, 0);
    }
};

string s;
int n;
vector<node> v(1000005);

void update(int pos, int val, int no)
{
    while (pos <= n)
    {
        v[pos].p[no] += val;
        pos += pos & (-pos);
    }
}

int sum(int pos, int no)
{
    int s = 0;
    while (pos > 0)
    {
        s += v[pos].p[no];
        pos -= pos & (-pos);
    }
    return s;
}

int main()
{
    bool ti= false;
    fast1;
    fast2;
    cin >> s;
    n = s.size();
    clock_t start, end;
    start = clock();
    assert(n <= 1000000);
    for (int i = 0; i < n; i++)
        update(i + 1, 1, s[i] - '0');
    int q;
    cin >> q;
    assert(q <= 500000);
    vector<int> m(10, 0);
    while (q--)
    {
        int t;
        cin >> t;
        assert(t == 2 || t == 1);
        if (t == 1)
        {
            int x, y;
            cin >> x >> y;
            assert(x>0 && x <= n);
            assert(y >= 0 && y < 10);
            int old = s[x-1] - '0';
            if(old==y) 
                continue;
            s[x-1] = (char)(y + '0');
            update(x , -1, old);
            update(x , 1, y);
            //cout<< s << endl;
        }
        else
        {
            int l, r, x;
            cin >> l >> r >> x;
            assert(l <= n && r >= l && r <= n && l>0);
            assert(x>0 && x <= (r - l + 2));
            for (int i = 0; i < 10; i++)
            {
                m[i] = sum(r, i);
                m[i] -= sum(l-1, i);
                //trace2(i,m[i]);
            }
            int ss = 0;
            for (int i = 1; i < 10; i++)
            {
                ss += ((i % 9) * (m[i] % 9)) % 9;
                ss %= 9;
            }
            m[9 - ss]++;
            for (int i = 9; i >= 0; i--)
            {
                if (m[i] >= x)
                {
                    cout << i << endl;
                    break;
                }
                x -= m[i];
            }
        }
    }
    end = clock();
    if(ti){
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
    cout << "Time taken by program is : " << fixed
         << time_taken << setprecision(5);
    cout << " sec " << endl;}
    return 0;
}