Description

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

In the ith 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.

The function gcd(x, y) is the greatest common divisor of x and y.

 

Example 1:

Input: nums = [1,2]

Output: 1

Explanation: The optimal choice of operations is: (1 * gcd(1, 2)) = 1

Example 2:

Input: nums = [3,4,6,8]

Output: 11

Explanation: The optimal choice of operations is: (1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

Example 3:

Input: nums = [1,2,3,4,5,6]

Output: 14

Explanation: The optimal choice of operations is: (1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

 

Constraints:

• 1 <= n <= 7

• nums.length == 2 * n

• 1 <= nums[i] <= 106

Thinking

This problem is tagged as 'Hard'. Still, a DP problem. Basically, it is to find a way to pair all the numbers so that I will achieve the highest value. For the problems that will need to iterate all the possibilities, the backtracking approach should immediately comes to your mind. Backtracking is an ideology, the instance is depth first search which is using the recursive function.

My initial approach (DFS without memoization, TLE)

Following the standard DFS approach, the recursion function parameter includes the original data vector<int> nums, the round number we need to track int round, a table to record if a position has been visited – vector<int> visited, and the final result to pass to the end int sum. The termination condition is when all numbers get paired, i.e. the round reach to the nums.size() / 2 + 1. Inside the recursion function, we will use two loop to iterate all pairs in the nums array, and use visited array to mark the status. Once we find a new pair, mark it as visited and goes to the next round. When we coming back from the inner dfs, we reverse the visiting status for future use.

​x
class Solution {
    int ans;
public:
    void dfs(vector<int>& nums, int round, vector<int>& visited, int sum) {
        if(round > nums.size() / 2) {
            ans = max(ans, sum);
            return;
        }

        for(int i=0;i<nums.size();++i) {
            if(visited[i] == 1) continue;
            visited[i] = 1;
            for(int j=i+1;j<nums.size();++j) {
                if(visited[j] == 1) continue;
                visited[j] = 1;
                dfs(nums, round+1, visited, sum + round * __gcd(nums[i], nums[j]));
                visited[j] = 0;
            }
            visited[i] = 0;
        }


    }

    int maxScore(vector<int>& nums) {
        ans = 0;
        vector<int> visited(nums.size(), 0);
        dfs(nums, 1, visited, 0);

        return ans;
    }
};

This code passed some test and finally get a TLE which is expected since we don't have memoization to avoid the repeated calculation.

DFS with memoization

I think the hard part for memoization in this problem is how to identify a stage in the whole process. As we all know, the memoization is a mapping process between the calculated stage and the calculated value. In normal DP problems, such stage is easy to define. But here, how to denote the paired information into one state. After referencing the editorial, I realized that we could use bit mask. Each number is denoted by one number, either 0 or 1. If a number gets paired, the corresponding number would be 1 and vice versa. Initially, everyone is not visited so the mask = 0, i.e. every bit is 0. Now, we can use mask denote the whole state of whether the number is paired. The rest logic is basically the same to what we already achieved.

xxxxxxxxxx
class Solution {
    int ans;
public:
    int dfs(vector<int>& nums, int round, vector<int>& memo, int mask) {
        if(round > nums.size() / 2) {
            return 0;
        }

        if(memo[mask] != -1) {
            return memo[mask];
        }

        int ret = 0;
        for(int i=0;i<nums.size();++i) {
            if(((mask >> i) & 1) == 1) continue; // Check if it is visited
            for(int j=i+1;j<nums.size();++j) {
                if(((mask >> j) & 1) == 1) continue; // Check if it is visited
                
                // Create a new mask to pass to the next dfs
                int newMask = mask | (1 << j) | (1 << i); // Mark i and j is visited
                int currScore = round * __gcd(nums[i], nums[j]);
                int remainingScore = dfs(nums, round+1, memo, newMask);
                ret = max(ret, currScore + remainingScore);
            }
        }

        memo[mask] = ret;
        return ret;
    }

    int maxScore(vector<int>& nums) {
        ans = 0;
        vector<int> memo(1 << nums.size(), -1);

        return dfs(nums, 1, memo, 0);
    }
};

What I learned

The bit mask sometimes is a great way to denote a complex state. Bare this in mind!