We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Candles Counting
  5. Discussions

Candles Counting

  • dehaka
     + 0 comments

    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);
}