diff options
-rw-r--r-- | apply_operations_max_score.c | 92 | ||||
-rw-r--r-- | apply_operations_max_score.py | 72 |
2 files changed, 164 insertions, 0 deletions
diff --git a/apply_operations_max_score.c b/apply_operations_max_score.c new file mode 100644 index 0000000..166c756 --- /dev/null +++ b/apply_operations_max_score.c @@ -0,0 +1,92 @@ +// 2818. Apply Operations to Maximize Score +#include "leetcode.h" + +/* + * 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' + */ + +static int mod = 1e9 + 7, *vals; + +void prime_score(int *score, int upper) { + memset(score, 0, upper * sizeof(int)); + for (int i = 2; i < upper; i++) + if (!score[i]) + for (int j = i; j < upper; j += i) + score[j] += 1; +} + +long long mod_pow(long long base, long long exp, long long mod) { + long long res = 1; + while (exp) { + if (exp % 2 == 1) + res = (res * base) % mod; + base = (base * base) % mod; + exp /= 2; + } + return res; +} + +int cmp(const void *a, const void *b) { + return vals[*(int *)b] - vals[*(int *)a]; +} + +int maximumScore(int *nums, int n, int k) { + int upper = 0; + for (int i = 0; i < n; i++) { + if (nums[i] > upper) + upper = nums[i]; + } + upper++; + int *score = (int *)malloc(upper * sizeof(int)); + int *next = (int *)malloc(n * sizeof(int)); + int *prev = (int *)malloc(n * sizeof(int)); + int *stack = (int *)malloc(n * sizeof(int)); + prime_score(score, upper); + int top = -1, ans = 1; + for (int i = 0; i < n; i++) { + while (top >= 0 && score[nums[i]] > score[nums[stack[top]]]) + top--; + prev[i] = (top >= 0) ? stack[top] : -1; + stack[++top] = i; + } + top = -1; + for (int i = n - 1; i >= 0; i--) { + while (top >= 0 && score[nums[i]] >= score[nums[stack[top]]]) + top--; + next[i] = (top >= 0) ? stack[top] : n; + stack[++top] = i; + } + int *indices = (int *)malloc(n * sizeof(int)); + for (int i = 0; i < n; i++) + indices[i] = i; + vals = nums; + qsort(indices, n, sizeof(int), cmp); + for (int i = 0; i < n && k > 0; i++) { + int idx = indices[i], num = nums[idx]; + long long operations = (long long)(idx - prev[idx]) * (next[idx] - idx); + if (operations > k) + operations = k; + ans = (ans * mod_pow(num, operations, mod)) % mod; + k -= operations; + if (!k) + break; + } + free(score); + free(next); + free(prev); + free(stack); + free(indices); + return ans; +} + +int main() { + int n1[] = {8, 3, 9, 3, 8}, n2[] = {19, 12, 14, 6, 10, 18}; + printf("%d\n", maximumScore(n1, ARRAY_SIZE(n1), 2)); // expect: 81 + printf("%d\n", maximumScore(n2, ARRAY_SIZE(n2), 3)); // expect: 4788 +} 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)) |