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

Probability & Expected value ( part - 1 )

probability and expected value এর উপর top coder এবং codechef এ ভাল কিছু লিখা হইছে । যে কোন কিছু ভাল করে শিখার একটা ভাল উপায় হইল প্রথমে থিউরী শিখে এইগুলো কোন প্রবলেম এ এপ্লাই করা । আমার ইচ্ছা প্রবলেম সল্ভিং এ আমরা কিভাবে এই থিউরীগুলাকে কাজে লাগাইতে পারি তা নিয়ে লিখা । আমি নিজেও খুব একটা ভাল না এই টপিকটাতে । সাম্প্রতিক সময়ে যেহেতু আমি ২০১৫ এর ঢাকা রিজিওনালের জন্য প্রিপারেশন নিচ্ছি আমি আমার চোখে পড়া ভাল বা মজার প্রবলেম গুলার সল্যুশন ট্রিকগুলা  সিরিজ আকারে লিখে রাখার চেস্টা করছি যেন আগামীতে যে কেউ এইখান থেকে তার বা তার টিমের প্রিপারেশনের জন্য হ্যাল্প নিতে পারে ।

কিছু টিউটরিয়াল এর লিঙ্ক ( আমি এইটা আপডেট করতে থাকব , কোন কারণে এখন টপ কোডারের সাইট এক্সেস করা যাচ্ছে না তাই এইটা এইখানে এখন দিতে পারলাম না )

                  ১। codechef

What is the Probability ?

এই প্রবলেম এ বলা হইছে n জন ব্যাক্তি dice game টা খেলছে । dice এর ৬টা তলের যেকোন একটা তল হইল আমাদের উইনিং ইভেন্ট । মানে হইল ঐ তলটা যে খেলোয়াড় মারার টাইমে উঠে যাবে ও জিতে যাবে । এখানে আমাদের তিনটা ইনফরমেশন দেওয়া হবে । এক কয়জন খেলোয়াড় খেলছে , দুই যে তলটা উঠলে প্রতিযোগী জিতে যাবে ঐ তলটা উঠার সম্ভাব্যতা কত এবং শেষ হচ্ছে আমাদের যে প্রতিযোগীর জন্য probability বের করতে হবে তার সংখ্যা কত । এইখানে সিরিয়াল ওয়াইস মুভ দেওয়া হয় । মানে হইল প্রথমে ১ নাম্বার প্লেয়ার , তারপর ২ নাম্বার এইভাবে n নাম্বার তারপর আবার ১ নাম্বার প্লেয়ার ।  এইখানে সম্ভাব্যতা দশমিকের ৪ ঘর পর্যন্ত বের করতে বলা হইছে ।

আমরা যদি দেখি আমাদের k নাম্বার প্লেয়ারের জন্য তার winning probability বের করতে বলছে তাহলে আমরা এইটা পাই যে যেহেতু ও জিতবে তাহলে ও জিতবে হল k , n + k , n + n + k , n + n + n + k ............ নাম্বার মুভে । যদি ও k নাম্বার মুভে জিতে তাহলে আগের k - 1 মুভ হচ্ছে হারার মুভ , যেখানে সবাই ( 1 - p ) সম্ভাব্যতায় আমাদের winning event করে নি । যদি সে n + k নাম্বার মুভে জিতে তাহলে আগের n + k - 1 গুলা মুভ হচ্ছে হারার মুভ বা আমাদের জিতার ইভেন্ট না উঠার মুভ । যেহেতু সব গুলা dependent event তাই সবাই গুণ আকারে থাকবে । এখন আমারা একটা threshold value set করে নিবে এইখানে যেমন আমি ধরে নিয়েছি ( eps = 1e-9 ) . যখনই আমাদের winning event এর probability এই threshold value এর থেকে কমে যাবে আমরা loop  ব্রেক করে দিব ।

	int cs , t = II ;
	for ( cs = 1 ; cs <= t ; cs++ )
	{
	double p , n , ply;
	scanf("%lf %lf %lf",&n,&p,&ply);
	double res = 0 ;
	while( p * pow( ( 1.0 - p ) , ply - 1 ) > eps )
	{
	res += (p * pow ( ( 1.0 - p ) , ply - 1 )); // what if win now
	ply += n ;
	}
	printf("%.4lf\n",res);
	}

view raw PE1.cpp hosted with ❤ by GitHub

Probability|Given

এই প্রবলেম এ বলা হইছে n জন বন্ধু market এ গেছে এদের মধ্যে থেকে r জন বন্ধু কিছু না কিছু কিনছে । যদি সবার কিনার  সম্ভাব্যতা দেওয়া থাকে ( যদি ও মার্কেট এ যায় তাহলে কিনবে কি কিনবে না এর  সম্ভাব্যতা ) তাহলে যে r জন কিনছে এর মধ্যে প্রত্যেকের কিনার সম্ভাবতা কত ? এইটাই আমাদের এইখানে বলতে বলা হইছে ।


এইখানে আসলে আমাদের বলতে হবে ,

P ( A ( এই ব্যাক্তি কিনবে ) | R ( অবশ্যই R জন কিনবে ) ) = P ( A কিনছে এমন ঘটানায় টোটাল সম্ভাবনা ) / P ( R জন কিনছে এমন ঘটনার টোটাল সম্ভাবনা )

এই প্রবলেমটা আমরা backtrack করে সহজেই টোটাল সম্ভাবনা এবং এমন সবার আলাদা আলাদা কন্ট্রিবিউশনের টোটাল কত ছিল তা পেয়ে যেতে পারি , এমন কি এই কাজটা আমরা next_permutation দিতে করতে পারি , এর জন্য আগে থেকে n size এর কোন array এর  n - r কে মার্ক করব ০ আর বাকি r index কে মার্ক করব ১ । তারপর sort করে next_permutation করব । যে index এ ১ আছে মানে এই কেইজ এ ঐ ইনডেক্স এর জন কিনছিল তা বুঝায় । এইভাবে টোটাল এবং আলাদা আলাদা সবার টোটাল বের করে সবার  সম্ভাব্যতা উপরের সুত্র দিয়ে বের করতে পারি ।

	const int NX = 25 ;
	double tot[ NX ] , p [ NX ] ;
	int n , r ;
	bool input()
	{
	n = II , r = II ;
	if( n == 0 && r == 0 ) return 0 ;
	rep ( i , n )
	{
	tot[i] = 0 ;
	scanf("%lf",&p[i]);
	}
	return 1 ;
	}
	double DP( int pos , double P , int taken )
	{
	if( pos == n )
	{
	if( taken == r ) return P ;
	else return 0.0 ;
	}
	double ans1 = 0 , ans2 = 0 ;
	if( taken < r ) // its possible to buy
	{
	ans1 = DP( pos + 1 , P * p[pos] , taken + 1 );
	tot[ pos ] += ans1 ;
	}
	ans2 = DP( pos + 1 , P * ( 1 - p[pos] ) , taken );
	return ans1 + ans2 ;
	}
	int main()
	{
	int cs = 1 ;
	while(input())
	{
	double ans = DP( 0 , 1 , 0 );
	printf("Case %d:\n",cs++);
	rep( i , n ) printf("%lf\n",tot[i]/ans);
	}
	return 0;
	}

view raw PE2.cpp hosted with ❤ by GitHub

Vampires :

এই প্রবলেম এ বলা হইছে দুইজন পিশাচ ( Vampirer এর বাংলা টার্ম :p ) যুদ্ধ লাগছে , প্রাথমিক ভাবে দুইজন এর লাইফ হচ্ছে যথাক্রমে ev1 , ev2 । এইখানে আরো দুইটা ইনফমেশন দেওয়া আছে । dice head , D .  এইখানে যে কোন ফাইটে প্রথম পিশাচের জিতবে যদি  একটা dice এর ৬টা তলের মধ্যে যেকোন তল উঠল এবং তা যদি given dice_head এর সমান বা ছোট হয় । যদি কোন পিশাচ কোন গেম জিতে তাহলে অপর পিশাচের লাইফ থেকে D amount life কমিয়ে ফেলবে । আমাদের বলতে হবে এই যুদ্ধে প্রথম পিশাচ জিতার সম্ভাব্যতা কত ?

এই প্রবলেমটা একটা ক্লাসিক সম্ভাব্যতা  প্রবলেম এর ক্লোন   "gambler's ruin problem" .  ঐ প্রবলেম এ দুইজন gambler যাদের initially n1 আর n2 টাকা আছে তারা বেট করে । যেখানে প্রতিটা গেম এর জন্য একটা  ফিক্সড সম্ভাব্যতা থাকে জিতার । যতক্ষণ না দুইজন এর একজন জিতছে তখন খেলা চলতেই থাকবে । এই প্রবলেম টার একটা closed form solution আছে ( formula solution ) না হলে হয়তো infinity পর্যন্ত খেলা চলতেই থাকত । প্রাথমিক অবস্থা দেখে আমরা বলে দিতে পারি কোন প্লেয়ার এর জিতার সম্ভাব্যতা কত ।

যদি l হয় প্লেয়ার ১ এর জিতার সম্ভাব্যতা এবং q = 1 - l হয় প্লেয়ার ২ এর জিতার সম্ভাব্যতা তাহলে প্লেয়ার ১ এর জিতার সম্ভাব্যতা হবে ( 1 - pow( q/p , n1 ) )/ ( 1 - pow( q/p , n1 + n2 ) ) । এবং প্লেয়ার ২ এর হবে ১ বিয়োগ এইটা ।

আমাদের এই প্রবলেমটাকে আমরা Gambler ruin problem এ convert করতে পারি । এইখানে n1 , n2 হবে
n1 = ceil( ev1 / d ) , n2 = ceil ( n2 / d ) .  p = ( given_head ) / 6.0 and q = ( 1 - p ) .

তবে যদি  p == q হয় তাহলে একটা special case হয় যেখানে প্রথম জনের জিতার সম্ভাব্যতা হবে  n1 / ( n1 + n2 ) .

	int a[5] ;
	while( scanf("%d %d %d %d",&a[0],&a[1],&a[2] , &a[3] ) == 4 )
	{
	if( a[0] == 0 && a[1] == 0 && a[2] == 0 && !a[3] ) break ;
	ev1 = a[0];
	ev2 = a[1];
	atk = a[2];
	dif = a[3];
	double res ;
	n1 = ( a[0] + a[3] - 1 ) / a[3] ;
	n2 = ( a[1] + a[3] - 1 ) / a[3] ;
	if( atk == 3.0 ) // equal probility
	{
	res = ( n1 / ( n1 + n2 ) );
	res *= 100 ;
	}
	else
	{
	double p = atk / 6.0 ;
	double q = ( 1 - p );
	res = ( 1 - pow( q/p , n1 ) )/ ( 1 - pow( q/p , n1 + n2 ) );
	res *= 100 ;
	}
	printf("%.1lf\n",res);
	}

view raw PE3.cpp hosted with ❤ by GitHub

এই পর্বে এইটুকুই । কোন ভুল থাকলে বা কনফিউশন থাকলে কমেন্ট করে জানাতে পারেন ।

DP trick - Knuth's optimization

কিছু classical dp problem আছে "cutting rod" এর মত যেখানে আমাদের একটা গ্রুপ এর মধ্যে ম্যাস্কিমাম বা মিনিমাম ভ্যালু বের করতে হয় । প্রবলেমগুলাতে এই ধরনের recursion relation থাকে
if l is the left part and r is the right part of the interval then

dp[l][r] = min( dp[l][r] , d[l][m] + dp[m][r] ) + Inp[l][r] ;

এই প্রবলেমগুলাকে আমরা l থেকে r এ যে কোন mid point ধরে o( n ^ 3 ) এ যেখানে n হচ্ছে আমরা রডটাকে কতটা ভাগে ভাগ করতে পারি প্রবলেমটা সল্ভ করতে পারি , যা লিমিট একটু বড় হলে TLE দিবে । এই ধরনের প্রবলেম সল্যুশনে আমরা knuth's optimization technique use করতে পারি এতে code এর run time O ( n ^ 3 ) থেকে কমে এসে O ( n ^ 2 ) হয়ে যায় ।

তবে তা ব্যাবহার করা যাবে যদি নিচের দুইটা শর্ত বজায় থাকে ।

1.  quadrangle inequality
   Inp[ a ] [ c ] + Inp [ b ] [ d ] <= Inp[a][d] + Inp[ b ][ c ] where a <= b <= c <= d
2. monotonicity  

         Inp[b][c] <= Inp[a][d] where a <= b <= c <= d 

যদি সহজে বলি আমাদের পার্টিশন পয়েন্ট গুলা শর্ট হিসাবে থাকবে ( ছোট থেকে বড় )

আমরা একটা প্রবলেম নিয়ে এইটা কিভাবে এই ট্যাকনিক এ সল্ভ করা যাবে এইটা দেখি ।
Breaking Strings :

এই প্রবলেম এ একটা string কে কিভাবে break করলে সব থেকে মিনিমাম খরচে করা যাবে তা বলতে হবে । এইখানে string এর breaking point গুলা কি কি তা দেওয়া হয়েছে । এইখানে যে কোন পয়েন্ট এ ব্রেক করার সময় টোটাল কত lenght এর পার্ট থেকে এইটা ভাঙ্গছে এইটাই হচ্ছে এর cost ।

এর সমাধানে কোন পার্ট l - r এর জন্য এর mid[l][r] হচ্ছে এই পয়েন্ট যেখানে l - r  ভাঙলে সব থেকে কম হবে । যেহেতু middle point monotonously  end point এর উপর নির্ভর করে তাই
 mid[ l ][ r - 1] <= mid [ l ][ r ] <= mid [ l + 1 ][ r ] এইটা বজায় থাকবে । এইখানে আমরা l to r এর জন্য mid point update করতে থাকব mid[l][r-1] & min[l+1][r] এর পার্ট থেকে কারণ অবশ্যই best mid point ( partioning point ) হবে mid[l][r-1] <= our_target_partitioning_point <= mid[l+1][r ] for l - r interval .

	const int NX = 1005 ;
	const Long INF = 1e17 ;
	Long dp[NX][NX] , mid[NX][NX] , inp[NX] ;
	int n , m ;
	Long kunth_optimization()
	{
	ms( dp , 0 );
	ms( mid , 0 );
	int l , r , s ;
	for ( s = 0 ; s <= m ; s++ ) // length of the substring
	{
	for ( l = 0 ; l + s <= m ; l++ ) // left starting part
	{
	r = s + l ; // right ending part
	if( s < 2 )
	{
	dp[l][r] = 0 ; // base case , nothing to break
	mid[l][r] = l ; // mid is equal to left border
	continue ;
	}
	int mleft = mid[l][r-1]; // knuth's tricks
	int mright = mid[l+1][r];
	dp[l][r] = INF ;
	for ( int mm = mleft ; mm <= mright ; mm++ )
	{
	Long tmp = dp[l][mm] + dp[mm][r] + ( inp[r] - inp[l] );
	if( tmp < dp[l][r] )
	{
	dp[l][r] = tmp ;
	mid[l][r] = mm ; // updating mid
	}
	}
	}
	}
	return dp[0][m] ;
	}
	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
	//cout << ( 1 << 30 ) << endl ;
	while( scanf("%d %d",&n,&m) == 2 )
	{
	m++ ;
	inp[0] = 0 ;
	for ( int i = 1 ; i < m ; i++ ) inp[i] = LL ;
	inp[ m ] = n ;
	printf("%lld\n",kunth_optimization());
	}
	return 0;
	}

view raw knuth.cpp hosted with ❤ by GitHub

প্রতিটা starting l এর জন্য আমরা চেক করে দেখছি যার জন্য m বার iteration লাগছে । run time  O( m ^ 2 ) .
প্রবলেম : 1
Reference Link : here