Capable Models

Frequency: Reported

Given n machine-learning models, each model has a cost cost[i] and a two-character binary string featureAvailability[i] describing compatibility with two features:

"00": supports neither feature.
"01": supports feature A but not feature B.
"10": supports feature B but not feature A.
"11": supports both features.

A set of models is k-capable when at least k models in the set support feature A and at least k models in the set support feature B.

For each k from 1 through n, determine the minimum cost of a k-capable set. Return an array of n integers in which entry i is the minimum cost of an (i + 1)-capable set, or -1 if no such set exists.

Example

text

n = 6
cost = [3, 6, 9, 1, 2, 5]
featureAvailability = ["10", "01", "11", "01", "11", "10"]

Using the one-based model indices shown in the source:

`k`	Optimal set	Feature A compatible	Feature B compatible	Cost
1	`[5]`	`[5]`	`[5]`	`2`
2	`[1, 4, 5]`	`[1, 5]`	`[4, 5]`	`3 + 1 + 2 = 6`
3	`[1, 3, 4, 5]`	`[1, 3, 5]`	`[3, 4, 5]`	`3 + 9 + 1 + 2 = 15`
4	`[1, 2, 3, 4, 5, 6]`	`[1, 3, 5, 6]`	`[2, 3, 4, 5]`	`3 + 6 + 9 + 1 + 2 + 5 = 26`

For k >= 5, no capable set exists. Return:

text

[2, 6, 15, 26, -1, -1]

Function

python

def getMinimumCost(cost, featureAvailability):
    # Write your code here

Parameters:

int cost[n]: model costs.
string featureAvailability[n]: the compatibility strings.

Return int[n], where the ith integer is the minimum cost of an i-capable set, using the source's one-based description of i.

Constraints

text

1 <= n <= 10^5
1 <= cost[i] <= 10^4
featureAvailability[i] is a binary string of length 2

Sample case

text

cost = [5, 6, 10, 1]
featureAvailability = ["10", "01", "11", "00"]

Return:

text

[10, 21, -1, -1]

For k = 1, choose model 3, which supports both features and costs 10. For k = 2, choose models [1, 2, 3] for a total cost of 5 + 6 + 10 = 21. No capable set exists for k >= 3.