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:**

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

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).

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

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.

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 )