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