
//-------------------------------------------------------------
// (Minimum) Set Cover
//   NP-complete
//
// Consider using SetCoverEasy, when mask is downward closed.
//
// Verified by
//   - SRM345 Div1 LV3
//-------------------------------------------------------------

LL next_combination(LL p)
{
	LL lsb = p & -p;
	LL rem = p + lsb;
	LL rit = rem & ~p;
	return rem|(((rit/lsb)>>1)-1);
}

// Is it possible to cover the goal by at most k elements from mask?
// Assumption:  goal \subseteq \bigcup mask
bool canCover( LL goal, set<LL>& mask, int k )
{
	// optimizer
	for(bool update=true; update; ) {
		update = false;

		// if *it \subseteq *jt for some jt, then we NEVER use it
		// if *it is the only mask covering some city, we ALWAYS use it
		for(set<LL>::iterator it=mask.begin(); it!=mask.end(); ) {
			bool isSubset = false;
			LL   onlyByMe = *it & goal;
			for(set<LL>::iterator jt=mask.begin(); jt!=mask.end(); ++jt)
				if( it!=jt ) {
					onlyByMe &= ~*jt;
					isSubset |= (*it & *jt & goal) == (*it & goal);
				}

			update |= isSubset | !!onlyByMe;

			if( isSubset )
				mask.erase(it++);
			else if( onlyByMe ) {
				if( --k < 0 )
					return false;
				goal &= ~*it;
				mask.erase(it++);
			}
			else
				++it;
		}

		if( mask.size()<=k || goal==0 )
			return true;
	}

	// exhaustive search
	vector<LL> ms(mask.begin(), mask.end());
	for(LL i=(1LL<<k)-1; i<(1LL<<ms.size()); i=next_combination(i))
	{
		LL gg = goal;
		for(LL j=0; (1LL<<j)<=i; ++j)
			if( i & (1<<j) )
				gg &= ~ms[j];
		if( gg == 0 )
			return true;
	}
	return false;
}
