ফেসবুক এ ব্লগ লিখা বা কনটেস্ট করার সুবিধার্থে অনেকের সাথে কথা হয় । অনেকবারই অনুরোধ ছিল DP on tree নিয়ে যেন লিখি । Quora তে অনেক ভাল একটা পোস্ট আছে IIT Haydrabad এর ( লিঙ্ক ) যেইটা পড়লেই আসলে হয় , এইখানে অনেক variation নিয়ে লিখা হয়েছে । শুধু এই পোস্ট না উনাদের Data Structure এবং Graph Theory এর উপর অনেক ভাল কিছু পোস্ট আছে যা ফলো করা উচিত যারা সিরিয়াস কনটেস্ট করছে বা করতে চায় । IIT এর Threads এর পোস্ট এর পর আসলে DP on Tree এর উপর কিছু লিখার থাকে না তবুও অনেকের এর অনুরোধ ছিল যেন লিখি তাই আমার মত করে আমি বাংলায় একটা লিখার চেস্টা করছি।
DP on tree এই নামই বা কেন ? আসলে tree উপর ডিপি চালানো হয় বলে এই নাম । এইটা কোন ক্যাসিক্যাল প্রবলেম না মানে প্রবলেম এর উপর এর সল্ভ ট্যাকনিক ভিন্ন হইতে পারে ( একই রকম সল্যুশন প্যাটান নাই তবে কমন কিছু বৈশিষ্ট্য অবশ্যই আছে ) । যেহেতু ট্রি এর উপর ডিপি , লিফ নোড থেকে সহজেই ডিপেন্ডেন্সি মেইনট্যান্ট করা সম্ভব । প্রবলেমগুলার সলুশ্যন ম্যাক্সিমাম ক্ষেত্রেই রিকাশন রিলেশনের মাধ্যমে বের করতে সুবিধা হয় । ট্রি এবং রিকারশন ডিপি এইখানে ৩টা কমন জিনিস দেখা যায় ।
( ১ ) Base Case , leaf node এ থেকে কিছু হয় ।
( ২ ) parent node এর dp value তার child node or grand-child corresponding grand-child এর উপর নির্ভর করে ।
( ৩ ) রিকারশন ডিপি হওয়ার পরও যেহেতু ট্রি একটা নোড এর কল একবারই হয় , অনেক ক্ষেত্রেই memorization লাগে না ( yes !!! you read it right !!! ) normal dfs call এর মাধ্যমেই হয়ে যায় ।কারণ ট্রি বলে পার নোড এ একবারই কল হয় । দরকারে binary-search করা লাগতে পারে । তবে ডিপি মানেই সাব-প্রবলেম টাস্ক , এক নোডের রেজাল্ট তার চাইল্ড এবং গ্রেন্ড চাইল্ডের উপর নির্ভর করে ।
এখন আমরা কিছু প্রবলেম এর সল্যুশন ট্যাকনিক দেখার চেস্টা করব ।
PT07X - Vertex Cover :
DP on Tree এর ব্যাসিক প্রবলেম হিসাবে বুঝার জন্য কিভাবে tree dp গুলা কাজ করে এইটা খুবই ভাল একটা প্রবলেম । এই প্রবলেম এ আমাদের বলছে আমাদের একটা ট্রি এর edge list দেওয়া হবে আমাদের minimum node set নিতে হবে যাতে সবগুল edge এর কোন না কোন একটা end point থাকে , দুইটা end point থাকলে প্রবলেম নাই কিন্তু একটা অবশ্যই থাকতে হবে ।
প্রবলেম সল্ভ এর সব থেকে একটা key point হইল এইটা ট্রি , মানে যে কোন নোডই কোন না কোন একটা edge এর end point হবে । অর্থাৎ যদি আমরা কোন নোডকে না নিতে চাই তাহলে অবশ্যই আমরা এর সাথে যত নোড কোন একটা edge connection এ আছে তাদেরকে অবশ্যই নিতে হবে না হইলে আমাদের শর্ত মানা হবে না । যদি নেই তাহলে তার সাথে যে যে সব নোড edge connection এ আছে তাদেরকে নিতেই হবে এমন শর্ত আর থাকে না তাই তাদের কোনটি নিয়ে বা না নিয়ে minimum set টাই আমারা নিব ।
উপরের কোন এ dp[ ( node_number ) ][ 0 ] means করে এই নোডটা না নিয়ে এবং dp[ ( node_number ) ][ 1 ] means করে এই নোডটা নিয়ে কি কি পাওয়া হচ্ছে সেট ।
Anniversary party :
এই প্রবলেমটা অনেক মজার এবং basic DP on tree বুঝার জন্য অনেক ভাল একটা প্রবলেম । এইখানে n জন মানুষকে একটা পার্টিতে দাওয়াত দিতে হবে , এবং প্রতিটা মানুষ এর পার্টিটা জমাইয়া রাখার কিছু রেটিং পয়েন্ট আছে । আমাদের নরমাল লাইফে এ দেখা যায় কিছু মানুষ জন আছে যারা অনেক মজা করতে পারে , তারা কোন অনুষ্ঠানে থাকলে সবাই অনেক মজা পায় আবার কেউ কেউ অনেক গম্ভীর তাদের থাকা না থাকা একই ব্যাপার , আবার কেউ কেউ অনেক রাগী তারা না থাকলেই ভাল । এইখানে আরো একটা শর্ত দেওয়া আছে । যেহেতু এইটা একটা প্রতিষ্ঠানের পার্টি এইখানে কোন বস তার ইমেডিয়েট জুনিওর থাকলে ঐ পার্টিতে যায় না , জুনিওর এর ক্ষেত্রেও একই । মানে হইল হয় বস থাকবে না হয় জুনিওর থাকবে বা কেউই থাকবে না । আমাদের এমনভাবে পার্টি করার জন্য সবাইকে দাওয়াত দিতে হবে যেন পার্টিটা সব থেকে বেশী মজার হয় ।
উপরের প্রবলেমটার মত এই প্রবলেমও বেস কেইজ দুইটা । dp[ employee_number ][ 2 ] ;
dp[ employe_number ][ 0 ] ; // যদি কারেন্ট ইমপ্লোয়ি প্রেজেন্ট থাকে , তাহলে পার্টিতে হাইস্ট 'conviviality rating' কত হইতে পারে , dp[ employee ][ 1 ] ; // যদি তিনি না থাকেন তাহলে কি হইতে পারে।
এইখানে যখন আমরা dp[ employee_number ][ 0 ] নিয়ে নিব তখন অবশ্যই তার ইমেডিয়েন্ট জুনিওর 'U' হলে ও অবশ্যই নেওয়া যাবে না , কিন্তু ইমেডিয়েন্ট জুনিওর 'U' না নিয়ে যা পাওয়া গেছে তা এড হবে । কারণ এতে কোন প্রবলেম নাই ।
যদি আমরা current employee কে না নেই তাহলে আমরা অবশ্যই জুনিওর কে নিয়ে বা না নিয়ে যেইটা সবথেকে বেশী হয় এইটা এড করব ।
এই প্রবলেম দুইটা DP on tree বুঝার জন্য অনেক ভাল প্রবলেম । সামনে আরো লিখার মোটিভেশন পাইলে কিছু hard dp on tree নিয়ে লিখার ইচ্চা আছে ।
DP on tree এই নামই বা কেন ? আসলে tree উপর ডিপি চালানো হয় বলে এই নাম । এইটা কোন ক্যাসিক্যাল প্রবলেম না মানে প্রবলেম এর উপর এর সল্ভ ট্যাকনিক ভিন্ন হইতে পারে ( একই রকম সল্যুশন প্যাটান নাই তবে কমন কিছু বৈশিষ্ট্য অবশ্যই আছে ) । যেহেতু ট্রি এর উপর ডিপি , লিফ নোড থেকে সহজেই ডিপেন্ডেন্সি মেইনট্যান্ট করা সম্ভব । প্রবলেমগুলার সলুশ্যন ম্যাক্সিমাম ক্ষেত্রেই রিকাশন রিলেশনের মাধ্যমে বের করতে সুবিধা হয় । ট্রি এবং রিকারশন ডিপি এইখানে ৩টা কমন জিনিস দেখা যায় ।
( ১ ) Base Case , leaf node এ থেকে কিছু হয় ।
( ২ ) parent node এর dp value তার child node or grand-child corresponding grand-child এর উপর নির্ভর করে ।
( ৩ ) রিকারশন ডিপি হওয়ার পরও যেহেতু ট্রি একটা নোড এর কল একবারই হয় , অনেক ক্ষেত্রেই memorization লাগে না ( yes !!! you read it right !!! ) normal dfs call এর মাধ্যমেই হয়ে যায় ।কারণ ট্রি বলে পার নোড এ একবারই কল হয় । দরকারে binary-search করা লাগতে পারে । তবে ডিপি মানেই সাব-প্রবলেম টাস্ক , এক নোডের রেজাল্ট তার চাইল্ড এবং গ্রেন্ড চাইল্ডের উপর নির্ভর করে ।
এখন আমরা কিছু প্রবলেম এর সল্যুশন ট্যাকনিক দেখার চেস্টা করব ।
PT07X - Vertex Cover :
DP on Tree এর ব্যাসিক প্রবলেম হিসাবে বুঝার জন্য কিভাবে tree dp গুলা কাজ করে এইটা খুবই ভাল একটা প্রবলেম । এই প্রবলেম এ আমাদের বলছে আমাদের একটা ট্রি এর edge list দেওয়া হবে আমাদের minimum node set নিতে হবে যাতে সবগুল edge এর কোন না কোন একটা end point থাকে , দুইটা end point থাকলে প্রবলেম নাই কিন্তু একটা অবশ্যই থাকতে হবে ।
প্রবলেম সল্ভ এর সব থেকে একটা key point হইল এইটা ট্রি , মানে যে কোন নোডই কোন না কোন একটা edge এর end point হবে । অর্থাৎ যদি আমরা কোন নোডকে না নিতে চাই তাহলে অবশ্যই আমরা এর সাথে যত নোড কোন একটা edge connection এ আছে তাদেরকে অবশ্যই নিতে হবে না হইলে আমাদের শর্ত মানা হবে না । যদি নেই তাহলে তার সাথে যে যে সব নোড edge connection এ আছে তাদেরকে নিতেই হবে এমন শর্ত আর থাকে না তাই তাদের কোনটি নিয়ে বা না নিয়ে minimum set টাই আমারা নিব ।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //BISMILLAHIRRAHMANIRRAHIM | |
| /* | |
| manus tar shopner soman boro | |
| Author :: Shakil Ahmed | |
| .............AUST_CSE27......... | |
| prob :: | |
| Type :: | |
| verdict:: | |
| */ | |
| #include <bits/stdc++.h> | |
| #define pb push_back | |
| #define mp make_pair | |
| #define pi acos(-1.0) | |
| #define ff first | |
| #define ss second | |
| #define re return | |
| #define QI queue<int> | |
| #define SI stack<int> | |
| #define SZ(x) ((int) (x).size()) | |
| #define all(x) (x).begin(), (x).end() | |
| #define sqr(x) ((x) * (x)) | |
| #define ms(a,b) memset((a),(b),sizeof(a)) | |
| #define G() getchar() | |
| #define MAX3(a,b,c) max(a,max(b,c)) | |
| #define II ( { int a ; read(a) ; a; } ) | |
| #define LL ( { Long a ; read(a) ; a; } ) | |
| #define DD ({double a; scanf("%lf", &a); a;}) | |
| double const EPS=3e-8; | |
| using namespace std; | |
| #define FI freopen ("t.txt", "r", stdin) | |
| #define FO freopen ("output.txt", "w", stdout) | |
| typedef long long Long; | |
| typedef long long int64; | |
| typedef unsigned long long ull; | |
| typedef vector<int> vi ; | |
| typedef set<int> si; | |
| typedef vector<Long>vl; | |
| typedef pair<int,int>pii; | |
| typedef pair<string,int>psi; | |
| typedef pair<Long,Long>pll; | |
| typedef pair<double,double>pdd; | |
| typedef vector<pii> vpii; | |
| // For loop | |
| #define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i) | |
| #define rep(i, n) forab (i, 0, (n) - 1) | |
| #define For(i, n) forab (i, 1, n) | |
| #define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i) | |
| #define per(i, n) rofba (i, 0, (n) - 1) | |
| #define rof(i, n) rofba (i, 1, n) | |
| #define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i) | |
| template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); } | |
| template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); } | |
| //Fast Reader | |
| template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;} | |
| //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction | |
| //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction | |
| //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction | |
| //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction | |
| /* ************************************** My code start here ****************************************** */ | |
| const int MX = 100000 + 10 ; | |
| vector < int > adj[MX]; | |
| int dp[MX][2]; | |
| void dfs(int x , int par) | |
| { | |
| dp[x][0] = 0 ; | |
| dp[x][1] = 1 ; | |
| int sz = adj[x].size(); | |
| rep ( i , sz ) | |
| { | |
| int v = adj[x][i]; | |
| if ( v == par ) continue ; | |
| dfs(v,x); | |
| dp[x][0] += dp[v][1]; | |
| dp[x][1] += min(dp[v][1] , dp[v][0]); | |
| } | |
| } | |
| 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 | |
| //FI ; | |
| // FO ; | |
| int n = II ; | |
| rep ( i , n - 1 ) | |
| { | |
| int x = II ; | |
| int y = II ; | |
| adj[x].pb(y); | |
| adj[y].pb(x); | |
| } | |
| dfs(1,-1); | |
| printf("%d\n",min(dp[1][0] , dp[1][1] ) ); | |
| return 0; | |
| } |
উপরের কোন এ dp[ ( node_number ) ][ 0 ] means করে এই নোডটা না নিয়ে এবং dp[ ( node_number ) ][ 1 ] means করে এই নোডটা নিয়ে কি কি পাওয়া হচ্ছে সেট ।
Anniversary party :
এই প্রবলেমটা অনেক মজার এবং basic DP on tree বুঝার জন্য অনেক ভাল একটা প্রবলেম । এইখানে n জন মানুষকে একটা পার্টিতে দাওয়াত দিতে হবে , এবং প্রতিটা মানুষ এর পার্টিটা জমাইয়া রাখার কিছু রেটিং পয়েন্ট আছে । আমাদের নরমাল লাইফে এ দেখা যায় কিছু মানুষ জন আছে যারা অনেক মজা করতে পারে , তারা কোন অনুষ্ঠানে থাকলে সবাই অনেক মজা পায় আবার কেউ কেউ অনেক গম্ভীর তাদের থাকা না থাকা একই ব্যাপার , আবার কেউ কেউ অনেক রাগী তারা না থাকলেই ভাল । এইখানে আরো একটা শর্ত দেওয়া আছে । যেহেতু এইটা একটা প্রতিষ্ঠানের পার্টি এইখানে কোন বস তার ইমেডিয়েট জুনিওর থাকলে ঐ পার্টিতে যায় না , জুনিওর এর ক্ষেত্রেও একই । মানে হইল হয় বস থাকবে না হয় জুনিওর থাকবে বা কেউই থাকবে না । আমাদের এমনভাবে পার্টি করার জন্য সবাইকে দাওয়াত দিতে হবে যেন পার্টিটা সব থেকে বেশী মজার হয় ।
উপরের প্রবলেমটার মত এই প্রবলেমও বেস কেইজ দুইটা । dp[ employee_number ][ 2 ] ;
dp[ employe_number ][ 0 ] ; // যদি কারেন্ট ইমপ্লোয়ি প্রেজেন্ট থাকে , তাহলে পার্টিতে হাইস্ট 'conviviality rating' কত হইতে পারে , dp[ employee ][ 1 ] ; // যদি তিনি না থাকেন তাহলে কি হইতে পারে।
এইখানে যখন আমরা dp[ employee_number ][ 0 ] নিয়ে নিব তখন অবশ্যই তার ইমেডিয়েন্ট জুনিওর 'U' হলে ও অবশ্যই নেওয়া যাবে না , কিন্তু ইমেডিয়েন্ট জুনিওর 'U' না নিয়ে যা পাওয়া গেছে তা এড হবে । কারণ এতে কোন প্রবলেম নাই ।
যদি আমরা current employee কে না নেই তাহলে আমরা অবশ্যই জুনিওর কে নিয়ে বা না নিয়ে যেইটা সবথেকে বেশী হয় এইটা এড করব ।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //BISMILLAHIRRAHMANIRRAHIM | |
| /* | |
| manus tar shopner soman boro | |
| all my suceesses are dedicated to my parents | |
| The true test of a man's character is what he does when no one is watching. | |
| Don't let your dreams be dreams. | |
| Author :: Shakil Ahmed | |
| .............AUST_CSE27......... | |
| prob :: | |
| Type :: | |
| verdict:: | |
| */ | |
| #include <bits/stdc++.h> | |
| #define pb push_back | |
| #define mp make_pair | |
| // Macro | |
| #define eps 1e-9 | |
| #define pi acos(-1.0) | |
| #define ff first | |
| #define ss second | |
| #define re return | |
| #define QI queue<int> | |
| #define SI stack<int> | |
| #define SZ(x) ((int) (x).size()) | |
| #define all(x) (x).begin(), (x).end() | |
| #define sq(a) ((a)*(a)) | |
| #define distance(a,b) (sq(a.x-b.x) + sq(a.y-b.y)) | |
| #define iseq(a,b) (fabs(a-b)<eps) | |
| #define eq(a,b) iseq(a,b) | |
| #define ms(a,b) memset((a),(b),sizeof(a)) | |
| #define G() getchar() | |
| #define MAX3(a,b,c) max(a,max(b,c)) | |
| #define II ( { int a ; read(a) ; a; } ) | |
| #define LL ( { Long a ; read(a) ; a; } ) | |
| #define DD ({double a; scanf("%lf", &a); a;}) | |
| double const EPS=3e-8; | |
| using namespace std; | |
| #define FI freopen ("1.txt", "r", stdin) | |
| #define FO freopen ("2.txt", "w", stdout) | |
| typedef long long Long; | |
| typedef long long int64; | |
| typedef unsigned long long ull; | |
| typedef vector<int> vi ; | |
| typedef set<int> si; | |
| typedef vector<Long>vl; | |
| typedef pair<int,int>pii; | |
| typedef pair<string,int>psi; | |
| typedef pair<Long,Long>pll; | |
| typedef pair<double,double>pdd; | |
| typedef vector<pii> vpii; | |
| // For loop | |
| #define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i) | |
| #define rep(i, n) forab (i, 0, (n) - 1) | |
| #define For(i, n) forab (i, 1, n) | |
| #define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i) | |
| #define per(i, n) rofba (i, 0, (n) - 1) | |
| #define rof(i, n) rofba (i, 1, n) | |
| #define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i) | |
| template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); } | |
| template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); } | |
| #define __(args...) {dbg,args; cerr<<endl;} | |
| struct debugger{template<typename T> debugger& operator , (const T& v){cerr<<v<<"\t"; return *this; }}dbg; | |
| #define __1D(a,n) rep(i,n) { if(i) printf(" ") ; cout << a[i] ; } | |
| #define __2D(a,r,c,f) forab(i,f,r-!f){forab(j,f,c-!f){if(j!=f)printf(" ");cout<<a[i][j];}cout<<endl;} | |
| template<class A, class B> ostream &operator<<(ostream& o, const pair<A,B>& p){ return o<<"("<<p.ff<<", "<<p.ss<<")";} //Pair print | |
| template<class T> ostream& operator<<(ostream& o, const vector<T>& v){ o<<"[";forstl(it,v)o<<*it<<", ";return o<<"]";} //Vector print | |
| template<class T> ostream& operator<<(ostream& o, const set<T>& v){ o<<"[";forstl(it,v)o<<*it<<", ";return o<<"]";} //Set print | |
| //Fast Reader | |
| template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;} | |
| //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction | |
| //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction | |
| //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction | |
| //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction | |
| /* ************************************** My code start here ****************************************** */ | |
| const int NX = 1e6 ; | |
| int dp[2][ NX ] , n , inp[NX] , parnt[NX]; | |
| vector < int > adj[ NX ]; | |
| void ini() | |
| { | |
| for( int i = 0 ; i <= n + 1 ; i++ ) | |
| { | |
| adj[i].clear(); | |
| dp[0][i] = dp[1][i] = 0; | |
| parnt[i] = -1 ; | |
| } | |
| } | |
| void dfs( int x ) | |
| { | |
| int sz = adj[x].size(); | |
| dp[0][x] = max( 0 , inp[x] ) ; | |
| for( int i = 0 ; i < sz ; i++ ) | |
| { | |
| int u = adj[x][i]; | |
| dfs(u); | |
| dp[0][x] += max( 0 , dp[1][u] ); // from his grand child | |
| dp[1][x] += max( 0 , max( dp[1][u] , dp[0][u] ) ); | |
| } | |
| } | |
| 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 | |
| while( scanf("%d",&n) == 1 ) | |
| { | |
| ini(); | |
| for( int i = 1 ; i <= n ; i++ ) inp[i] = II ; | |
| int x , y ; | |
| while( scanf("%d %d",&x,&y) == 2 ) | |
| { | |
| if( x == 0 && y == 0 ) break ; | |
| adj[y].pb(x); | |
| parnt[x] = y ; | |
| } | |
| int root ; | |
| int ans = 0 ; | |
| for( int i = 1 ; i <= n ; i++ ) | |
| { | |
| if( parnt[i] == -1 ) | |
| { | |
| dfs( i ); | |
| ans += max( dp[0][i] , dp[1][i] ); | |
| } | |
| } | |
| printf("%d\n",ans); | |
| } | |
| return 0; | |
| } |
এই প্রবলেম দুইটা DP on tree বুঝার জন্য অনেক ভাল প্রবলেম । সামনে আরো লিখার মোটিভেশন পাইলে কিছু hard dp on tree নিয়ে লিখার ইচ্চা আছে ।
