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!