4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // (Minimum) Set Cover
4fd800b3a8 2011-02-23        kinaba: //   NP-complete
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Assumption: "mask" must be downward closerd,
4fd800b3a8 2011-02-23        kinaba: //   i.e., X subset Y & Y in mask => X in mask
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - Google Code Jam 09 Round2 C
4fd800b3a8 2011-02-23        kinaba: //     (The "Only" part never tested, in the test cases of
4fd800b3a8 2011-02-23        kinaba: //      the problem, that optimization had never used.
4fd800b3a8 2011-02-23        kinaba: //      Be careful to use that; to be on the safer side,
4fd800b3a8 2011-02-23        kinaba: //      consider using the <true,false> mode.)
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: int minCover_exhaustive( int goal, const set<int>& mask )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	typedef int STATE;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	vector<STATE> Q( 1, 0 );
4fd800b3a8 2011-02-23        kinaba: 	set<STATE> visited;
4fd800b3a8 2011-02-23        kinaba: 	for(int step=0; step<=mask.size(); ++step)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		vector<STATE> Q2;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<Q.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			STATE s = Q[i];
4fd800b3a8 2011-02-23        kinaba: 			if( s == goal )
4fd800b3a8 2011-02-23        kinaba: 				return step;
4fd800b3a8 2011-02-23        kinaba: 			for(set<int>::const_iterator it=mask.begin(); it!=mask.end(); ++it)
4fd800b3a8 2011-02-23        kinaba: 				if( !visited.count( s|*it ) )
4fd800b3a8 2011-02-23        kinaba: 				{
4fd800b3a8 2011-02-23        kinaba: 					visited.insert( s|*it );
4fd800b3a8 2011-02-23        kinaba: 					Q2.push_back( s|*it );
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		Q.swap(Q2);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return -1;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<bool Subs, bool Only>
4fd800b3a8 2011-02-23        kinaba: int minCover( int goal, set<int> mask )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	if( Subs )
4fd800b3a8 2011-02-23        kinaba: 		for(set<int>::iterator it=mask.begin(); it!=mask.end(); )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			bool needed = true;
4fd800b3a8 2011-02-23        kinaba: 			for(int m=1; m<=goal; m<<=1)
4fd800b3a8 2011-02-23        kinaba: 				if( (goal&m) && !(*it&m) && mask.count(*it|m))
4fd800b3a8 2011-02-23        kinaba: 					{needed = false; break;}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			if( needed )
4fd800b3a8 2011-02-23        kinaba: 				++it;
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 				mask.erase(it++);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	if( Only )
4fd800b3a8 2011-02-23        kinaba: 		for(set<int>::iterator it=mask.begin(); it!=mask.end(); )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int onlyByMe = goal & *it;
4fd800b3a8 2011-02-23        kinaba: 			for(set<int>::iterator jt=mask.begin(); jt!=mask.end(); ++jt)
4fd800b3a8 2011-02-23        kinaba: 				onlyByMe &= ~*jt;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			if( !onlyByMe )
4fd800b3a8 2011-02-23        kinaba: 				++it;
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 				mask.erase(it++), goal &= ~onlyByMe;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	return minCover_exhaustive(goal, mask);
4fd800b3a8 2011-02-23        kinaba: }