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: // Consider using SetCoverEasy, when mask is downward closed.
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - SRM345 Div1 LV3
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: LL next_combination(LL p)
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	LL lsb = p & -p;
4fd800b3a8 2011-02-23        kinaba: 	LL rem = p + lsb;
4fd800b3a8 2011-02-23        kinaba: 	LL rit = rem & ~p;
4fd800b3a8 2011-02-23        kinaba: 	return rem|(((rit/lsb)>>1)-1);
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // Is it possible to cover the goal by at most k elements from mask?
4fd800b3a8 2011-02-23        kinaba: // Assumption:  goal \subseteq \bigcup mask
4fd800b3a8 2011-02-23        kinaba: bool canCover( LL goal, set<LL>& mask, int k )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	// optimizer
4fd800b3a8 2011-02-23        kinaba: 	for(bool update=true; update; ) {
4fd800b3a8 2011-02-23        kinaba: 		update = false;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// if *it \subseteq *jt for some jt, then we NEVER use it
4fd800b3a8 2011-02-23        kinaba: 		// if *it is the only mask covering some city, we ALWAYS use it
4fd800b3a8 2011-02-23        kinaba: 		for(set<LL>::iterator it=mask.begin(); it!=mask.end(); ) {
4fd800b3a8 2011-02-23        kinaba: 			bool isSubset = false;
4fd800b3a8 2011-02-23        kinaba: 			LL   onlyByMe = *it & goal;
4fd800b3a8 2011-02-23        kinaba: 			for(set<LL>::iterator jt=mask.begin(); jt!=mask.end(); ++jt)
4fd800b3a8 2011-02-23        kinaba: 				if( it!=jt ) {
4fd800b3a8 2011-02-23        kinaba: 					onlyByMe &= ~*jt;
4fd800b3a8 2011-02-23        kinaba: 					isSubset |= (*it & *jt & goal) == (*it & goal);
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			update |= isSubset | !!onlyByMe;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			if( isSubset )
4fd800b3a8 2011-02-23        kinaba: 				mask.erase(it++);
4fd800b3a8 2011-02-23        kinaba: 			else if( onlyByMe ) {
4fd800b3a8 2011-02-23        kinaba: 				if( --k < 0 )
4fd800b3a8 2011-02-23        kinaba: 					return false;
4fd800b3a8 2011-02-23        kinaba: 				goal &= ~*it;
4fd800b3a8 2011-02-23        kinaba: 				mask.erase(it++);
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 				++it;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		if( mask.size()<=k || goal==0 )
4fd800b3a8 2011-02-23        kinaba: 			return true;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	// exhaustive search
4fd800b3a8 2011-02-23        kinaba: 	vector<LL> ms(mask.begin(), mask.end());
4fd800b3a8 2011-02-23        kinaba: 	for(LL i=(1LL<<k)-1; i<(1LL<<ms.size()); i=next_combination(i))
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		LL gg = goal;
4fd800b3a8 2011-02-23        kinaba: 		for(LL j=0; (1LL<<j)<=i; ++j)
4fd800b3a8 2011-02-23        kinaba: 			if( i & (1<<j) )
4fd800b3a8 2011-02-23        kinaba: 				gg &= ~ms[j];
4fd800b3a8 2011-02-23        kinaba: 		if( gg == 0 )
4fd800b3a8 2011-02-23        kinaba: 			return true;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return false;
4fd800b3a8 2011-02-23        kinaba: }