Codeforces - D. Make Them Equal

 Problem Link

Algorithm used: Knapsack DP

Time Complexity: O(N²)

In this problem, you start out with

1.  an array A of size N where all elements are initially 1
2.  an array B of size N where all elements are in the range 1 - 10³
3. an array C of size N where all elements are in the range 1 - 10⁶. 

In one operation, you may increase the value of A[i] by ⌊A[i] / x⌋, where x is a non negative integer. You may do this at most K times. For each A[i] that you modify, such A[i] = B[i], you receive C[i] coins. Find the most number of coins that you may receive while not performing more than K operations.

For each A[i], find the minimum number of operations needed to convert 1 to B[i]. This can be done using a simple BFS, where each node is the current value of A[i], and the distance to this node is the number of operations needed to reach this value. For a distance x, we can increase it by x/1, x/2, x/3 ... x/x. It doesn't make sense to divide x by any number greater than x, because then the increment would be equal to 0. So for each node, we add nodes x + x/1, x + x/2 ... x + x/x to a queue, so long as they haven't already been visited.

From here it is a simple knapsack problem, where we find out the maximum number of coins that we can receive, by performing no more than j operations and choosing from the first i items. However, this may get a TLE verdict, since j is at most K and i is at most N; K * N = 10⁹ * 10³ = 10¹².

To avoid this, observe that at most 12 operations are needed to covert 1 to B[i]. This means that a total of N * 12 ≈ 10⁴ operations will be done. Reset K to n * 12, if this is smaller. The computer will perform K * N = 10⁴ * 10³ = 10⁷ operations, which will be enough to pass.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + 1;

int moves[MAX_N], c[MAX_N], vis[MAX_N];

int main() {

    int T;

    cin >> T;

    while (T--) {

        int n, k;

        cin >> n >> k;

        k = min(k, n * 12);

        fill(moves, moves + n + 1, INT_MAX);

        for (int i = 1; i <= n; i++) {

            int x;

            cin >> x;

            queue <pair <int, int>> q;

            q.push({1, 0});

            fill(vis, vis + x + 1, false);

            while (!q.empty()) {

                int a = q.front().first;

                int b = q.front().second;

                q.pop();

                if (a == x) {

                    moves[i] = b;

                    break;

                }

                for (int i = 1; i <= a; i++) {

                    if (a + a / i <= x && !vis[a + a / i]) {

                        vis[a + a / i] = true;

                        q.push({a + a / i, b + 1});

                    }

                }

            }

        }

        for (int i = 1; i <= n; i++)

            cin >> c[i];

        vector <vector <int>> dp(n+1, vector <int> (k+1, 0));

        for (int i = 1; i <= n; i++) {

            for (int j = 0; j <= k; j++) {

                dp[i][j] = dp[i-1][j];

                if (j > 0)

                    dp[i][j] = max(dp[i][j], dp[i][j-1]);

                if (moves[i] > j)

                    continue;

                dp[i][j] = max(dp[i][j], dp[i-1][j - moves[i]] + c[i]);

            }

        }

        cout << dp[n][k] << '\n';

    }

}