OPyrohov's blog

By OPyrohov, 13 months ago, In English

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?


Read more »

  • Vote: I like it
  • +34
  • Vote: I do not like it