Alice has 'a' candles. Each candle burns for one hour and then goes out. Alice, being a smart person, can make a new candle from 'b' went out candles. This new candle can be used like any other candle. Given 'a' and 'b', find the maximum number of hours Alice can light the candles. Assume that the value of ‘b’ is strictly greater than 1. Employee portal system

similar to the longest increasing subsequence where hackerrank gives u a vid to the solution, except instead of using lower_bound to do a log time search at each iteration, fenwick trees are used to keep track of the sum

O(N * log(max height) * 2^K), pass all test. good thing number of colors is 7 at max, or else this algo will blow for too many colors. no idea how to reduce the 2^K factor to K

void update(vector<vector<long>>& fenwick, int i, int subset, long value) {
    while (i < fenwick.size()) {
        fenwick[i][subset] = (fenwick[i][subset] + value) % 1000000007;
        i = i + (i & -i);
    }
}

long access(const vector<vector<long>>& fenwick, int i, int subset) {
    long sum = 0;
    while (i > 0) {
        sum = (sum + fenwick[i][subset]) % 1000000007;
        i = i - (i & -i);
    }
    return sum;
}

int candlesCounting(int N, int K, vector<long> H, vector<long> C, int maxH) {
    vector<vector<long>> fenwick(maxH + 1, vector<long>(1 << K));
    for (int i=0; i < N; i++) {
        update(fenwick, H[i], 1 << (C[i]-1), 1);
        for (int S = 1; S < (1 << K); S++) update(fenwick, H[i], S | 1 << (C[i]-1), access(fenwick, H[i]-1, S));
    }
    return access(fenwick, maxH, (1 << K) - 1);
}

int main()
{
    int N, K, x, y, maxH = 0;
    vector<long> H, C;
    cin >> N >> K;
    for (int i=1; i <= N; i++) {
        cin >> x >> y;
        H.push_back(x);
        C.push_back(y);
        maxH = max(maxH, x);
    }
    cout << candlesCounting(N, K, H, C, maxH);
}

Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Candles Counting Problem Solution

Here is Candles Counting problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-candles-counting-problem-solution.html

Alice has 'a' candles. Each candle burns for one hour and then goes out. Alice, being a smart person, can make a new candle from 'b' went out candles. This new candle can be used like any other candle. Given 'a' and 'b', find the maximum number of hours Alice can light the candles. Assume that the value of ‘b’ is strictly greater than 1.