Trigger the chutes and protect the jackpot

Question

You are going to participate in a gameshow. One of the challenges works as follows:

• The first room contains a large number of identical balls.
• The second room contains a series of chutes, each of which has a sensor which counts how many balls have been placed in it. A ball which is placed in a chute cannot then be recovered.
• Each chute will trigger after a certain number of balls (its trigger count) have been placed into it. When it triggers it flashes lights, makes a noise, and leaves you in no doubt that it has triggered.
• You must trigger N chutes to continue to the next challenge.
• You know the trigger counts, but not the correspondence between count and chute.
• You have one opportunity to take balls from the first room into the second. Once you put a ball into a chute, you cannot go back for more balls.
• Each ball which you take deducts money from the jackpot.

Obviously you want to ensure that you will pass the challenge, but you want to minimise the jackpot money loss. Write a program, function, verb, etc. to tell you how many balls you need.

Example

Suppose the trigger counts are 2, 4, and 10, and you need to trigger 2 chutes to pass. There is a strategy to pass with 10 balls: place up to 4 balls in the first chute, up to 4 balls in the second chute, and up to 4 balls in the third chute. Since one of the three chutes will trigger after only 2 balls, you only use a total of 10. There is no strategy which is guaranteed to work with fewer than 10, so that is the correct output.

Input

The input consists of an array of integer trigger counts and a integer giving the number of chutes to trigger. You may take the two inputs in either order, and if needed you may take a third input with the length of the array.

You may assume that all of the inputs are greater than zero, and that the number of chutes which must be triggered does not exceed the number of chutes.

You may also assume that the counts are sorted (ascending or descending), as long as you state that clearly in your answer.

Output

The output should be a single integer, giving the number of balls required by the optimum strategy.

Test cases

Format: N counts solution

1 [2 4 10] 6
2 [2 4 10] 10
3 [2 4 10] 16
1 [3 5 5 5 5 5 5 5 5 5] 5
2 [1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 8 11] 8
2 [1 2 6 6 6 6 6 6 6 10] 16
2 [1 2 3 3 4 4 6 6 6 11] 17
3 [1 2 3 4 5 5 6] 16
3 [2 4 7 7 7 7 7 7 7] 21
5 [1 2 2 3 3 3 3 3 5 9 9 11] 27
2 [5 15 15] 25
1 [4 5 15] 10
3 [1 4 4 4] 10
2 [1 3 4] 6
2 [1 3 3 8] 8

Answer 1

Python, 222 198 bytes

def S(G,P,T=0):
 T=T or[0]*len(P);r=[0]*(sum(t>=p for t,p in zip(T,P))>=G)
 for i,t in enumerate(T):
    if t<max(P):a=next(p for p in P if p>t)-t;T[i]+=a;r+=[a+S(G,P,sorted(T))];T[i]-=a
 return min(r)

Usage is S(2, (2, 4, 10)).

In order to test this program at any decent speed, add memoization by putting this after the function definition:

old_s = S
mem = {}
def S(G, P, T=0):
    k = (G, tuple(P), T and tuple(T) or 0)
    if k in mem: return mem[k]
    r = old_s(G, P, T)
    mem[k] = r
    return r

---

We do dynamic programming on an array T that contains the number of balls we've thrown into each chute, initially all zeroes. Without providing a rigorous proof, I claim that we can keep T sorted at all times, that is, assume we always throw the most balls into the last chute, which in turn we will assume was the largest chute.

If then T, when matched element for element with P (which is our problem input), has at least G (which is our goal) elements bigger, we've found a solution, and we return 0, because we need to throw 0 more balls to find a solution. This means that if G is 1 our least thrown into chute must contain an equal or more amount of balls than the smallest chute requirement, and so on for bigger G.

Otherwise, for each position we throw in enough balls to upgrade to the next chute requirement (anything in between would never be observable) and recurse. We then return the minimum of these recursive calls.

Answer 2

Haskell, 124 117 100 98 91 80 78 bytes

Saved 11 bytes thanks to @Peter Taylor

0#_=0
n#a=minimum$zipWith(\x y->x*y+(n-1)#(snd.splitAt y$a))a[1..length a-n+1]

Try it online!

(#) takes an integer and a list of integers in descending order as arguments

Usage is 1#[10,4,2]

Explaination:

For each value, x, in position i (1-idexed) in the list, the best tactic to remove that element (or some amount of elements less than or equal to x) is to pour x balls into i chutes.

For each element, x, in position i in the list, (n#) calculates x*i + ((n-1)#) of the list beyond position i (until n is 0). Then it takes the minimum of all the possibilities checked.

Answer 3

Haskell, 54 bytes

(%)0
(p%l)n|h:t<-l=p+min(p%t$n)(h%t$n-1)|n<1=p|1>0=1/0

Try it online!

Takes the list in ascending order.

Answer 4

Python, 73 bytes

f=lambda n,c:n and min(c[i]*-~i+f(n-1,c[-~i:])for i in range(len(c)-n+1))

Port of H.PWiz's Haskell answer. Requires the input to be in descending order.

Answer 5

CJam (35 bytes)

{:A,,e!f<{$__(;A,+.-\Af=.*1bz}%:e<}

Online demo

Takes input as N counts assuming that counts is sorted in ascending order.

Dissection

Denote the counts in descending order as a 1-indexed array C (so the second element of C is the second largest count). Suppose that we end up winning by triggering chutes C[a_0], C[a_1], ... C[a_{N-1}]. Then in the worst case, for each C[a_i] we have put at least C[a_i] balls into each of chutes 1 to a_i. So we put C[a_{N-1}] balls into a_{N-1} chutes, an additional C[a_{N-2}] balls into a_{N-2} of them, ...

Over each subset of N counts, which gives us the smallest sum? Then we should aim to win with that subset of counts.

NB The code actually uses the counts in ascending order, but I think descending order is more intuitive.

{         e# Define a block
  :A      e#   Store the sorted counts as A
  ,,e!f<  e#   Get all N-element subsets of A's indices
  {       e#   Map over these subsets S:
    $__   e#     Sort the subset and get a couple of copies
    (;A,+ e#     Remove the first element from one copy and append len(A)
    .-    e#     Pointwise subtraction, giving [S[0]-S[1] S[1]-S[2] ...]
    \Af=  e#     Get the counts [A[S[0]] A[S[1]] ...]
    .*    e#     Pointwise multiplication
    1bz   e#     Sum and take absolute value, giving the worst case score
  }%
  :e<     e#   Select the minimum worst case score
}