MANG Problem #45: Maximize Score After N Operations (Hard)

1. Problem Statement

You are given nums, an array of positive integers of size 2 * n. You must perform n operations.

In the i-th operation (1-indexed), you will:

• Choose two elements, x and y.
• Receive a score of i * gcd(x, y).
• Remove x and y from nums.

Return the maximum score you can receive after performing n operations.

2. Approach: DP + Bitmasking

We have an array of up to 14 elements (7 operations). A brute-force exploration of all pairs would be $O((2N)!)$, which is too slow.

Because $N$ is very small (max 14), this is a classic Bitmask DP problem. We use an integer's bits to represent the state of the array (e.g., 1001 means the first and fourth elements are available).

1. State: dp(mask) returns the max score for the remaining operations, given the current available elements (mask).
2. Operation Count: The operation number i can be derived from the number of set bits in the mask. i = (TotalElements - SetBits) / 2 + 1.
3. Transitions: For the current mask, try every possible pair of available elements. Find their GCD, multiply by i, and add the result of dp(new_mask). Return the maximum.

3. Java Implementation

public int maxScore(int[] nums) {
    int n = nums.length;
    // Memoization table for all 2^n possible bitmasks
    int[] dp = new int[1 << n];
    return solve(nums, (1 << n) - 1, dp);
}

private int solve(int[] nums, int mask, int[] dp) {
    if (mask == 0) return 0; // All elements used
    if (dp[mask] != 0) return dp[mask]; // Return cached result

    int n = nums.length;
    // Calculate which operation number we are on
    int opNum = (n - Integer.bitCount(mask)) / 2 + 1;
    int maxScore = 0;

    // Try all pairs of available elements
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) { // If element i is available
            for (int j = i + 1; j < n; j++) {
                if ((mask & (1 << j)) != 0) { // If element j is available
                    // Calculate score for this pair
                    int score = opNum * gcd(nums[i], nums[j]);
                    // Create new mask with elements i and j removed
                    int newMask = mask ^ (1 << i) ^ (1 << j);
                    
                    // Recursive call
                    maxScore = Math.max(maxScore, score + solve(nums, newMask, dp));
                }
            }
        }
    }
    dp[mask] = maxScore;
    return maxScore;
}

private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: Any array length $\le 20$ combined with a combinatorial optimization is almost always Bitmask DP. A 14-bit integer represents every combination of available elements effortlessly.
2. The State Space: dp[mask] caches the best score for a specific set of remaining numbers. It doesn't matter how we reached this mask (which pairs were picked previously), the optimal future score only depends on what's left.
3. Bit Operations:
   • (mask & (1 << i)) != 0 checks if the $i$-th bit is 1 (element is available).
   • mask ^ (1 << i) ^ (1 << j) toggles the $i$-th and $j$-th bits to 0 (removes the elements).

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "O(2^N * N^2) where N is the total number of elements. There are 2^N states, and for each state, we use two loops to try all O(N^2) pairs."
• Interviewer: "Could we pre-compute the GCDs?"
• You: "Yes, we could compute the GCD of all pairs once and store it in an $N \times N$ matrix to avoid redundant calculations inside the loops, which speeds up the constant factor significantly."