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

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