PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a number of videos, and under a certain conditions, find the number of playlists that can be formed.
EXPLANATION:
Let’s divide the number of videos into two parts, first which have been played(M) and second which have not been played(N).
At each moment of creating the playlist you can do one of two things.
If length(N) > 0, choose any videos from group N and play it. After this, move the videos from N to M.
If len(M) > B, choose any of the (len(M)-B) videos from group B that are not violating the Isolation rule and play it.
Pseudo code :-
function playlist(position,len(M),len(N))
result = 0;
if (len(N) > 0)
result += playlist(position+1, len(M)+1, len(N)-1) * len(N);
if (len(M) > B)
result += playlist(position+1, len(M), len(N)) * (len(M)-B);
return result % MOD;