2818. Apply Operations to Maximize Score

Problem Link

Description

---

You are given an array nums of n positive integers and an integer k.

Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:

• Choose any non-empty subarray nums[l, ..., r] that you haven't chosen previously.
• Choose an element x of nums[l, ..., r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.
• Multiply your score by x.

Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.

The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5.

Return the maximum possible score after applying at most k operations.

Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [8,3,9,3,8], k = 2
Output: 81
Explanation: To get a score of 81, we can apply the following operations:
- Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray. Hence, we multiply the score by nums[2]. The score becomes 1 * 9 = 9.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 1, but nums[2] has the smaller index. Hence, we multiply the score by nums[2]. The score becomes 9 * 9 = 81.
It can be proven that 81 is the highest score one can obtain.

Example 2:

Input: nums = [19,12,14,6,10,18], k = 3
Output: 4788
Explanation: To get a score of 4788, we can apply the following operations: 
- Choose subarray nums[0, ..., 0]. nums[0] is the only element in this subarray. Hence, we multiply the score by nums[0]. The score becomes 1 * 19 = 19.
- Choose subarray nums[5, ..., 5]. nums[5] is the only element in this subarray. Hence, we multiply the score by nums[5]. The score becomes 19 * 18 = 342.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 2, but nums[2] has the smaller index. Hence, we multipy the score by nums[2]. The score becomes 342 * 14 = 4788.
It can be proven that 4788 is the highest score one can obtain.

 

Constraints:

• 1 <= nums.length == n <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= min(n * (n + 1) / 2, 109)

Solution

---

Python3

def get_primes(n):
    p = 3
    sieve = [1 for _ in range(n+1)]
    while p*p <= n:
        if sieve[p]:
            for x in range(p*p, n+1, 2*p):
                sieve[x] = 0
        p += 2
    ret = [2]
    for i in range(3, n+1, 2):
        if sieve[i]:
            ret.append(i)
    return ret
 
PRIMES = get_primes(318)
 
class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        N = len(nums)
        M = 10 ** 9 + 7
        res = 1
        A = []
        count = []
        
        for i, x in enumerate(nums):
            p = 0
 
            for prime in PRIMES:
                if x % prime == 0:
                    p += 1
                
                while x % prime == 0:
                    x //= prime
                
                if prime * prime > x:
                    break
                
            if x != 1:
                p += 1
 
            count.append(p)
            A.append((p, i))
 
        A.sort(key = lambda x : (-x[0], x[1]))
 
        left = []
        stack = []
 
        for i in range(N):
            while stack and count[i] > count[stack[-1]]:
                stack.pop()
            
            if stack:
                left.append(i - stack[-1])
            else:
                left.append(i + 1)
 
            stack.append(i)
        
        right = []
        stack = []
 
        for i in range(N - 1, -1, -1):
            while stack and count[i] >= count[stack[-1]]:
                stack.pop()
            
            if stack:
                right.append(stack[-1] - i)
            else:
                right.append(N - i)
            
            stack.append(i)
        right.reverse()
 
        B = []
 
        for i, x in enumerate(nums):
            B.append((left[i] * right[i], x))
        
        B.sort(key = lambda x : -x[1])
 
        for n, x in B:
            operations = min(n, k)
            k -= operations
            res *= pow(x, operations, M)
            res %= M
 
            if k == 0: break
        
        return res