Looking for hints to solve this dynamic programming problem

Question

I am trying to improve my problem solving skills for programming interviews and am trying to solve this problem. I have a feeling it can be solved using dynamic programming but the recursive relationship is not obvious to me.

To select the first three choir singers I simply use brute force. Since there are only 20 Choose 3 = 1140 ways to pick them. At first I thought dp[a][b][c] could represent the shortest song with three choir singers with remaining breath a, b, c. If I could calculate this using dp[a][b][c] = 1 + dp[a - 1][b - 1][c - 1], but what should be done when any of the indices equal 0, which choir singer should be substituted in. Additionally, we cannot reuse the dp array, because say in one instance we start with choir singers with breath a, b, c and in the second instance d, e, f. Once the first instance has been calculated and the dp array filled; the second instance may need to use dp[i][j][k] computed by the first instance. Since this value depends on the available choir singers in the first instance, and the available singers in both instances are not the same, dp[i][j][k] may not be possible in the second instance. This is because the shortest song length dp[i][j][k] may use choir singers which in the second instance are already being used.

I am out of ideas to tackle this problem and there is no solution anywhere. Could someone give me some hints to solve it?

Problem statement

We have N singers, who each have a certain time they can sing for and need 1 second to recover once out of breath. What is the minimum song they can sing, where three singers are singing at all times and where they all three finish singing simultaneously?

Input:

Input 3 < N <= 20 N integers Fi (1 <= Fi <= 10, for all 1 <= i <= N)

Answer 1

The state in terms of memoisation seems unrelated to the time elapsed since the start. Take any starting position,

a, b, c

where a, b, c are chosen magnitudes (how long each singer can hold their breath), and a is the smallest magnitude. We have

a, b, c
t = 0

and it's the same as:

0, b - a, c - a
t = a

So let's define the initial state with smallest magnitude a as:

b, c, ba, ca
  where ba = b - a
        ca = c - a
t = a

From here, every transition of the state is similar:

new_a <- x
  where x is a magnitude in
  the list that can be available
  together with b and c. (We only
  need to try each such unique
  magnitude once during this
  iteration. We must also prevent
  a singer from repeating.)

  let m = min(new_a, ba, ca)

  then the new state is:
    u, v, um, vm
    t = t + m
      where u and v are from the
      elements of [new_a, b, c] that
      aren't associated with m, and um
      and vm are their pairs from
      [new_a, ba, ca] that aren't m,
      subtracted by m.

The state for memoisation of visited combinations can be only:

[(b, ba), (c, ca)] sorted by
the tuples' first element

with which we can prune a branch in the search if the associated t that is reached is equal or higher to the minimal one seen for that state.

Example:

2 4 7 6 5

Solution (read top-down):

4 5 6
7 4 5
  2

States:

u v um vm
5 6 1 2
t = 4

new_a = 7
m = min(7, 1, 2) = 1 (associated with 5)
7 6 6 1
t = 5

new_a = 4
m = min(4, 6, 1) = 1 (associated with 6)
4 7 3 5
t = 6

new_a = 5
m = min(5, 3, 5) = 3 (associated with 4)
5 7 2 2
t = 9

new_a = 2
m = min(2, 2, 2) = 2 (associated with 2)
5 7 0 0
t = 11

Python code:

import heapq
from itertools import combinations

def f(A):
  mag_counts = {}

  for x in A:
    if x in mag_counts:
      mag_counts[x] = mag_counts[x] + 1
    else:
      mag_counts[x] = 1

  q = []

  seen = set()

  # Initialise the queue with unique starting combinations
  for comb in combinations(A, 3):
    sorted_comb = tuple(sorted(comb))
    if not sorted_comb in seen:
      (a, b, c) = sorted_comb
      heapq.heappush(q, (a, (b-a, b), (c-a, c), a))
    seen.add(sorted_comb)

  while q:
    (t, (ba, b), (ca, c), prev) = heapq.heappop(q)

    if ba == 0 and ca == 0:
      return t

    for mag in mag_counts.keys():
      # Check that the magnitude is available
      # and the same singer is not repeating.
      [three, two] = [3, 2] if mag != prev else [4, 3]
      if mag == b == c and mag_counts[mag] < three:
        continue
      elif mag == b and mag_counts[mag] < two:
        continue
      elif mag == c and mag_counts[mag] < two:
        continue
      elif mag == prev and mag_counts[mag] < 2:
        continue

      m = min(mag, ba, ca)

      if m == mag:
        heapq.heappush(q, (t + m, (ba-m, b), (ca-m, c), m))
      elif m == ba:
        heapq.heappush(q, (t + m, (mag-m, mag), (ca-m, c), b))
      else:
        heapq.heappush(q, (t + m, (mag-m, mag), (ba-m, b), c))

  return float('inf')

As = [
  [3, 2, 3, 3], # 3
  [1, 2, 3, 2, 4], # 3
  [2, 4, 7, 6, 5] # 11
]

for A in As:
  print A, f(A)

Answer 2

Here is the idea.

At each point in the singing, the current state can be represented by who the singers are, how long they have been singing, and which ones are currently out of breath. And from each state we need to transition to a new state, which is every singer out of breath is ready to sing again, every singer singing is good for one less turn, and new singers might be chosen.

Done naively, there are up to 20 choose 3 singers, each of which can be in 10 current states, plus up to 2 more who are out of breath. This is 175560000 combined states you can be in. That's too many, we need to be more clever to make this work.

Being more clever, we do not have 20 differentiable singers. We have 10 buckets of singers based on how long they can sing for. If a singer can sing for 7 turns, they can't be in 10 states if currently singing, but only 7. We do not care whether the two can sing for 7 turns are at 4 and 3 turns left or 3 and 4, they are the same. This introduces a lot of symmetries. Once we take care of all of the symmetries, that reduces the number of possible states that we might be in from hundreds of millions to (usually) tens of thousands.

And now we have a state transition for our DP which is dp[state1] to dp[state2]. The challenge being to produce a state representation that takes advantage of these symmetries that you can use as keys to your data structure.

UPDATE:

The main loop of the code would look like this Python:

while not finished:
    song_length += 1
    next_states = set()
    for state in current_states:
        for next_state in transitions(state):
            if is_finished(next_state):
                finished = True # Could break out of loops here
            else:
                next_states.add(next_state)
    current_states = next_states

Most of the challenge is a good representation of a state, and your transitions function.