Light OJ - 1193 Tutorial | DP Series(Episode-21)

 Problem Description here

Problem:

এই প্রব্লেমে আমাদেরকে n সংখ্যক ডাইস দেয়া থাকবে। প্রতিটি ডাইসের k সংখ্যক তল থাকে যাদেরকে 1,2,3,....,k দ্বারা সংখ্যায়িত করা হয়। আমি ডাইসগুলো যেকোনভাবে সাজাতে পারি। সাজানোর পর যদি সকল ডাইসের উপরের তলের সংখ্যাগুলোর যোগফল S এর সমান হয় তবে স্কোর হবে উপরের তলের সংখ্যাগুলোর গুণফলের সমান। 

এখন, আমাকে যতোগুলো ভ্যালিড ওয়ে তে সাজানো যায় সবগুলোর জন্য স্কোর এর যোগফল হিসেব করতে হবে।

 

এই প্রব্লেমটি আমার সলভ করা ডিপি অপটিমাইজেশনের অন্যতম মজার একটি প্রব্লেম। এই প্রব্লেম সলভ করার আগে আমি ডিপি অপটিমাইজেশন নিয়ে যে পর্বগুলো লিখেছি সবগুলো পড়ে আসতে হবে। এবং DICE-1 প্রব্লেমটি সলভ করে আসতে হবে। 

DP Optimization-1

DP Optimization-2

DP Optimization-3

DP Optimization-4

Light OJ 1145

Solution:

১) Prerequisite গুলো পূরণ করে আসলে দুইটা প্রব্লেম ই সিমিলার মনে হবে শুরুতেই। DICE(I) এর সল্যুশনে প্রথম যে ফাংশনটি লিখেছিলাম আমি ঠিক সেরকম একটি ফাংশন লিখতে পারবা এই প্রব্লেমের জন্য যাতে ছোট Constraint এর জন্য কাজ করে? 

আগের প্রব্লেমের সল্যুশনে ২৯ নাম্বার লাইনটি কি ছিলো?

dp[i][j]  +=  dp[i][j-val]

এখন, এই লাইনটি পরিবর্তিত হয়ে হবেঃ

dp[i][j] += (val * dp[i+1][j-val]

২) এখন, আমরা ধীরে ধীরে অপটিমাইজেশনে যাবো। এখানেও আগের প্রব্লেমের মতো করেই থার্ড ইনার লুপ টা গায়েব করে দিতে হবে!!! আগের প্রব্লেমে আমরা শুধুমাত্র প্রিপিক্স সাম ব্যাবহার করে এই কাজটি করতে সফল হয়েছিলাম। এখানেও কি হবো?

৩) খুবভালোভাবে লক্ষ্য করলে দেখবে যে, এই থার্ড ইনার লুপ রিপ্লেস করতে গিয়ে আমাদের ছোটখাটো আরেকটি প্রব্লেম সলভ করতে হবে। কেমন? 

প্রব্লেমটা হচ্ছে মোটামুটি এরকম যে আমাকে একটি অ্যারে ara[n] দেয়া থাকবে। আমি এই অ্যারের x সাইজের একটি সাবঅ্যারের উপর কাজ করবো। আমাকে ঐ সাবঅ্যারের rightmost এলিমেন্ট কে 1 দ্বারা, 2nd rightmost এলিমেন্ট কে 2 দ্বারা, 3rd rightmost এলিমেন্ট কে 3 দ্বারা এভাবে xth rightmost এলিমেন্ট কে x দ্বারা গুণ করে সবগুলো গুণফলের যোগফল বের করতে হবে। 

এখন, আমাদের মূল চ্যালেঞ্জই হচ্ছে এই কাজটি O(1) কমপ্লেক্সিটি তে করা। তাহলেই আমরা এই প্রব্লেম সলভ করতে পারবো।

এখন, আমাকে একটি অ্যারে ara[n] দিয়ে দেয়া হবে। 

মনে কর, আমার কাছে দুইটি অ্যারে p[n] এবং q[n] আছে। এরা সকলেই 1-indexed অ্যারে। 

p[i] = p[i-1] + ara[i]

q[i] = q[i-1] + p[i]

এখন, আমরা ara[lb....ub] এই সাব-অ্যারের জন্য উপরোক্ত প্রব্লেমটি কিভাবে সলভ করতে পারি? 

এই সাব-অ্যারের জন্য এন্সার হবেঃ q[ub] - q[lb-1] - (sizeofsubarray * p[lb-1])

নিশ্চয়ই মাথার উপর দিয়ে গেছে! যাওয়া টা স্বাভাবিক। এই সাবপ্রব্লেমের সল্যুশন যেহেতু নিজে নিজে বের করোনি, অন্তত এই সল্যুশন কেন এবং কীভাবে কাজ করে সেটি নিজে নিজে বের করো।

যেহেতু তুমি DICE(I) প্রব্লেম সলভ করে এসেছো আমার কথামতো এবং এই প্রব্লেমের মূল চ্যালেঞ্জটিও অতিক্রম করে ফেলেছো, এখন তোমার উচিৎ সল্যুশন টি নিজে নিজে লিখা।

এরপরও ব্যার্থ হলে সল্যুশন দেখে নিতে পারো।

	#include<bits/stdc++.h>
	#define ll long long int
	#define ull unsigned long long int
	#define sc scanf
	#define scin(x) sc("%d",&(x))
	#define scin2(x,y) sc("%d %d",&(x),&(y))
	#define scln(x) sc("%lld",&(x))
	#define scln2(x,y) sc("%lld %lld",&(x),&(y))
	#define pf printf
	#define ms(a,b) memset(a,b,sizeof(a))
	#define MOD 100000007
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	ll dp[3][15009],prefix[15009],prefpref[15009];
	/**
	Here, dp[i][j] means sum of score to make summation of all faces = j, considering
	ith to nth item.
	prefix[j] means (dp[i+1][0] + dp[i+1][1] + --- + dp[i+1][j]).
	We can re-write prefix[j] = prefix[j-1] + dp[i+1][j]
	PrefPref[j] = PrefPref[j-1] + prefix[j] = (1 * dp[i+1][j]) + (2 * dp[i+1][j-1]) + (3 * dp[i+1][j-2]) + ---
	Now, we have to find out ((ub-lb+1)*dp[i+1][lb]) + ((ub-lb)*dp[i+1][lb+1]) + --- + (2*dp[i+1][ub-1]) + (1*dp[i+1][ub])
	How can we find it out in O(1) complexity?
	Actually this above sequence is equal to
	(PrefPref[ub] - PrefPref[lb-1] - ((NumberOfTerms * prefix[lb-1])%MOD) + MOD)%MOD
	**/
	ll FuN(ll n,ll k,ll s)
	{
	ms(dp , 0);
	dp[n+1][0] = 1;
	for(ll i=n ; i>=1 ; i--){
	for(ll j=1 ; j<=s ; j++){
	for(ll val=1 ; val<=k ; val++){
	if(j-val >= 0)
	dp[i][j] = (dp[i][j] + (val * dp[i+1][j-val])%MOD)%MOD;
	else
	break;
	}
	}
	}
	return dp[1][s];
	}
	ll Optimized1(ll n,ll k,ll s)
	{
	ms(dp , 0);
	ms(prefix , 0);
	ms(prefpref , 0);
	dp[n+1][0] = 1;
	prefix[0] = 1;
	prefpref[0] = 1;
	for(ll j=1 ; j<=s ; j++){
	prefix[j] = prefix[j-1] + dp[n+1][j];
	prefpref[j] = prefpref[j-1] + prefix[j];
	}
	for(ll i=n ; i>=1 ; i--){
	for(ll j=0 ; j<=s ; j++)
	dp[i&1][j] = 0;
	for(ll j=1 ; j<=s ; j++){
	ll lb = max(0LL , j-k);
	ll ub = max(0LL , j-1);
	ll increment = prefpref[ub];
	ll numberofterms = ub-lb+1;
	if(lb > 0){
	increment = (increment - prefpref[lb-1] + MOD)%MOD;
	increment = (increment - ((numberofterms * prefix[lb-1])%MOD) + MOD)%MOD;
	}
	dp[i][j] = increment;
	}
	for(ll j=0 ; j<=s ; j++){
	prefix[j] = 0;
	prefpref[j] = 0;
	if(j > 0){
	prefix[j] = prefix[j-1];
	prefpref[j] = prefpref[j-1];
	}
	prefix[j] = (prefix[j] + dp[i][j])%MOD;
	prefpref[j] = (prefpref[j] + prefix[j])%MOD;
	}
	}
	return dp[1][s];
	}
	ll Optimized2(ll n,ll k,ll s)
	{
	ms(dp , 0);
	ms(prefix , 0);
	ms(prefpref , 0);
	dp[(n+1) & 1][0] = 1;
	prefix[0] = 1;
	prefpref[0] = 1;
	for(ll j=1 ; j<=s ; j++){
	prefix[j] = prefix[j-1] + dp[(n+1) & 1][j];
	prefpref[j] = prefpref[j-1] + prefix[j];
	}
	for(ll i=n ; i>=1 ; i--){
	for(ll j=0 ; j<=s ; j++)
	dp[i & 1][j] = 0;
	for(ll j=1 ; j<=s ; j++){
	ll lb = max(0LL , j-k);
	ll ub = max(0LL , j-1);
	ll increment = prefpref[ub];
	ll numberofterms = ub-lb+1;
	if(lb > 0){
	increment = (increment - prefpref[lb-1] + MOD)%MOD;
	increment = (increment - ((numberofterms * prefix[lb-1])%MOD) + MOD)%MOD;
	}
	dp[i & 1][j] = increment;
	}
	for(ll j=0 ; j<=s ; j++){
	prefix[j] = 0;
	prefpref[j] = 0;
	if(j > 0){
	prefix[j] = prefix[j-1];
	prefpref[j] = prefpref[j-1];
	}
	prefix[j] = (prefix[j] + dp[i & 1][j])%MOD;
	prefpref[j] = (prefpref[j] + prefix[j])%MOD;
	}
	}
	return dp[1 & 1][s];
	}
	void Solve(int t)
	{
	ll i,j,k,n,s,ans;
	sc("%lld %lld %lld",&n,&k,&s);
	ans = Optimized2(n , k , s);
	pf("Case %d: %lld\n",t,ans);
	}
	int main()
	{
	int t,T;
	scin(T);
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw LOJ - 1193.cpp hosted with ❤ by GitHub

Happy Coding 😊