At Coder Educational DP-K | DP Series(Episode-13)

 Problem Description here

Problem: এই প্রব্লেমে দুইজন প্লেয়ার একটি গেম খেলবে। যেটা হবেঃ

একটি পাথরের স্তূপ আছে যেখানে K সংখ্যক পাথর আছে। এবং n টি সংখ্যার একটি অ্যারে দেয়া আছে। প্রথম চাল দিবে ১ম জন, ২য় চাল ২য় জন, ৩য় চাল ১ম জন, ৪র্থ চাল ২জন, এভাবে খেলা চলতে থাকবে।

প্রতি চালে একজন প্লেয়ার অ্যারে থেকে যেকোন একটি সংখ্যা নিবে এবং এক্সেক্টলি ততোগুলো পাথর স্তূপ থেকে ফেলে দিবে। যদি কোন প্লেয়ার তার চালে কোন পাথরই না ফেলতে পারে তবে সে হারবে। 

বলতে হবে, দুইজন প্লেয়ারই অপ্টিমালি খেললে কে জিতবে? 

Recursive Solution: 

১) এই প্রব্লেমে আমাদের স্টেট নিতে হবে দুটি।

    স্টেট-১ঃ বর্তমানে স্তুপে কয়টি পাথর অবশিষ্ট আছে।

    স্টেট-২ঃ এখন কোন প্লেয়ার চাল দিবে। 

২) সল্যুশনে আমরা প্রথম প্লেয়ার কে ০তম এবং ২য় প্লেয়ার কে ১তম প্লেয়ার হিসেবে বিবেচনা করেছি।

৩) বেস কেসে পৌঁছানো মানে এখন আর চাল দেয়া সম্ভব নয়। অর্থাৎ, বেস কেসে যদি ১ম প্লেয়ার পৌঁছায় তার মানে ২য় প্লেয়ার উইনার আর যদি ২য় প্লেয়ার পৌঁছায় তার মানে ১ম প্লেয়ার উইনার। 

৪) বেস কেস ভিন্ন, যেহেতু দুইজন প্লেয়ার অপ্টিমালি খেলবে সেহেতু এখন যদি ১ম প্লেয়ার এর চাল হয় তবে ১ম প্লেয়ার সম্ভাব্য সকল চাল এর মধ্যে যে চালে জিতবে সে চাল ই দিবে। একইভাবে ২য় প্লেয়ারও খেলবে। 

৫) যেহেতু, অ্যারে থেকে যেকোন সংখ্যাই নির্বাচন করা যায় সেহেতু একটি ইনার লুপ চালিয়ে অ্যারের সকল সংখ্যা নিয়েই চেষ্টা করতে হবে। 

	#include<bits/stdc++.h>
	using namespace std;
	int n,k,ara[105],dp[100005][3];
	/** State-1: Remaining stone ; State-2: which player is playing now **/
	int FuN(int baki,int player)
	{
	if(baki < ara[0]){
	return player^1;
	}
	if(dp[baki][player] != -1)
	return dp[baki][player];
	bool fg;
	if(player == 0){
	fg=1;
	for(int i=0; i<n; i++){
	if(baki-ara[i] >= 0)
	fg = fg & FuN(baki-ara[i] , player^1);
	else
	break;
	}
	}
	else
	{
	fg=0;
	for(int i=0; i<n; i++){
	if(baki-ara[i] >= 0)
	fg = fg | FuN(baki-ara[i] , player^1);
	else
	break;
	}
	}
	return dp[baki][player]=fg;
	}
	int main()
	{
	int i,j,ans;
	memset(dp , -1 , sizeof(dp));
	cin>>n>>k;
	for(i=0; i<n; i++)
	cin>>ara[i];
	sort(ara,ara+n);
	ans = FuN(k,0);
	if(ans == 0)
	printf("First\n");
	else
	printf("Second\n");
	return 0;
	}

view raw Episode-13.1.cpp hosted with ❤ by GitHub

Iterative Solution:

১) Iterative Solution এ dp[i][j] বলতে বুঝানো হয়েছে, স্তুপে পাথর সংখ্যা যদি i হয় এবং বর্তমান চাল যদি jth প্লেয়ার এর হয় তবে কোন প্লেয়ার জিতবে। 

রিকার্সিভ সল্যুশন বুঝে থাকলে বাকি অংশ বুঝতে সমস্যা হওয়ার কথা নয়। 

	#include<bits/stdc++.h>
	using namespace std;
	int n,k,ara[105],dp[100009][3];
	int main()
	{
	cin>>n>>k;
	for(int i=1 ; i<=n ; i++)
	cin>>ara[i];
	sort(ara+1 , ara+n+1);
	///Base Case
	for(int val=0 ; val<ara[1] ; val++){
	for(int player=0 ; player<2 ; player++)
	dp[val][player] = player^1;
	}
	for(int val=ara[1] ; val<=k ; val++){
	for(int player=0 ; player<2 ; player++){
	int fg;
	if(!player){ ///First player move
	fg = 1;
	for(int i=1 ; i<=n ; i++){
	if(val-ara[i] >= 0)
	fg &= dp[val - ara[i]][player^1];
	else
	break;
	}
	}
	else{ ///Second player move
	fg = 0;
	for(int i=1 ; i<=n ; i++){
	if(val-ara[i] >= 0)
	fg |= dp[val - ara[i]][player^1];
	else
	break;
	}
	}
	dp[val][player] = fg;
	}
	}
	if(!dp[k][0])
	printf("First\n");
	else
	printf("Second\n");
	return 0;
	}

view raw Episode-13.2.cpp hosted with ❤ by GitHub

Next Episode

Happy Coding