At Coder Educational DP-L | DP Series(Episode-14)

 Problem Description here

Problem: এটি মূলত ইন্টারভাল ডিপির একটি প্রব্লেম।

এই প্রব্লেমে দুইজন প্লেয়ার একটি গেম খেলবে। গেমটা হচ্ছে, n সাইজের একটি অ্যারে দেয়া আছে। প্রতি চালে একজন প্লেয়ার অ্যারের সর্ববামের অথবা সর্বডানের ভ্যালুটা নিবে এবং সেটি অ্যারে থেকে বাদ দিবে। ১ম প্লেয়ার এর মোট স্কোর X এবং ২য় প্লেয়ার এর মোট স্কোর Y হলে, ১ম প্লেয়ার চাইবে X-Y ম্যাক্সিমাইজ করতে এবং ২য় প্লেয়ার চাইবে X-Y মিনিমাইজ করতে। ২জন প্লেয়ার অপ্টিমালি খেলবে। 

উল্লেখ্য যে, ১ম চাল ১ম প্লেয়ার এর, ২য় চাল ২য় প্লেয়ার, ৩য় চাল ১ম প্লেয়ার, ৪র্থ চাল ২য় প্লেয়ার এভাবে চলবে। 

Recursive Solution:

১) এই প্রব্লেমে প্রথম প্লেয়ার এর টার্গেট হচ্ছে X-Y ম্যাক্সিমাইজ করা এবং ২য় প্লেয়ার এর টার্গেট হচ্ছে X-Y মিনিমাইজ করা। ভালোভাবে লক্ষ্য করলে দেখবে যে, এর মানে হচ্ছে উভয় প্লেয়ার  চায় তার নিজের স্কোর যতোটা সম্ভব বাড়াতে।

২) কিন্তু, আমরা একই সাথে উভয় প্লেয়ার এর স্কোর নিয়ে কাজ করতে পারি না। তাহলে উপায়?

আরেকটি ব্যাপার কি লক্ষ্য করেছো? অ্যারের যেসব ভ্যালু ১ম প্লেয়ার নিবে না সেগুলো অবশ্যই ২য় প্লেয়ার নিবে! 

তাহলে, ব্যাপারটি কি দাঁড়ালো? 

আমরা যদি শুধু ১ম প্লেয়ার এর স্কোর নিয়ে কাজ করি তাহলেই কিন্তু হচ্ছে। ১ম প্লেয়ার তার চালে চাইবে এই স্কোর বাড়াতে আর ২য় প্লেয়ার তার চালে এই স্কোর কমাতে চাইবে। কারণ, ১ম প্লেয়ার এর স্কোর কমা মানেই কিন্তু ২য় প্লেয়ার এর স্কোর বাড়া! 

৩) এখন স্টেট কি কি হবে? যেহেতু, আমরা অ্যারের সর্ববামের ভ্যালু অথবা সর্বডানের ভ্যালু নিতে পারি সেহেতু আমরা ৩টি স্টেট নিয়ে কাজ করতে হবে।

    স্টেট-১ঃ অ্যারের সর্ববামের কোন পজিশনটি এখনও কেউ নেয় নি।

    স্টেট-২ঃ অ্যারের সর্বডানের কোন পজিশনটি এখনও কেউ নেয় নি।

    স্টেট-৩ঃ এখন, কোন প্লেয়ার এর চাল

৪) ১ম প্লেয়ার এর চালে একবার সে বামের ভ্যালু টি কেটে কত বানানো যায় দেখবে। আবার, ডানের ভ্যালুটি কেটে কত বানানো যায় দেখবে। দুটির মধ্যে ম্যাক্সিমামটিই সে নিবে।

	ret1 = ara[lft] + FuN(lft+1 , rgt , player^1);
	ret2 = ara[rgt] + FuN(lft , rgt-1 , player^1);
	return dp[lft][rgt][player] = max(ret1 , ret2);

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

৫) ২য় প্লেয়ার এর চালে একবার সে বামের ভ্যালুটি কেটে কত বানানো যায় দেখবে। আবার, ডানের ভ্যালুটি কেটে কত বানানো যায় দেখবে। দুটির মধ্যে মিনিমামটি সে নিবে। 

	ret1 = FuN(lft+1 , rgt , player^1);
	ret2 = FuN(lft , rgt-1 , player^1);
	return dp[lft][rgt][player] = min(ret1 , ret2);

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

উপরের দুটি ক্ষেত্রে কোডে একটি পার্থক্য দেখতে পাচ্ছো নিশ্চয়ই। সেটি হচ্ছে, ১ম প্লেয়ার যখন একটি ভ্যালু কাটছে সেটি স্কোর এর সাথে যোগ হচ্ছে। কিন্তু, ২য় প্লেয়ার যখন কাটছে সেটি স্কোর এর সাথে যোগ হচ্ছে না!!!

কারণ, আমরা কিন্তু ১ম প্লেয়ার এর স্কোর এর হিসেব রাখতেছি শুধু। কাজেই, ২য় প্লেয়ার যে ভ্যালু কাটছে সেটি বাদ যাবে। এবং ২য় প্লেয়ার স্কোর মিনিমাইজ করবে। কারণ, ১ম প্লেয়ার এর স্কোর মিনিমাইজ আর ২য় প্লেয়ার এর স্কোর ম্যাক্সিমাইজ একই কথা! 

আশা করি, সম্পূর্ণ কোড বুঝতে আর সমস্যা হবে না।

	#include<bits/stdc++.h>
	using namespace std;
	long long n,ara[3005],dp[3005][3005][2];
	///1-First Player ; 0-Second Player
	long long FuN(int lft,int rgt,int player)
	{
	if(lft > rgt)
	return 0LL;
	if(dp[lft][rgt][player] != -1)
	return dp[lft][rgt][player];
	long long ret1=0 , ret2=0;
	if(player){
	ret1 = ara[lft] + FuN(lft+1 , rgt , player^1);
	ret2 = ara[rgt] + FuN(lft , rgt-1 , player^1);
	return dp[lft][rgt][player] = max(ret1 , ret2);
	}
	else{
	ret1 = FuN(lft+1 , rgt , player^1);
	ret2 = FuN(lft , rgt-1 , player^1);
	return dp[lft][rgt][player] = min(ret1 , ret2);
	}
	}
	int main()
	{
	long long sum = 0;
	memset(dp , -1 , sizeof(dp));
	cin>>n;
	for(int i=1 ; i<=n ; i++){
	cin>>ara[i];
	sum += ara[i];
	}
	long long fscore = FuN(1 , n , 1);
	long long sscore = sum - fscore;
	cout<<fscore - sscore<<endl;
	return 0;
	}

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

Iterative Solution:

১) যেহেতু, এটি ইন্টারভাল ডিপির প্রব্লেম তার মানে আমরা উক্ত অ্যারের ছোট ছোট সাব-অ্যারের জন্য প্রথমে প্রব্লেমটি সলভ করবো। এরপর, ছোট ছোট সাব-অ্যারের জন্য প্রাপ্ত ফলাফল কম্বাইন করে অপেক্ষাকৃত বড় সাব-অ্যারের জন্য ফলাফল বের করবো। এভাবে ধীরে ধীরে পুরো অ্যারের জন্য ফলাফল ক্যালকুলেট করতে হবে। 

২) dp[i][j] = Total Score of 1st player for a[i..j] - Total Score of 2nd player for a[i..j]

বিঃদ্রঃ এখানে, 1st Player বলতে আমি Taro কে বুঝাই নি। 1st Player বলতে বুঝানো হয়েছে, এই সাব-অ্যারের জন্য যে প্লেয়ার 1st move দিতে পারবে। অর্থাৎ, অ্যারে থেকে এখন পর্যন্ত বিজোড় সংখ্যক ভ্যালু কাটা হলে এই সাব-অ্যারের জন্য 1st Player হচ্ছে Jiro আর জোড় সংখ্যক ভ্যালু কাটা হলে 1st Player Taro

dp[i][j] = max(ara[i]-dp[i+1][j] , ara[j]-dp[i][j-1]

Here, ara[i] - dp[i+1][j] means

= ara[i] - (1st Player Score for a[i+1...j] - 2nd Player Score for a[i+1...j])

= ara[i] - 1st Player Score for a[i+1...j] + 2nd Player Score for a[i+1...j]

= (ara[i] + 2nd Player Score for a[i+1...j]) - 1st Player Score for a[i+1...j]

= 1st Player Score for a[i...j] - 2nd Player Score for a[i...j]

Did you notice that 2nd player of previous state now become 1st Player!

এবার কোড দেখে নেয়া যাকঃ 

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	ll ara[3005],dp[3005][3005];
	int main()
	{
	ll i,j,k,n,ans;
	cin>>n;
	for(i=1 ; i<=n ; i++) cin>>ara[i];
	for(ll sz = 1 ; sz <= n ; sz++){
	for(ll start=1 ; start <= n-sz+1 ; start++){
	ll ed = start+sz-1;
	dp[start][ed] = max(ara[start]-dp[start+1][ed] , ara[ed]-dp[start][ed-1]);
	}
	}
	cout<<dp[1][n]<<endl;
	return 0;
	}

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

Next Episode

Happy Coding