OPyrohov's blog

I can't solve this problem (looking for ideas/solutions) ...
By OPyrohov, 4 years 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?

Thanks!

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

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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 - Mother of Dragons.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply