aboutsummaryrefslogtreecommitdiff
path: root/apply_operations_max_score.py
diff options
context:
space:
mode:
Diffstat (limited to 'apply_operations_max_score.py')
-rw-r--r--apply_operations_max_score.py72
1 files changed, 72 insertions, 0 deletions
diff --git a/apply_operations_max_score.py b/apply_operations_max_score.py
new file mode 100644
index 0000000..d0834de
--- /dev/null
+++ b/apply_operations_max_score.py
@@ -0,0 +1,72 @@
+# 2818. Apply Operations to Maximize Score
+
+"""
+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 maxmise your score by
+applying the following operation at most 'k' times: chose any non-empty
+element 'x' of 'nums[l .. r]' with the highest prime score. if multiple such
+elements exist, choose the one with the smallest index. multiple your score
+'x'. return the maximum possible score after applying at most 'k' operations.
+since the answer may be very large, return it module '10e9+7'
+"""
+
+
+class Solution(object):
+ mod = 10**9 + 7
+
+ def mod_pow(self, x, n):
+ res = 1
+ while n > 0:
+ if n % 2 == 1:
+ res = (res * x) % self.mod
+ x = (x * x) % self.mod
+ n //= 2
+ return res
+
+ def maximumScore(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ n = len(nums)
+ upper = max(nums) + 1
+ prime = [True] * upper
+ prime[0] = prime[1] = False
+ score = [0] * upper
+ for i in range(2, upper):
+ if prime[i]:
+ for j in range(i, upper, i):
+ score[j] += 1
+ prime[j] = False
+ next, stk = [n] * n, []
+ for i in range(n - 1, -1, -1):
+ while stk and score[nums[i]] >= score[nums[stk[-1]]]:
+ stk.pop()
+ next[i] = stk[-1] if stk else n
+ stk.append(i)
+ prev, stk = [-1] * n, []
+ for i in range(n):
+ while stk and score[nums[i]] > score[nums[stk[-1]]]:
+ stk.pop()
+ prev[i] = stk[-1] if stk else -1
+ stk.append(i)
+ ans = 1
+ tuples = [[nums[i], i] for i in range(n)]
+ tuples.sort(reverse=True)
+ for num, idx in tuples:
+ operations = min(
+ (idx - prev[idx]) * (next[idx] - idx),
+ k,
+ )
+ ans = (ans * self.mod_pow(num, operations)) % self.mod
+ k -= operations
+ if k == 0:
+ return ans
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumScore(nums=[8, 3, 9, 3, 8], k=2))
+ print(obj.maximumScore(nums=[19, 12, 14, 6, 10, 18], k=3))