Lamest O(2^K) is enough here.

Act greedy.
At each iteration select such team X,  that if X in contest,  then the number of teams can't attend contest is minimal.
Remove such teams that have common members with X from the list.

5
1 2 a
4 b c
3 a b
5 c d
6 7 d

answer 3

LOL. That's interesting. Could you share code please?

That's because in Java objects like String pass by their links, when in C++ strings pass by their values(all chars). So when you move a string in Java you do less operations than you do in C++


Edited by author 24.04.2022 12:50

try this:
13
a b c
b c d
a e q
e r t
q f e
dd qw ff
aa f dd
e q f
dd ee mm
vv bb cc
pp ii uu
pp a d
d e q

ans: 5

It's possible to solve that problem with only 32-bit masks. Encode team number k as  2^k (in c "1 << k", in pascal "1 shl k").

Create an array (I named it "check"):

forall (i)
{
  check[i] = 0;
  forall (j, not equal i)
  {
    if (there is a member in team j that exists also in team i)
      then check[i] = check[i] bitwise or (2 ^ j);
  }
}

You can encode every possible teams combination in one number from interval [0 .. (2^k) - 1]. Note that the number is less than 2 ^ 18 (or 262144).

Then enumerate all numbers from that interval and for every number S for every bit p in position q in number S check inequality "S & check[q] > 0".

If for some p in position q in number S this inequality is true, than state S is inacceptable.

Edited by author 23.09.2011 01:18

There were no EOLN characters in the end of some tests. Now your first approach is AC too.

Yes, this problem is NP-hard.

I find that if we are allowed to create groups by changing members then in the example cited we must get answer as 5 instead of 4.But it is not so. can anybody please explain?