Crossfade Rehearsal Orders
Minimum cost and optimal permutation count given a matrix and precedence
A music streaming team is rehearsing a sequence of preview tracks. Every track must appear exactly once, but the order has not been chosen.
Tracks are numbered from 0 to n - 1, where n is the number of rows in fees. If track i is immediately followed by track j, the crossfade contributes fees[i][j] to the rehearsal's total fee. A negative fee represents a credit. There is no fee before the first track or after the last track, and the sequence does not wrap around.
Each pair [a, b] in before requires track a to appear somewhere before track b; they do not need to be consecutive. All requirements must be satisfied. Requirements may conflict, making a rehearsal impossible.
Return a two-element list:
- The minimum total fee among all valid track orders.
- The number of distinct track orders attaining that minimum, modulo 1,000,000,007.
Two orders are distinct if their sequences of track indices differ, even when some fees are equal. If no valid order exists, return [-1, 0].
Examples
Example 1
Input: fees = [[0,1,1],[1,0,1],[1,1,0]], before = [[0,2]] Output: [2,3]
The requirement places track 0 before track 2. Every valid order has two transitions, each with fee 1, so all valid orders attain the same minimum.
Example 2
Input: fees = [[0,2,9],[8,0,1],[3,6,0]], before = [] Output: [3,1]
There are no ordering requirements. Playing tracks 0, 1, and 2 in that order uses the inexpensive directed transitions from 0 to 1 and from 1 to 2. Every other order has a larger total fee.
Example 3
Input: fees = [[0,4],[7,0]], before = [[0,1],[1,0]] Output: [-1,0]
Each track is required to precede the other. No order can satisfy both requirements.
Constraints
- 1 <= n <= 16
- fees is an n by n integer matrix.
- -1,000,000 <= fees[i][j] <= 1,000,000
- fees[i][i] = 0
- 0 <= before.length <= n * (n - 1)
- Each element of before is a pair [a, b] with 0 <= a, b < n and a != b.
- The pairs in before are distinct.
The intended algorithm uses O(n^2 * 2^n) time and O(n * 2^n) space. Fees are directed: fees[i][j] need not equal fees[j][i]. Negative fees are safe because every transition adds a previously unplayed track.
Hints
Show hint 1Hint 1
A partial order can be summarized by the set of tracks already played and the index of the last track.
Show hint 2Hint 2
For each state, store both its least fee and the number of ways to attain that fee. A track can be appended only after all of its required predecessors have been played.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also reconstruct the lexicographically smallest optimal track order?
- How would the state and initialization change if exactly one chosen track could be omitted?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem