HackerEarth Akash and too many assignments solution

In this HackerEarth Akash and too many assignments problem Akash is an assignment-o-holic kind of a person, he’s crazy about solving assignments. So, to test his skills, his professor has given him an assignment to solve.

In this assignment, Akash is given a String S of length N consisting of lowercase letters (a – z) only. And he has to take care of 2 types of operations.

Operation type #1: [ 0 index c ] – 0 denotes the operation type #1. This operation expects you to change the character at index index to character c i.e., String[index] = c.

Operation type #2: [ 1 LeftLimit RightLimit K ] – 1 denotes the operation type #2. It expects you to print the lexicographically Kth smallest character in the sub-string of String S starting from LeftLimit to RightLimit, inclusively.

Help Akash out in solving this tricky assignment!

HackerEarth Akash and too many assignments problem solution.

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

const ll MOD = 1000000007;
const int MAX = 1000005;

int tree[MAX][30];

int read(int idx1, int idx2)
{
    int sum = 0;
    while(idx1 > 0)
    {
        sum += tree[idx1][idx2];
        idx1 -= (idx1 & -idx1);
    }
    return sum;
}

void update(int idx1, int idx2, int val, int n)
{
    while(idx1 <= n)
    {
        tree[idx1][idx2] += val;
        idx1 += (idx1 & -idx1);
    }
}


int main()
{
    int n, q, l, r, idx, k, c, ans;
    char y;
    string s;
    cin >> n >> q >> s;
    
    for(int i = 0;i < n;++i)
        update(i + 1, s[i] - 'a', 1, n);
        
    for(int i = 0;i < q;++i)
    {
        scanf("%d", &c);
        if(c)
        {
            scanf("%d %d %d", &l, &r, &k);
            ans = 0;
            int j;
            for(j = 0;j < 26;++j)
            {
                ans += read(r, j) - read(l - 1, j);
                if(ans >= k)
                    break;
            }
            if(ans >= k)
                printf("%cn", j + 'a');
            else printf("Out of rangen");
        }
        else
        {
            scanf("%d %c", &idx, &y);
            update(idx, s[idx-1] - 'a', -1, n);
            s[idx-1] = y;
            update(idx, s[idx-1] - 'a', 1, n);
        }
    }
    return 0;
}

Second solution

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

int tree[MAX][32];

void update(int idx1, int idx2, int val)
{
    while ( idx1 <= MAX-2 ) {
        tree[idx1][idx2] += val;
        idx1 += (idx1 & (-idx1));
    }
    return;
}

int query(int idx1, int idx2)
{
    int ans = 0;
    while ( idx1 > 0 ) {
        ans += tree[idx1][idx2];
        idx1 -= (idx1 & (-idx1));
    }
    return ans;
}

int main()
{
    int n,q,type,x,l,r,k;
    char y;
    string s;
    cin >> n >> q;
    cin >> s;
    for ( int i = 0; i < n; i++ ) update(i+1,s[i]-96,1);

    while ( q-- ) {
        cin >> type;
        if ( type == 0 ) {
            cin >> x >> y;
            update(x,s[x-1]-96,-1);
            s[x-1] = y;
            update(x,s[x-1]-96,1);
        }
        else {
            cin >> l >> r >> k;
            int cnt = 0;
            for ( int i = 1; i <= 26; i++ ) {
                cnt += query(r,i) - query(l-1,i);
                if ( cnt >= k ) {
                    cout << (char)(i+96) << endl;
                    goto p1;
                }
            }
            cout << "Out of range" << endl;
            p1: { }
        }
    }
    return 0;
}

coding problems solutions