Artifact d2930c13625ebb9212dca232b7282a48d8458bb6

• File _lib/typical/setCoverEasy.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/typical/setCoverEasy.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// (Minimum) Set Cover
//   NP-complete
//
// Assumption: "mask" must be downward closerd,
//   i.e., X subset Y & Y in mask => X in mask
//
// Verified by
//   - Google Code Jam 09 Round2 C
//     (The "Only" part never tested, in the test cases of
//      the problem, that optimization had never used.
//      Be careful to use that; to be on the safer side,
//      consider using the <true,false> mode.)
//-------------------------------------------------------------

int minCover_exhaustive( int goal, const set<int>& mask )
{
	typedef int STATE;

	vector<STATE> Q( 1, 0 );
	set<STATE> visited;
	for(int step=0; step<=mask.size(); ++step)
	{
		vector<STATE> Q2;
		for(int i=0; i<Q.size(); ++i)
		{
			STATE s = Q[i];
			if( s == goal )
				return step;
			for(set<int>::const_iterator it=mask.begin(); it!=mask.end(); ++it)
				if( !visited.count( s|*it ) )
				{
					visited.insert( s|*it );
					Q2.push_back( s|*it );
				}
		}
		Q.swap(Q2);
	}
	return -1;
}

template<bool Subs, bool Only>
int minCover( int goal, set<int> mask )
{
	if( Subs )
		for(set<int>::iterator it=mask.begin(); it!=mask.end(); )
		{
			bool needed = true;
			for(int m=1; m<=goal; m<<=1)
				if( (goal&m) && !(*it&m) && mask.count(*it|m))
					{needed = false; break;}

			if( needed )
				++it;
			else
				mask.erase(it++);
		}

	if( Only )
		for(set<int>::iterator it=mask.begin(); it!=mask.end(); )
		{
			int onlyByMe = goal & *it;
			for(set<int>::iterator jt=mask.begin(); jt!=mask.end(); ++jt)
				onlyByMe &= ~*jt;
	
			if( !onlyByMe )
				++it;
			else
				mask.erase(it++), goal &= ~onlyByMe;
		}

	return minCover_exhaustive(goal, mask);
}