12083 - Guardian of Decency

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

12083 - Guardian of Decency

Post by vsha041 » Sat Apr 26, 2014 1:04 pm

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
New poster
Posts: 16
Joined: Sun Jan 25, 2015 5:46 pm

Re: 12083 - Guardian of Decency

Post by fsps60312 » Tue Mar 24, 2015 2:57 am

vsha041 wrote: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
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 12083 - Guardian of Decency

Post by Repon kumar Roy » Thu Jun 25, 2015 1:29 pm

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;
}

Post Reply

Return to “Volume 120 (12000-12099)”