DP part - 3

DP নিয়ে আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে ।

এই পোস্টেও কিছু interesting bitmask dp problem নিয়ে লিখার ইচ্ছা আছে ।

Can You win ?

এইখানে বলা হইছে তুমি তোমার বোনের সাথে  দাবা খেলতেছ কিন্তু খুব একটা পাত্তা পাইতেছ না ।তোমার শুধু মাত্র রাজা আর একটা ঘোড়া বাকি আছে ।   তোমার বোন তার প্রিয় " ‘panju muttai" খাইতে একটু বাহিরে গেছে , এই সুযোগ একটু দুই নাম্বারি করার । তুমি n টা মুভে যদি তোমার বোনের pawn ( 'p' small p , its important . this cause me 2/3 WA ) বাদে অন্য power ( capital 'P' ) খেয়ে ফেলতে পার তোমার ঘোড়া দিয়ে তুমি জিতবা । তোমারে দাবা বোর্ড এর কারেন্ট অবস্থা বলা হইছে তোমাকে বলতে হবে তুমি জিততে পারবা কি পারবা না ।

*** পাওয়ার এর সংখ্যা ১-৮ ( যখনই লিমিট কম থাকবে তখন আমাদের জন্য ভাল , আমরা একে bitmask এ ফালাইতে পারি না হয় state বাড়াইয়া দিতে পারি )

লিমিট কম তাই আমরা সহজেই bitmask করতে পারি । আমি 4টা state এ করছিলাম । কারণ x_position < 8 , y_position < 8 , maximum_move <= 64 , mask <= ( 1 << 8 ) । টোটাল ( 8 * 8 * 64 * ( 1 << 8 ) ) == 1048576 । প্রাথমিক ভাবে আমরা আমাদের ঘোড়ার পজিশন থেকে স্টার্ট করব । তারপর দেখব আমাদের যে মাক্সিমাম মুভ দেওয়া আছে এর মধ্যে আমরা সব গুলা পাওয়ারকে খেয়ে ফেলতে পারব কি না । যদি পারি তাইলে "Yes" না হবে "No" । এইখানে আমরা আমাদের কারেন্ট পজিশন থেকে যে সব পজিশনে পাওয়ার আছে তাতে কত মুভে যাওয়া যায় এইটা বের করার জন্য bfs() চালাব ।

	const int INF = 1 << 28 ;
	int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
	int vis[ 8 ][ 8 ][ 64 ][ ( 1 << 8 ) + 1 ] , cs ;
	bool dp[ 8 ][ 8 ][ 64 ][ ( 1 << 8 ) + 1 ] ;
	int dis[ 8 ][ 8 ];
	char grid[ 8 ][ 8 ];
	pii pawn[ 10 ] , me ;
	int tot ;
	bool ok( int x , int y )
	{
	if( x < 0 || x >= 8 || y < 0 || y >= 8 ) return 0 ;
	if( grid[x][y] == 'K' || grid[x][y] == 'p' ) return 0 ;
	return 1 ;
	}
	int bfs( int sx , int sy , int ddx , int ddy )
	{
	queue < pii > q ;
	queue < int > cost ;
	q.push( mp( sx , sy ) );
	cost.push( 0 );
	int i , j ;
	rep( i , 8 ) rep( j , 8 ) dis[i][j] = INF ;
	dis[sx][sy] = 0 ;
	while( !q.empty() )
	{
	int x = q.front().ff ;
	int y = q.front().ss ;
	int c = cost.front();
	cost.pop();
	q.pop();
	rep( i , 8 )
	{
	int nx = x + dx[i];
	int ny = y + dy[i];
	if( ok( nx , ny ) == 0 ) continue ;
	if( nx == ddx && ddy == ny )
	{
	return c + 1 ;
	}
	if( grid[nx][ny] == 'P') continue ;
	if( c + 1 < dis[nx][ny] )
	{
	dis[nx][ny] = c + 1 ;
	q.push( mp( nx , ny ) );
	cost.push( c + 1 );
	}
	}
	}
	return -1 ;
	}
	bool DP( int sx , int sy , int lft , int mask )
	{
	if( mask == ( 1 << tot ) - 1 ) return 1 ;
	int &v = vis[sx][sy][lft][mask];
	bool &ret = dp[sx][sy][lft][mask];
	if( v == cs ) return ret ;
	v = cs ;
	ret = 0 ;
	rep( i , tot )
	{
	if( mask & ( 1 << i ) ) continue ;
	pii go = pawn[i];
	int d = bfs( sx , sy , go.ff , go.ss );
	if( d !=-1 && d <= lft )
	{
	grid[go.ff][go.ss] = '.';
	bool tmp = DP( go.ff , go.ss , lft - d , mask | ( 1 << i ) );
	if( tmp == 1 ) return ret = 1 ;
	grid[ go.ff ][go.ss] = 'P';
	}
	}
	return ret ;
	}
	int main()
	{
	int t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	int n = II ;
	rep( i , 8 ) scanf("%s",grid[i]);
	rep( i , 8 ) rep( j , 8 )
	if( grid[i][j] == 'k' )
	{
	me = mp( i , j );
	break ;
	}
	tot = 0 ;
	rep( i , 8 ) rep( j , 8 )
	{
	if( grid[i][j] == 'P')
	{
	pawn[tot].ff = i ;
	pawn[tot++].ss = j ;
	}
	}
	if( DP( me.ff , me.ss , n , 0 ) ) printf("Yes\n");
	else printf("No\n");
	}
	return 0;
	}

view raw dp31.cpp hosted with ❤ by GitHub

Headmaster's Headache :

এই প্রবলেমটা অনেক ভাল কিন্তু বিরক্তিকর ইনপুট এর প্রবলেম । এই প্রবলেম এ বলা হইছে একজন হেড মাস্টার তার স্কুল এর জন্য কিছু শিক্ষক নিয়োগ এর আবেদন পেয়েছেন , যা থেকে তিনি কাউকে কাউকে নিয়োগ দিতে পারেন । স্কুল এ n টা সাবজেক্ট পড়ানো হয় । হেড স্যার চান যেন সব সাবজেক্ট এ কমপক্ষে দুইজন টিচার থাকেন , স্কুল এ কিছু পারমানেন্ট টিচার আছেন যাদের নিদিষ্ট বেতন দেওয়া হয় এবং তারা কিছু নিদিষ্ট সাবজেক্ট পড়ায় । এখন নতুন আবেদন করা শিক্ষকদের নিয়ে বা না নিয়ে হেড স্যার কিভাবে বিদ্যালয়ের খরচ ( মানে শিক্ষকদের বেতন দিতে পারেন , এইখানে বলে রাখা ভাল যারা পারমানেন্ট তারা অবশ্যই থাকবেন ) মিনিমাম করতে পারেন যেন অবশ্যই প্রতিটা সাবজেক্ট এ কমপক্ষে দুইজন টিচার থাকে ।

এইখানে সাবজেক্ট সর্বমোট থাকতে পারে ৮টা , লিমিট যেহেতু অনেক কম তাই আমরা এই প্রবলেমটাকে bitmask করতে পারি । এখন আমাদের state কয়েকটা হবে । যেহেতু পারমানেন্ট টিচার অবশ্যই থাকবে এইটা আমাদের বিবেচনার ব্যাপার না । আমাদের বিবেচনার ব্যাপার যারা আবেদন করেছেন । অবশ্যই একটা state হইল যারা আবেদন করেছেন তাদের সংখ্যা ( সর্বমোট ১০০ জন আবেদন করতে পারেন ) । এখন  প্রতিটা সাবজেক্ট দুইজন করে টিচার পড়াবে যা বুঝার জন্য আমরা দুইটা mask রাখতে পারি । mask1 এর কোন পয়েন্ট ১ থাকা মানে ১ জন টিচার আছেন যা এ সাবজেক্ট টা পড়ান । mask2 এর কোন পয়েন্ট ১ থাকা মানে ২ জন টিচার আছেন যা ঐ সাবজেক্ট পড়ান । আমরা যখন দেখব ( mask1 == ( 1 << total_sum ) - 1 && mask2 == ( 1 << total_sub ) - 1 ) ) এই কন্ডিশন টা ট্রু হচ্ছে মানে আমরা সব সাবজেক্ট এ কমপক্ষে দুইজন টিচার আছে তা পেয়েগেছি । ইনপুট এর বিশাল প্রবলেম আছে  এই প্রবলেম এ । এর বাদে আর কোন বিশেষ দিক নেই । straight forward bitmask dp এর প্রবলেম ।

	const int NX = 104 ;
	const int INF = 1 << 29 ;
	const int MX = ( 1 << 8 ) + 3 ;
	int vis[ NX ][ MX ][ MX ] , cs , dp[ NX ][ MX ][ MX ];
	int sv[ NX ] , n , m , lim , need[ NX ] ;
	int DP( int pos , int mask1 , int mask2 )
	{
	if( mask1 == lim && mask2 == lim ) return 0 ;
	if( pos == n ) return INF ;
	int &v = vis[pos][mask1][mask2];
	int &ret = dp[pos][mask1][mask2];
	if( v == cs ) return ret ;
	v = cs ;
	ret = INF ;
	int tmp = ( mask1 & sv[pos] );
	ret = min( ret , DP ( pos + 1 , mask1 | sv[pos] , mask2 | tmp ) + need[pos] );
	ret = min( ret , DP( pos + 1 , mask1 , mask2 ) );
	return ret ;
	}
	int main()
	{
	// I will always use scanf and printf
	while( scanf("%d %d %d",&lim,&m,&n ) == 3 )
	{
	cs++;
	getchar();
	if( lim == 0 && n == 0 && m == 0 ) break ;
	lim = ( 1 << lim ) - 1 ;
	int mask1 = 0 , mask2 = 0 ;
	int ans = 0 ;
	string inp ;
	stringstream ss ;
	rep( i , m )
	{
	ss.clear();
	getline( cin , inp );
	ss << inp ;
	int fst = 1 , val ;
	int mask = 0 ;
	while( ss >> val )
	{
	if( fst )
	{
	ans += val ;
	fst = 0 ;
	}
	else
	{
	mask |= ( 1 << ( val - 1 ) );
	}
	}
	int tmp = ( mask1 & mask );
	mask1 |= ( mask );
	mask2 |= tmp ;
	}
	rep( i , n )
	{
	ss.clear(); // clear is important
	getline( cin , inp );
	ss << inp ;
	int fst = 1 , val ;
	sv[i] = 0 ;
	while( ss >> val )
	{
	if( fst )
	{
	need[i] = val ;
	fst = 0 ;
	}
	else
	{
	sv[i] |= ( 1 << (val - 1 ));
	}
	}
	}
	printf("%d\n",DP( 0 , mask1 , mask2 ) + ans );
	}
	return 0;
	}

view raw dp32.cpp hosted with ❤ by GitHub

Anagram Division 

এই প্রবলেম এ আমাদের বলা হইছে আমাদের একটা string ( s )  আর একটা নাম্বার ( d ) দেওয়া হবে । আমাদের বলতে হবে স্ট্রিংটা দ্বারা কয়টা নাম্বার এরকম করা যায় যা আমাদের এই নাম্বার d দ্বারা ভাগ যাবে ।

এই প্রবলেমটা ততক্ষণ পর্যন্ত কঠিন লাগতে পারে যতক্ষণ পর্যন্ত আমরা bitmask dp এর কথা ভাবি না । এইখানে বলা আছে স্ট্রিং এর লেন্থ হবে হাইস্ট ১০ ( যা খুব ভাল bitmask এর জন্য ) এবং d এর মান হাইস্ট হবে  < ১০০১ যাও অনেক ভাল । আমরা চাইলেই dp[ ( 1 << 10 ) ][ 1005 ] খুব সহজেই declear করতে পারি । এইখানে একটা উল্লেখ্য ব্যাপার আছে । যেহেতু permutation জড়িত , একই position main initial string এর different position same digit বসিয়েও আমরা একই নাম্বার তৈরি করতে পারি যা হবে ডুপলিকেট । ধরি আমাদের দেওয়া হল ০০০ স্ট্রিং । এইখানে bitmasking এ আমরা শুধু মাত্র position check করি । first index এ তার initial index এর 1  , 2 , 3 rd সব পজিশনের ভ্যালু বসেই কল হয় । কিন্তু আমাদের এই প্রবলেম এর জন্য আমাদের এই চেকটাও রাখতে হবে , আমরা যদি first index এ initial index এর 1 st position এর 0 বসাই তাহলে বসতে পারে initial string থেকে 2 , 3rd position এর ০ আমরা ১ নাম্বার পজিশনে বাসাব না । কারণ বসালে একই জিনিস দুই/আরও  বেশিও হতে পারে বসবে যা ডুপলিকেট অনেক কিছু তৈরি করবে । এর জন্য আমরা লোকাল ফ্লাগ array ( size 10 is good ) ব্যাবহার করব ।

	string inp ;
	int lim ;
	int dp[ ( 1 << 10 ) + 1 ][ 1005 ] , d ;
	int vis[ ( 1 << 10 ) + 1 ][ 1005 ] , cs ;
	int DP( int mask , int mod )
	{
	if( mask == ( 1 << lim ) - 1 )
	{
	return mod == 0 ; // if mod is still 0 that means this generated number can be divisible by d
	}
	int &ret = dp[mask][mod];
	int &v = vis[ mask ][mod ];
	if( v == cs ) return ret ;
	v = cs ;
	int flag[10] = {0};
	int i ;
	ret = 0 ;
	for ( i = 0 ; i < lim ; i++ )
	{
	int x = inp[i] - '0' ;
	if( mask & ( 1 << i ) || flag[x] ) continue ;
	flag[x] = 1 ; // make sure digit x wont place this position again
	ret += DP( mask | ( 1 << i ) , ( ( mod * 10 ) + x )%d );
	}
	return ret ;
	}
	int main()
	{
	// I will always use scanf and printf
	// May be i won't be a good programmer but i will be a good human being
	int t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	cin >> inp ;
	d = II ;
	lim = inp.size();
	int ans = DP( 0 , 0 );
	printf("Case %d: %d\n",cs,ans);
	}
	return 0;
	}

view raw dp33.cpp hosted with ❤ by GitHub