Light OJ ( DP part - 2 )

এইটা এই সিরিজের দ্বিতীয় লিখা । এই পর্বে কিছু  interesting problem এর solution process নিয়ে লিখার চেস্টা করতেছি ।

Lighted Panels :::

এই প্রবলেম এ আমাদের একটা লাইট প্যানেল এর অবস্থা দেওয়া  হয়েছে , কোন অবস্থার '*' এর মানে হচ্ছে লাইট জ্বলে আছে , '.' মানে হচ্ছে লাইটা নিভে আছে । আমাদেরকে মিনিমাম মুভে প্যানেল এর সবগুলা লাইট জ্বালাতে হবে । এইখানে যখন কোন পয়েন্ট  toggle করা হয় ( মানে এইটা যে অবস্থায় আছে জ্বলা থাকলে নিভা , নিভা থাকলে জ্বলে উঠবে ) ঐ পয়েন্ট এর সাথে adjacent যে পয়েন্টগুলা থাকে ( diagonal সহ ) তারাও toggle করবে। 

• যে কোন প্রবলেম solution process বের করার একটা way হচ্ছে constrain গুলা চেক করা । শুধু মাত্র ইনপুট এর লিমিট দেখেই আমরা কোন সল্যুশন প্রসেস চিন্তা করা শুরু করব আবার কোন প্রসেস চিন্তা করা বাদ দিব ।  এইখানে Row <= 8 and Column <= 8 দেওয়া আছে । স্বাভাবিক ভাবেই  লিমিট কম হলে আমাদের জন্য ভাল । আমরা যদি dp solution develop করতে চাই তাইলে মনের খুশী মত state ও বাড়াইয়া ফেলতে পারব যেটা লিমিট অনেক বড় হইলে সম্ভব হইত না । 
• এই প্রবলেমটা যদি দেখি আমরা যখন কোন পয়েন্ট toggle করি তাহলে কি হবে আমরা যে row তে আছি তার আগের row এবং পরের row এর আমরা যে column এ আছি তার আগের column এবং পরের column নিয়ে কাজ করব । অর্থাৎ আমরা যদি row wise করে লাইটগুলা জ্বালাতে থাকি তাহলে আমাদের main concern হইল আগের column , এখন যে column এ আসি এ column এবং পরের column নিয়ে । একই জিনিস column wise করে এগানোর জন্য প্রযোজ্য । তবে আমরা row wise solution process টা দেখব । 
• আমারা আমাদের solution process develop করব row wise , একটা জিনিস দেখি আমরা যখন যে row নিয়ে কাজ করছি এই row এর information তার আগের row এবং পরের row এর উপর নির্ভর করে । তাই কোনভাবে আমি এখন যে row তে আসি তার কিঅবস্থা ( মানে কোন কোন পয়েন্ট জ্বলে আসে কি নিভে আসে ) যে row থেকে আসলাম তার কি অবস্থা ছিল এবং যে row তে যাব তার কি অবস্থা আছে আমাদের তা জানা থাকা দরকার । 
• এই প্রবলেম এর একটা ভাল দিক ছিল এইখানে লিমিট অনেক কম । লিমিট কম থাকলে আমরা অনেক state নিয়ে ভাবতে পারি খুব একটা difference হয় না । যেহেতু আমরা row wise কাজ করতেছি অবশ্যই আমরা কোন row তে আসি তা একটা state , আমরা যে row থেকে আসলাম তার কি অবস্থা ( কোন কিছু যার মাধ্যমে আমরা বুঝতে পারি কোন কোন পজিশনের লাইট কি অবস্থায় আছে ) , এবং এখন যে অবস্থায় আসি তার কি অবস্থা আমাদের জানা থাকতে হবে । মানে এই ইনফরমেশনগুলা আমাদের state এ থাকা লাগবে । এখন কোন লাইট জ্বলে আসে কি নিভে আসে তা আমরা খুব সহজেই বিট  দিয়ে বুঝতে পারি , যেহেতু column highest হতে পারে ৮টা তাই আমাদের শুধুমাত্র ( ১ << ৮ ) সাইজের কোন state থাকলেই আমরা বুঝে যাব কোন  কোন পজিশনে কি কি আছে । তাই আমাদের dp table হবে । dp [ number_of_row ] [ bit_position_of_previous_row] [ bit_position_of_current_row ] অর্থাৎ dp[ 8 ] [ ( 1 << 8 ) ] [ ( 1 << 8 ) ] . আসলে তাইলে আমাদের লাগতেছে  8 * ( 1 << 8 ) * ( 1 << 8 ) == 524288 size এর dp array । 
• আমাদের ক্যালকুলেশন এর জন্য আমাদের পরের row ও দরকার হবে এইটা আমরা কোথায় পাব । আমরা প্রথমেই ইনপুট নেওয়ার সময় একটা array তে রেখে দিতে পারি কোন কোন লাইট এখন জ্বলে আসে ।  
• যে  row তে আসি এর প্রতিটা combination করে আমরা আমাদের store value গুলা change করে দেখব । এর জন্য আমরা subset mask use করতে পারি । যেহেতু column এর highest limit 8 .তাই ( 1 << 8 ) == 256 খুব সহজেই আমরা আমাদের dp এর ভিতর তা চালাতে পারি । 
• যখন আমরা নেক্সড row তে যাব যদি না আমরা প্রথম কলামে থাকি তাহলে অবশ্যই আমাদের sure করতে হবে আমাদের আগের row এর সবগুলা লাইটা জ্বালানো আছে ( যদি না থাকে তাহলে আর কোন ভাবেই ঐ লাইটাকে আর জ্বালানো সম্ভব হবে না  কিন্তু প্রথম রো থেকে এই জন্যই যাব কারণ আমি দ্বিতীয় রো থেকেও প্রথম রো এর সব লাইট নিভাতে পারি । ) ।
  
  কোড :

	const int INF = 1 << 29 ;
	int vis[9][ ( 1 << 8 ) + 10 ][ ( 1 << 8 ) + 10 ] , cs ;
	int dp[9][ ( 1 << 8 ) + 10 ][ ( 1 << 8 ) + 10 ];
	int sv[9] , r , c ;
	char str[10];
	int DP( int idx , int curmask , int prvmask )
	{
	if( idx >= r )
	{
	if( prvmask == ( 1 << c ) - 1 ) return 0 ;
	else return INF ;
	}
	int &v = vis[idx][curmask][prvmask];
	int &ret = dp[idx][curmask][prvmask];
	if( v == cs ) return ret ;
	// printf(" here \n");
	ret = INF ;
	for( int i = 0 ; i < ( 1 << c ); i++ )
	{
	int cnt = 0 ;
	int row[3] = {prvmask , curmask , sv[idx+1] }; // আগে রো , এখন যে রোতে আছি , যে রো তে যাব
	for ( int j = 0 ; j < c ; j++ ) // সাবসেট মাস্ক দিয়ে all combination নিয়ে দেখছি
	{
	if( !(i & ( 1 << j )) ) continue ; // no need for toggle
	// need to toggle
	cnt++;
	rep( k , 3 ) row[k] ^= ( 1 << j );
	if( j + 1 < c ) rep ( k , 3 ) row[k] ^= ( 1 << ( j + 1 ) );
	if( j - 1 >= 0 ) rep ( k , 3 ) row[k] ^= ( 1 << ( j - 1 ) );
	}
	if( idx == 0 ) ret = min( ret , cnt + DP( idx + 1 , row[2] , row[1] ) );
	else if( row[0] == ( 1 << c ) - 1 ) // only if there is all light open in our previous row
	ret = min( ret , cnt + DP( idx + 1 , row[2] , row[1] ) );
	}
	return ret ;
	}
	int main()
	{
	int t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	r = II , c = II ;
	ms( sv , 0 );
	rep( i , r )
	{
	scanf("%s",str);
	int mask = 0 ;
	rep( j , c )
	{
	if( str[j] == '*' ) mask |= ( 1 << j );
	}
	sv[i] = mask ; // save the current condition
	}
	int ans = DP( 0 , sv[0] , 0 );
	if( ans == INF ) printf("Case %d: impossible\n",cs);
	else printf("Case %d: %d\n",cs,ans);
	}
	return 0;
	}

view raw dp1.cpp hosted with ❤ by GitHub

এই প্রবলেমটা আমরা itterative ভাবেও  করতে পারি , subset mask এর মাধ্যমে ।

Tiles (II) :
এইটা একটু বিরক্তি কর bitmask প্রবলেম । আমাদের ছয়টা বিভিন্ন সাইজের টাইলস দেওয়া আছে । আমাদের বলতে হবে এই বিভিন্ন টাইলজ দিয়ে ( n x m ) সাইজের একটা গ্রীড কতভাবে পূরণ করা যাবে । দুইটা বোর্ড different হবে যদি এদের মধ্যে কোন cell এর কালার different হয় ।

• ইনপুট লিমিট এ দেওয়া দেওয়া আছে ( 1 <= n , m <= 100 but min( n , m ) <= 8 ) । এর মানে হইল row , column এর মধ্য যে কোন একটা 8 এর চেয়ে কম হবে । এইটার একটা ব্যাপার হইল আমরা চাইলে এই কম পার্টটাকে বিট করে ফেলতে পারি । এইখানে Row/Column দুইটার যে কোনটাই হইতে পারে । যেহেতু আমরা জানি না কোনটা হবে আমরা ধরে নেই column এর পার্টটাতে আমরা বিটমাস্ক করব কিন্তু Row ও হইতে পারে । যদি Row <= 8 হয় তাহলে আমরা given array এর Row এবং Column part টা swap করে দিব । মানে যা input এ ছিল আমাদের column এইটা কে আমরা Row ভ্যালু করে ফেলব  । মানে যদি Row = 8 , Column = 100 হয় তাহলে আমাদের Row হয়ে যাবে ১০০ এবং column হয়ে যাবে ৮ । 
•  এই প্রবলেমটার সাথে আগের প্রবলেম এর মিল আছে । আমরা যদি given tiles গুলা দেখি প্রতিটাই দুইটা row করে নিয়ে হচ্ছে । অর্থাৎ কোন tiles বসবে কি বসবে না এই জন্য আমাদের কাছে কমপক্ষে দুইটা row এর ইনফরমেশন থাকতে যাবে । 
• আমরা যখন কোন tiles বসাতে যাব আমাদের দেখতে হবে আমরা এখন যে Row তে আসি তার পরের Row এর যে সব column নিতে টাইলসটা হবে তা খালি আছে কিনা । 
• আমরা column ফিল করতে করতে next column এ আগাব এবং যেহেতু দুইটা curmask ও nextmask নিয়ে কাজ করছি অবশ্যই আমরা যখন সব Row ফিল করে ফেলব তখন nextmask অবশ্যই ০ থাকবে । 
• এই কাজটা একটু বিরক্তিকর কারণ আমাদের অনেক চেক রাখতে হবে । সবগুলা tiles নিয়ে ফিল করার জিনিসটা আমরা একটা backtrack function এর মাধ্যমে করতে পারি । এইখানে যেহেতু আমরা column এর basis এ ফিল করব ( backtrack এ ) আর লিমিট যেহেতু কম আমাদের খুব একটা বেশী কল হবে না ।
• এইখানে রেজাল্ট কে 2^64 mod করে দিতে বলা হইছে তাই আমরা unsigned long long int use করব ।  

কোড :

	//BISMILLAHIRRAHMANIRRAHIM
	/*
	manus tar shopner soman boro
	all my suceesses are dedicated to my parents
	Author :: Shakil Ahmed
	.............AUST_CSE27.........
	prob ::
	Type ::
	verdict::
	*/
	#include <bits/stdc++.h>
	#define pb push_back
	#define mp make_pair
	#define pi acos(-1.0)
	#define ff first
	#define ss second
	#define re return
	#define QI queue<int>
	#define SI stack<int>
	#define SZ(x) ((int) (x).size())
	#define all(x) (x).begin(), (x).end()
	#define sqr(x) ((x) * (x))
	#define ms(a,b) memset((a),(b),sizeof(a))
	#define G() getchar()
	#define MAX3(a,b,c) max(a,max(b,c))
	#define II ( { int a ; read(a) ; a; } )
	#define LL ( { Long a ; read(a) ; a; } )
	#define DD ({double a; scanf("%lf", &a); a;})
	double const EPS=3e-8;
	using namespace std;
	#define FI freopen ("input.txt", "r", stdin)
	#define FO freopen ("output.txt", "w", stdout)
	typedef long long Long;
	typedef long long int64;
	typedef unsigned long long ull;
	typedef vector<int> vi ;
	typedef set<int> si;
	typedef vector<Long>vl;
	typedef pair<int,int>pii;
	typedef pair<string,int>psi;
	typedef pair<Long,Long>pll;
	typedef pair<double,double>pdd;
	typedef vector<pii> vpii;
	// For loop
	#define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i)
	#define rep(i, n) forab (i, 0, (n) - 1)
	#define For(i, n) forab (i, 1, n)
	#define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i)
	#define per(i, n) rofba (i, 0, (n) - 1)
	#define rof(i, n) rofba (i, 1, n)
	#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
	template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
	template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
	//Fast Reader
	template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
	//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
	//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
	//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
	//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
	/* ************************************** My code start here ****************************************** */
	const int NX = ( 1 << 8 ) + 10 ;
	const int MX = 105 ;
	ull dp[MX][NX] ;
	int vis[MX][NX] , cs , row , col ;
	char inp[MX][MX] , grid[MX][MX] ;
	ull DP(int , int) ;
	ull gen( int r , int c , int curmask , int nxtmask )
	{
	if( c == col ) return DP( r + 1 , nxtmask );
	int cc = ( curmask >> c ) & 1 ;
	int cnc = ( curmask >> ( c + 1 ) ) & 1 ;
	int nc = ( nxtmask >> ( c ) ) & 1 ;
	int nnc = ( nxtmask >> ( c + 1 ) ) & 1 ;
	int npc = ( nxtmask >> max( 0 , c -1 ) ) & 1 ;
	if( cc ) return gen( r , c + 1 , curmask , nxtmask );
	if( grid[r][c] == '#' ) return gen( r , c + 1 , curmask , nxtmask );
	ull ret = 0 ;
	// title one
	if( r + 1 < row )
	{
	if( grid[r][c] == '.' && grid[r+1][c] == '.' && !cc && !nc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) , nxtmask | ( 1 << c ) );
	}
	}
	// tile two
	if( c + 1 < col )
	{
	if( grid[r][c] == '.' && grid[r][c+1] == '.' && !cc && !cnc )
	{
	ret += gen( r , c + 2 , curmask | ( 1 << c ) | ( 1 << ( c + 1 ) ) , nxtmask );
	}
	}
	// tile five
	if( c - 1 >= 0 && r + 1 < row )
	{
	if( grid[r][c] == '.' && grid[r+1][c] == '.' && grid[r+1][c-1] == '.' && !cc && !nc && !npc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) , nxtmask | ( 1 << c) | ( 1 << ( c - 1 ) ) );
	}
	}
	if( r + 1 < row && c + 1 < col )
	{
	// tile 4
	if( grid[r][c] == '.' && grid[r][c+1] == '.' && grid[r+1][c] == '.' && !cc && !cnc && !nc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) | ( 1 << ( c + 1 ) ), nxtmask | ( 1 << c) );
	}
	// tile 3
	if( grid[r][c] == '.' && grid[r+1][c] == '.' && grid[r+1][c+1] == '.' && !cc && !nc && !nnc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) , nxtmask | ( 1 << c) | ( 1 << ( c + 1 ) ) );
	}
	// tile 6
	if( grid[r][c] == '.' && grid[r][c+1] == '.' && grid[r+1][c+1] == '.' && !cc && !cnc && !nnc )
	{
	ret += gen( r , c + 1 , curmask | ( 1 << c ) | ( 1 << ( c + 1 ) ) , nxtmask | ( 1 << ( c + 1 ) ) );
	}
	}
	return ret ;
	}
	ull DP(int r , int mask)
	{
	if( r == row ) return mask == 0 ;
	ull &ret = dp[r][mask];
	int &v = vis[r][mask];
	if( v == cs ) return ret ;
	v = cs ;
	ret = gen(r , 0 , mask , 0 );
	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
	// ms( vis , -1 );
	int t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	row = II , col = II ;
	rep( i , row ) scanf("%s",inp[i]);
	if( row < col )
	{
	rep( i , row ) rep ( j , col ) grid[j][i] = inp[i][j];
	swap( row , col );
	}
	else
	{
	rep( i , row ) rep ( j , col ) grid[i][j] = inp[i][j];
	}
	printf("Case %d: %llu\n",cs,DP(0,0));
	}
	return 0;
	}

view raw DP2.cpp hosted with ❤ by GitHub

Software Company :
এই প্রবলেমটা binary search + dp এর । এইখানে একটা software company এর কথা বলা হইছে । তারা দুইটা প্রোজেক্ট শেষ করবে । n জন employee এর ইনফমেশনে দেওয়া আছে তাদের কত মিনিট করে নেয় দুইটা প্রোজেক্ট এর এক unit কাজ করতে । কোন প্রোজেক্ট সম্পূর্ণ শেষ করতে m unit কাজ কমপ্লিট করতে হবে ।

• এই প্রবলেমটা খুব সম্ভত বুঝাটা এইটা binary search এ হবে এইটাই সব থেকে কঠিন পার্ট । তারপরের কাজ খুব সহজ । আমরা যেকোন একটা employee নিয়ে ও যদি একা দুইটা কাজ করত তাহলে কত সময় লাগতকে high ধরে lower_bound binary seach করব । দেখব lowest কত value এর জন্য আমাদের কাজ দুইটি সম্পূর্ণ করা যাবে । 
• 3 state এর normal dp , current_employee_number , work_left_for_first_one , work_left_for_second_one . এইখানে লিমিট দেওয়া আছে ( 1 <= n , m <= 100 ) তাই আমাদের dp[101][101][101] size এর dp দিয়েই হয়ে যাবে । 
কোড

	const int NX = 102 ;
	int loop , vis[NX][NX][NX] ;
	bool dp[NX][NX][NX] ;
	pii inp[NX];
	int low , high , mid , ans , n , m ;
	bool DP( int idx , int need1 , int need2 )
	{
	if( need1 + need2 == 0 ) return true ;
	if( idx == n ) return false ;
	int &v = vis[idx][need1][need2];
	bool &ret = dp[idx][need1][need2];
	if( v == loop ) return ret ;
	v = loop ;
	ret = false ;
	int i ;
	for ( i = 0 ; i <= need1 && i * inp[idx].ff <= mid ; i++ )
	{
	int k = ( mid - ( i * inp[idx].ff ) )/ inp[idx].ss ;
	if( k > need2 ) k = need2 ;
	if( DP( idx + 1 , need1 - i , need2 - k ) ) return ret = true ;
	}
	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 cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	n = II , m = II ;
	rep( i , n )
	{
	int x = II , y = II ;
	inp[i] = mp( x , y );
	}
	low = 0 , high = inp[0].ff * m + inp[0].ss * m ;
	while( low <= high )
	{
	mid = ( low + high )/2 ;
	loop++;
	if( DP( 0 , m , m ) )
	{
	ans = mid ;
	high = mid - 1 ;
	}
	else low = mid + 1 ;
	}
	printf("Case %d: %d\n",cs,ans);
	}

view raw dp3.cpp hosted with ❤ by GitHub

এই সিরিজের আরো কয়েকটা লিখা ইচ্ছা আছে , যদি লিখার মোটিভেশন বজায় থাকে । ধন্যবাদ পড়ার জন্য ।