Timus - 1203 সমস্যা ও সমাধান

সমস্যার বিবরণ: এই প্রব্লেমে আমাদের n সংখ্যক event দেওয়া থাকবে। প্রতিটি even একটি নির্দিষ্ট সময়ে শুরু হবে এবং একটি নির্দিষ্ট সময়ে শেষ হবে। শুরু এবং শেষ দুটি সময়ই [1,30000] এই ব্যবধির integer হবে। আর n এর মানের ব্যবধি হল [1,100000]. 

আমরা event time overlap করে এমন কোন দুটি event এর যেকোনো একটিতে যোগদান করতে পারব। আমরা তাহলে maximum কয়টি event এ যোগদান করতে পারব সেটি বের করতে হবে। 

সমাধান: এটি একটি Basic Dynamic Programming problem. এখানে observation টি হচ্ছে সময় integer এবং এর maximum value 30000 হতে পারে। 

আমরা dp নামে একটি array রাখবো, যেখানে dp[ i ] এর value নির্দেশ করবে i-তম মিনিট বা তার আগে শেষ হয়ে যাওয়া event গুলোর মধ্যে maximum কয়টি event এ যোগদান করতে পারব সেটি। তাহলে আমরা dp[ 30000 ] এর value কে main answer হিসেবে print করতে পারব, তাই না? 

এখন আসা যাক আমরা এই dp array কে কিভাবে calculate করব। আমরা প্রথমে event গুলোকে তাদের শুরু হওয়ার সময় ধরে ascending order এ sort করে নিবো। 

এবার আমরা 1 থেকে 30000 মিনিটের উপর loop চালাবো। ধরি, এখন আমরা loop এর ভিতর j-তম মিনিটে আছি। এখন আমরা dp[ j ] এর value কে max(dp[ j ], dp[ j - 1 ]) দিয়ে update করব। কারণ dp[ j ] এর value j তম মিনিট বা তার আগে শেষ হয়ে যাওয়া সকল answer এর মধ্যে maximum কে নির্দেশ করে। 

এখন একেবারে মূল কাজটি বাকি। আমরা যখন j-তম মিনিটে আছি, তখন যদি আমরা দেখি যে i-তম event টি j-তম মিনিটে শুরু হচ্ছে, তবে আমরা ওই event এর end time এর জন্য dp[endtimei] এর value কে update করব max(dp[ j-1 ] + 1, dp[endtimei] ) দিয়ে। কারণ ( j-1 ) - তম মিনিটের পর আমরা শুধু i-তম event অর্থাৎ শুধু একটি event এ যোগদান করতে পারব যেটি endtimei পর্যন্ত চলবে, অথবা already যদি dp[endtimei] এর মান dp[j-1]+1 থেকে বড় হয়ে থাকে, তবে আমরা সেটিকেই consider করব। 

এভাবে আমাদের main answer টি dp[30000] এর মধ্যে calculated হয়ে store হয়ে যাবে। আসলে যে event টি সবার শেষে শেষ হবে, ওই শেষ মিনিট পর্যন্ত calculate করলেই আমাদের main answer হয়ে যায়। 

My Solution Code: 

#include<bits/stdc++.h> #define ll long long #define pb push_back using namespace std; int n; int dp[30004]; vector<pair<int,int> >vec; void input(); void solve(){     sort(vec.begin(),vec.end());     int i = 0;     int j = 1;     while(j<=30000){         int ff = vec[i].first;         int ss = vec[i].second;         dp[j] = max(dp[j],dp[j-1]);         if(ff==j){             dp[ss]=max(1+dp[j-1],dp[ss]);             i++;             continue;         }         j++;     }     cout<<dp[30000]<<"\n"; } void Clear(){ } int main(){     ios::sync_with_stdio(false);     cin.tie(0);     input();     solve();     Clear(); } void input(){     int n;     cin>>n;     for(int i=0;i<n;i++){         int u,v;         cin>>u>>v;         vec.pb({u,v});     } }

getline( ) দিয়ে space (' ') সহ string input নেওয়া

কিছু প্রব্লেমে আমাদের space (‘ ’) character সম্বলিত string input নিতে হয়। cin ব্যবহার করে সাধারণ string এর মতো আমরা এই ধরনের string input নিতে পারি না। এর জন্য আমরা getline() ব্যবহার করতে পারি। কোন string s কে input নেওয়ার জন্য getline(cin,s); - এই statement টি লিখলেই computer space (‘ ’) character সম্বলিত string input নিয়ে string s এর মধ্যে store করবে। এক্ষেত্রে কত গুলো character নিবে সে ব্যাপারে একটু খেয়াল রাখতে হবে। যতক্ষণ না পর্যন্ত ‘\n’ character পাবে, ততক্ষণ getline() ফাংশনটি character নিতে থাকবে। যদি আমরা cin ব্যবহার করে input নিয়ে থাকি তবে পরবর্তী line এ getline() ব্যবহার করে input নিলে একটি empty string store হয়ে যাবে। এই সমস্যা এড়ানোর জন্য আমাদের এই empty string কে আলাদা করে input নিতে হবে। যেমন, নিচের program টি লক্ষ করি।

#include<bits/stdc++.h> using namespace std; int main(){     string empty_string, s;     int n;     cin>>n;     getline(cin,empty_string);          getline(cin,s);          cout<<empty_string<<"\n";     cout<<s<<"\n"; }

Input: 5 Hello

Output: Hello

এই প্রোগ্রামে আমরা integer n কে input নেওয়ার পর নতুন line এ “Hello” input নিয়েছি। ফলে “Hello” input নেওয়ার আগে একটি ‘\n’ input হয়েছে। এর ফলে যে empty string আমরা পাচ্ছি সেটিকে আমরা getline(cin,empty_string) এর মাধ্যমে empty_string variable এ store করেছি। 

উপরের আলোচনা আমরা বুঝে থাকলে আর একটু মাথা খাটিয়ে Timus 1563 সমস্যাটির সমাধান করে ফেলতেই পারি, তাই না?