Hi Code Forces Fellows,

Found a very interesting and challenging problem while reading a blog post. Originally, this problem (F) was a part of the timus contest.

I can't solve it and it keeps me awake at night...

As I understand, we need to find the number of **complete** and **unique** subgraphs (subsets of robots that are all friends). Suppose we have two groups of robots that are friends to each other:

`{1, 2, 3}`

`{2, 3, 4}`

So, the possible unique subsets are:

`{1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {2, 4}, {3, 4}, {2, 3, 4}`

And the answer will be `12`

in this case, on the 12th day we will be out of possible unique combinations.

My silly brute force solution gives a TLE on the 4th test case, of course, and I don't understand how to implement this idea efficiently.

Could somebody please help me with solution?

Thanks!

Maybe, just maybe, try calculating all possible subsets then minus the ones that aren't unique.

This problem can be solved using Meet in the Middle and Bitmasks DP. The algorithm is quite similar to the one where you have to find the maximum complete subgraph, which is explained on problem 839E - Мать драконов.

Thank you for pointing out this interesting idea and algorithm, I will try to get familiar with it and implement.