Hello, everyone!

I have just brushed off my Subset Dynamic Programming knowledge by solving the problem Marbles (Div.2 E) from Round #585.

Very nice problem and a perfect example of how this technique comes into play when you need to try out each possible permutation or combination of elements in order to find an optimal one.

Rite of passage:

1. n is really big, buuuut.. why are there only 20 different colours? Should be backtracking or Subset Dynamic Programming!

2. Each possible solution corresponds to a permutation of these 20 colors. Usually, if I find a brute force approach which tries each possible permutation, I'm pretty confident I can use Subset Dynamic Programming to reduce the time complexity from O(k!) to O(2^k) or maybe O(2^k * k).

3. Looks like the mask is going to represent the subset of colors I have added into my permutation.

4. At each step, I will find a color which was not added yet and I update the subset containing this subset and this new color.

5. I can do this, awesome! But I need one more precompution before that...

Here is the link to my video tutorial: Codeforces Problem — Marbles ( Subset Dynamic Programming )