1799. Maximize Score After N Operations (Leetcode)

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

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.

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

Example: 1

Input: nums = [1,2]

Output: 1

Example: 2

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

Output: 11

Example: 3

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

Output: 14

Constraints:

• 1 <= n <= 7
• nums.length == 2 * n
• 1 <= nums[i] <= 10 ^ 6

Step I (Brute Force: Get all gcd pairs):

• First of all we require the gcd values of every pairs to check which pair needs to be taken, or is to be included into the result.

Implementation of the current step: pairs = new int[(nums.length * (nums.length - 1)) / 2][]; int pairs_i = 0; for(int i = 0; i < nums.length; i++) { for(int j = i + 1; j < nums.length; j++) { // each pairs is denoted as (i, j, gcd(nums[i], nums[j])) int[] a = new int[] {i, j, gcd(nums[i], nums[j])}; pairs[pairs_i++] = a; } }

Step II (Greedy: Pairs should be sorted in ascending order of gcd):

• As the problem statement requires, we must add the value i * gcd(x, y) to our final result.
• We can see that the pair having greatest gcd should be selected afterwards and the pair having lesser gcd should be selected before that. This in turn will increase the value of i * gcd(x, y).
• So we will sort the gcd pairs we have obtained.

Implementation of the current step: Arrays.sort(pairs, new Comparator<int[]>() { @Override public int compare(int[] p, int[] q) { return p[2] - q[2]; } });

Step III (Recursion & Bitmasking: Solving the problem recursively and keeping track using bitmasking):

• Let's say we have selected pairs[i], now we will go to all other pairs such that the elements in current pair does not coincide with the elements in the next pair. We can do this recursively.
• It is important to note here that we cannot use any index more than once. So we need to keep track of which indices have we currently included in our result set. We will do this using bitmasking.
• If we have selected an element at index i, we will set the i^th bit of our bitmask. This can be done by (1 << i) | bitmask.
• We can stop the recursion once we have collected all elements or no of selected pairs equals nums.length / 2.

Implementation of the current step: // taken = bitmask of all elements taken so far long recur(int idx, int order, int taken, int till) { // current pair int[] cur = pairs[idx]; // checking if we have already included the first element of our pair. If yes we will return min value to nullify this step if(((1 << cur[0]) & taken) != 0) return Integer.MIN_VALUE; if(((1 << cur[1]) & taken) != 0) return Integer.MIN_VALUE; // order = the depth upto which the recursion has gone till now. // when order reached nums.length / 2, recursion will stop and return a value. // till = nums.length / 2 if(order == till) { return order * cur[2]; } else { // marking the elements we have taken now. taken |= (1 << cur[0]); taken |= (1 << cur[1]); // calculating max from all sub-problems and returning the final result. long max = 0, here = order * cur[2]; for(int i = idx + 1; i < pairs.length; i++) { max = Math.max(max, here + recur(i, order + 1, taken, till)); } return max; } }

Step IV (Caching: Changing TLE to accepted):

• Now the above code will TLE, because the subproblems will be calculated again and again.
• So we will cache the result of the subproblems we have solved during recursion.
• It is important to note that, during recursion, we consider a sub-problem to be solved if we are returning a value from that recursion step.
• So we will cache the current recursion state, i.e (idx, order, taken) triplet.

Implementation of the current step: // taken = bitmask of all elements taken so far long recur(int idx, int order, int taken, int till) { // current pair int[] cur = pairs[idx]; // checking if we have already included the first element of our pair. If yes we will return min value to nullify this step if(((1 << cur[0]) & taken) != 0) return Integer.MIN_VALUE; if(((1 << cur[1]) & taken) != 0) return Integer.MIN_VALUE; // order = the depth upto which the recursion has gone till now. // when order reached nums.length / 2, recursion will stop and return a value. // till = nums.length / 2 if(order == till) { return order * cur[2]; } else { // checking if we have already solved this sub-problem // if yes then return its value if(dp[idx][order][taken] != 0) { return dp[idx][order][taken]; } // marking the elements we have taken now. taken |= (1 << cur[0]); taken |= (1 << cur[1]); // calculating max from all sub-problems and returning the final result. long max = 0, here = order * cur[2]; for(int i = idx + 1; i < pairs.length; i++) { max = Math.max(max, here + recur(i, order + 1, taken, till)); } // storing the result of current sub-problem (i.e idx, order, taken) dp[idx][order][taken] = max; return max; } }

Step V (State space optimization):

• We can see that the field order is not required necessarily, because once all elements are taken we can return the result. This can be found out by considering our taken varible.
• So caching of order variable is not required. This will reduce our state space and will make our code more optimal.

Implementation of the current step: // taken = bitmask of all elements taken so far long recur(int idx, int order, int taken, int till) { // current pair int[] cur = pairs[idx]; // checking if we have already included the first element of our pair. If yes we will return min value to nullify this step if(((1 << cur[0]) & taken) != 0) return Integer.MIN_VALUE; if(((1 << cur[1]) & taken) != 0) return Integer.MIN_VALUE; // order = the depth upto which the recursion has gone till now. // when order reached nums.length / 2, recursion will stop and return a value. // till = nums.length / 2 if(order == till) { return order * cur[2]; } else { // checking if we have already solved this sub-problem // if yes then return its value // notice that the order field is removed if(dp[idx][taken] != 0) { return dp[idx][taken]; } // marking the elements we have taken now. taken |= (1 << cur[0]); taken |= (1 << cur[1]); // calculating max from all sub-problems and returning the final result. long max = 0, here = order * cur[2]; for(int i = idx + 1; i < pairs.length; i++) { max = Math.max(max, here + recur(i, order + 1, taken, till)); } // storing the result of current sub-problem (i.e idx, taken) dp[idx][taken] = max; return max; } }

Full Code (Java): class Solution { long[][] dp; int[][] pairs; public int maxScore(int[] nums) { pairs = new int[(nums.length * (nums.length - 1)) / 2][]; int pairs_i = 0; for(int i = 0; i < nums.length; i++) { for(int j = i + 1; j < nums.length; j++) { int[] a = new int[] {i, j, gcd(nums[i], nums[j])}; pairs[pairs_i++] = a; } } Arrays.sort(pairs, new Comparator<int[]>() { @Override public int compare(int[] p, int[] q) { return p[2] - q[2]; } }); dp = new long[pairs.length][1 << nums.length]; long ans = 0, len = pairs.length - (nums.length / 2) + 1; for(int i = 0; i < len; i++) { ans = Math.max(ans, recur(i, 1, 0, nums.length / 2)); } return (int) ans; } long recur(int idx, int order, int taken, int till) { int[] cur = pairs[idx]; if(((1 << cur[0]) & taken) != 0) return Integer.MIN_VALUE; if(((1 << cur[1]) & taken) != 0) return Integer.MIN_VALUE; if(order == till) { return order * cur[2]; } else { if(dp[idx][taken] != 0) { return dp[idx][taken]; } taken |= (1 << cur[0]); taken |= (1 << cur[1]); long max = 0, here = order * cur[2]; for(int i = idx + 1; i < pairs.length; i++) { max = Math.max(max, here + recur(i, order + 1, taken, till)); } dp[idx][taken] = max; return max; } } int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } }