Problem statement

https://binarysearch.com/problems/Weekly-Contest/

Solution

First of all notice, that if we take tasks in order (i, j, k) and in order (j, i, k), then we will get better score for the case where points_i > points_j - we can do math and see this. It means, that it is always optimal to take first tasks with bigger points (I denote them by x and chances denoted by p). No, let us consider dp(i, taken) state, where we work with [i, n-1] tasks, task i is taken and also in total we already tried to solve taken tasks.

Then we have \(dp(i, taken) = \max\limits_{i < j \leqslant n} p_i \cdot x_i + (1-p_i) \cdot dp(j, taken - 1)\)

It total we have O(n * k) states with O(n) time to compute state, which is not enough to pass. However we can also calculate accumulate maximum of suffixes, which will lead to total O(n * k) time.

Complexity

Time complexity is O(n * k) as well as space.

Code

class Solution:
    def solve(self, points, chances, k):
        xp = sorted((x, p/100) for x, p in zip(points, chances))[::-1]
        n = len(xp)

        @lru_cache(None)
        def dp(i, taken):
            if taken == 0: return 0
            if i == n: return -float("inf")
            return xp[i][0]*xp[i][1] + (1 - xp[i][1]) * mp(i + 1, taken - 1)

        @lru_cache(None)
        def mp(i, taken):
            if i == n: return 0
            return max(mp(i + 1, taken), dp(i, taken))

        return max([int(dp(i, k)) for i in range(n-k+1)] or [0])

Code 2

In fact it can be written in shorter way if we define state dp(i, taken) as [i, n-1] tasks, (task i can be taken or not taken) and also in total we already tried to solve taken` tasks. Complexity is the same.

class Solution:
    def solve(self, points, chances, k):
        xp = sorted((x, p/100) for x, p in zip(points, chances))[::-1]
        n = len(xp)

        @lru_cache(None)
        def dp(i, k):
            if k == 0 or i == n: return 0
            x, p = xp[i]
            return max(x*p + dp(i + 1, k - 1) * (1 - p), dp(i + 1, k))

        return int(dp(0, k))