12083 - Guardian of Decency

[vsha041]

This is an interesting MIS problem (Maximum Independent Set). You can create a bipartite graph between men and women. Connect men to all those women whose height difference with men is <= 40 and music is different and sport is the same (3 conditions). After that just use the MCBM algorithm to get the vertex cover. Subtract this from total number of people to get the answer.

MCBM Algorithm - http://www.geeksforgeeks.org/maximum-bi ... -matching/

For the first sample input the graph will look like this

m0 -
m1 - w0
m2 - w0

Size of vertex cover is 1 and MIS = 4 - 1 = 3

For the second sample input the graph will look like this

m0 - w1
m1 -
m2 -
m3 -
m4 -
m5 -

Size of vertex cover is 1 and MIS = 8 - 1 = 7

[fsps60312]

This is an interesting MIS problem (Maximum Independent Set). You can create a bipartite graph between men and women. Connect men to all those women whose height difference with men is <= 40 and music is different and sport is the same (3 conditions). After that just use the MCBM algorithm to get the vertex cover. Subtract this from total number of people to get the answer.

MCBM Algorithm - http://www.geeksforgeeks.org/maximum-bi ... -matching/

For the first sample input the graph will look like this

m0 -
m1 - w0
m2 - w0

Size of vertex cover is 1 and MIS = 4 - 1 = 3

For the second sample input the graph will look like this

m0 - w1
m1 -
m2 -
m3 -
m4 -
m5 -

Size of vertex cover is 1 and MIS = 8 - 1 = 7

I think it should be "music is the same and sport is different"

[Repon kumar Roy]

Getting WA . Why ??
Using MCBM to find MIS..

Code: Select all

//
//  main.cpp
//  12083 - Guardian of Decency
//
//  Created by Repon Macbook on 6/25/15.
//  Copyright (c) 2015 Repon Macbook. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				505
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define debug(x)              cout <<#x <<" -> " << x << endl;
#define EPS				1e-7
#define fred()                 freopen("in.txt","r",stdin);
#define fwrt()               freopen("in.txt","w",stdout);


/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

map<string, int> lm ;
map<string, int> sm;
vi EdgeList[LMT];

struct Person {
      int h , music , sport;
};

vector<Person> Male , Female;

char mus[103] , sp[103] ;

int S[LMT] , T[LMT] , P[LMT];

bool isLove ( int i , int j )
{
      
      if( abs(Male[i].h - Female[j].h ) <= 40 && Male[i].music == Female[j].music && Male[i].sport != Female[j].sport ) {
            return true;
      }
      return false;
}


bool dfs( int s)
{
      S[s] = 1;
      for( int i = 0; i < EdgeList[s].size() ; i ++ ) {
            int v = EdgeList[s][i] ;
            if( T[v] == 0 ){
                  T[v] = 1;
                  if( P[v] == -1 || dfs(v)) {
                        P[v] = s;
                        return true;
                  }
            }
      }
      return false;
}


int bmp ( int n)
{
      int r = 0;
      ms(P , -1);
      for( int i =0 ; i < n ;i ++ ) {
            ms(S, 0);
            ms(T , 0);
            if( dfs(i)) r ++;
      }
      return r;
}
int main()
{
      
      int tc , h ;
      int n ;
      sc(tc);
      
      char sx;
      while (tc-- ) {
            sc(n);
            int cn1 = 0, cn2 = 0;
            for (int i = 0; i < n ; i ++) {
                  scanf("%d %c %s %s" , &h , &sx , mus , sp);
                  
                  if( lm.count(mus) == 0) lm[mus] = ++cn1;
                  if( sm.count(sp) == 0 )sm[sp] = ++ cn2;
                  
                  
                  if( sx == 'M' )Male.push_back( {h,lm[mus] , sm[sp]} );
                  
                  else Female.push_back( {h,lm[mus] , sm[sp]} );
                  
            }
            
            for( int i =0 ; i < Male.size()  ; i ++ ) {
                  for( int j = 0; j < Female.size() ; j ++ ) {
                        if( isLove ( i , j )) {
                              EdgeList[i].pb( j );
                        }
                  }
            }
            
            int p = bmp ( (int ) Male.size()) ;
            
            printf("%d\n" , n - p );
            
            for( int i = 0 ;i  < Male.size() ;i ++) EdgeList[i].clear();
            Male.clear();
            Female.clear();
            lm.clear();
            sm.clear();
      }
      return 0;
}