dp[i][j][k] = min cost upto element A[i] with j segments already and the value A[i] was changed to k

const int INF = N + 1, MX = 1000;
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(K + 1,
                                            vector<int>(MX + 1, INF)));
    for (int i = 1; i <= MX; ++i) {
        dp[0][0][i] = 1;
    }
    dp[0][0][A[0]] = 0;
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j <= K; ++j) {
            int mn = INF;
            for (int v = 1; v <= MX; ++v) {
                mn = min(mn, dp[i - 1][j][v]);
            }
            // change A[i] to v
            for (int v = 1; v <= MX; ++v) {
                dp[i][j][v] = min(dp[i][j][v], dp[i - 1][j][v] + 1);
            }
            dp[i][j][A[i]] = min(dp[i][j][A[i]], dp[i - 1][j][A[i]]);
            // start new seg without change A[i]
            if (j < K) {
                dp[i][j + 1][A[i]] = min(dp[i][j + 1][A[i]], mn);
            }
            // start new seg with change A[i]
            if (j < K) {
                for (int v = 1; v <= MX; ++v) {
                    dp[i][j + 1][v] = min(dp[i][j + 1][v], mn + 1);
                }
            }
        }
    }

Here's my solution, which runs in $$$O(N^2K)$$$, which is slightly more efficient than the $$$O(NK A_i)$$$ solution given below (with the 15s time limit, the latter should still pass in time, but it may be slightly tight if implemented inefficiently).

First, we create an array $$$cost$$$, which stores, for each range in the set, the minimum number of changes in height we need to make every value in this range the same. We can see that this is equal to the length of the range minus the number of times the most common value in the range appears, and we can compute this in $$$O(N^2)$$$ by iterating over each possible starting position for the range, maintaining the number of times each value has occurred in our range, and maintaining the most common value in the range. Afterwards, we can iterate over the ending positions and set the values of our cost array accordingly.

Then, we let $$$dp[i][j]$$$ be the minimum number of edits we need to make the first $$$i$$$ elements of the array include at most $$$j$$$ changes in height. We can compute $$$dp[i][j]$$$ as the minimum value of $$$dp[k][j-1] + cost[k+1][i]$$$ over all $$$k$$$. There are $$$O(N)$$$ values of $$$k$$$ to check for each pair of $$$i$$$ and $$$j$$$, and we have $$$N$$$ values for $$$i$$$ and $$$K+1$$$ for $$$j$$$, so our total complexity is $$$O(N^2K)$$$.

We can convert A[i] to integers in the range [0 , n). This would reduce the complexity to O(n * n * k).

for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) dp[i][j][k] = INF;
        for(int i = 0; i < n; i++) dp[0][i][0] = (a[0] == i ? 0 : 1);
        for(int i = 1; i < n; i++){
            for(int prev = 0; prev < n; prev++){
                for(int cur : {a[i] , prev}){
                    for(int k = 0; k <= K; k++){
                        if((k - (prev == cur ? 0 : 1)) >= 0)
                            dp[i][cur][k] = min(dp[i][cur][k] , dp[i - 1][prev][k - (prev == cur ? 0 : 1)] + (cur == a[i] ? 0 : 1));
                    }
                }
            }
        }
        int ans = INF;
        for(int i = 0; i < n; i++){
            for(int k = 0; k <= K; k++){
                ans = min(ans , dp[n - 1][i][k]);
            }
        }

I used dp[i][j] where each state (i, j) represents minimum number of changes needed to build j segments (of equal elements) till index i. The final answer shall be minimum over all dp(n, j) where j ranges from 1 to k + 1 (If we have k + 1 segments => there are k changes). To calculate each state, (i, j) we loop from l = i to 1 and dp[i][j] = min(dp[i][j], dp[l][j — 1] + (l — i + 1 — max_count). Here, l represents the first element that will be present in the last segment. max_count is the maximum occurrence of any element in the range [l, i]. So basically, in the last segment, we will make all elements equal to the maximum occurring element.

Code: https://ideone.com/i80LgQ

We do complementary counting. There are initially $$$N^2$$$ ordered pairs of workers. Then, we subtract those which aren't valid mentorship pairs. Create a map mapping sets of skills to the number of times they appear in the data. Then, for each set of skills, iterate over its subsets. If set Y is a subset of set X and X appears A times in the data while Y appears B times in the data, then we have $$$AB$$$ invalid ordered mentorship pairs, since the $$$B$$$ workers with the skillset $$$Y$$$ cannot mentor the $$$A$$$ workers with the skillset $$$X$$$. We thus subtract the value of $$$AB$$$ for each subset of each skillset.

To evaluate our complexity, note that there are $$$N$$$ workers, each with $$$2^{C_i}$$$ subsets of its skillset. Moreover, each of these subsets takes $$$O(C_i)$$$ time to construct. If we use an unordered map to perform our count queries, our complexity is thus $$$O(N C_i 2^{C_i})$$$. I used a regular map in C++ to avoid the occasional hacks that plague unordered_map, and even with the extra $$$O(\log N)$$$ factor, this passed in time. (On Codeforces, my submission took just about eight seconds to solve a large test set twenty times, so it may have been a fairly tight squeeze, but it did seem to work out.)

Straightforward solution using bitset passes without any problem

I had a similar issue--I accidentally computed $$$N^2$$$ before converting to long on problem B. Luckily, I caught my error while testing my program's runtime to make sure it would actually pass the large dataset, so I was able to resubmit before the end of the contest (though unfortunately, it did drop me from 3rd to 16th).

my code's complexity was O(32*N*Log(32*N)) but I got TLE..

The basic idea is tree DP. We can arbitrarily root the tree and store three DP values for each vertex. One stores the maximum score over the subtree rooted at this vertex if this vertex is not illuminated at all, one stores the same value if this vertex is illuminated by one of its children but does not contain a lighthouse, and one stores the same value if our vertex contains a lighthouse. The transitions get a little messy but can be computed efficiently for an $$$O(N)$$$ solution in total. Feel free to check out my submission on the Google Kickstart website for implementation details on the transitions.

Usually when that's not mentioned, it means you should be able to handle $$$T$$$ cases of the maximum size, but I'm not sure if that's the case here.