নতুন ইউটিভ চ্যানেল স্টার্ট

এই ব্লগটা যখন শুরু করা হয় তখন আমি ভার্সিটিতে পড়তাম । ভার্সিটিতে আমি কনটেস্ট ট্রনিং প্রোগ্রামের সাথে যুক্ত ছিলাম । মাঝেমধ্যেই জুনিওরদের ক্লাস নিতাম, কিছু সময়ের জন্য আহসানউল্লাহ ইউনিভার্সিটির ট্রেইনারও ছিলাম। ব্লগ স্টার্ট করার একটা মোটিভেশন ছিল আমি যা ক্লাস নিতেছি তা যেন পরবর্তী সময়ে যে কেউ চাইলে আবার দেখে নিতে পারে প্লাস বাংলাতে প্রোগ্রামিং কনটেস্টের জন্য ব্লগ বলতে ফাহিম ভাইয়া আর সাফায়াত ভাইয়ার ব্লগ ছিল , অবশ্যই সেগুলা অনেক ভাল ছিল তাও আমার কাছে মনে হইত আমার নিজেরও কিছু কনট্রিভিউট করা উচিত তাই এই ব্লগ । এখন যেহেতু আমি সফটওয়্যার ফার্মে জব করতেছি আবার আমি উইকেন্ডে  সাউথ ইস্ট ইউনিভার্সিটিতে ক্লাসও নেই ।  আমার এখন  আর কনটেস্ট প্রোগ্রামিং এ সময় দেওয়া হয় না আবার কিছু লিখাও হয় না । যদিও একসময় এই জিনিসটা আমি অনেক উপভোগ করতাম । ভার্সিটিতে ক্লাস নেওয়ার একটা সুবিধা হইছে এখন আবার আগে পড়া বিসয়সমুহ দেখা হচ্ছে । বিগত কয়েক সেমিস্টার যাবত আমার ছাত্র-ছাত্রীদের একটা ডিমান্ড হচ্ছে ওদের ক্লাসের টপিক ইউটিউভ এ ভিডিও করে কেন দেওয়া হয় না তাতে তাদের অনেক সুবিধা হয় । ভিডিও ম্যাকিং , এডেটিং প্লাস এক্সট্রা আরোও কিছু সময় দেওয়াতে আমার সব সময় অনেক আলসামি  কাজ করে এবং এতদিন জিনিসটা আমি না করেই পার পাইতে চাচ্ছিলাম  আর এইসব ব্যাপারে আমার আগ্রহ বা ইচ্ছার ও ঘাটতি আছে । এই সিমিস্টারে নানা সমস্যার কারণে অনেক ক্লাস মিস হচ্ছিল এবং স্বাভাবিকভাবেই সিলাবাসের সব পড়ানো যাচ্ছিল না , তাই কিছুটা বাধ্য হয়েই আমার ভিডিও বানাইতে হচ্ছে, ক্লাসের টপিক এবং খুবই ব্যাসিক এলগরিদমের । ক্লাসে সবার সাথে কথা বলতে বলতে একটা অভ্যাস হয়ে গেলেও স্কিন কাস্ট করে কিছু বানাইতে গেলে অনেক বিপত্তি । আর আমি নিজে খুব গুছিয়ে কথাও বলতে পারি বলে আমার মনে হয় , কথা বলার সময় অনেক জড়তা কাজ করে । যাই হোক আমি কিছু ভিডিও করা ফেলছি , কোন প্রকার এডেটিং কিছু করা ছাড়া যেহেতু আমি এইসব কিছু পারি না । সাউথ ইস্ট ইউনিভার্সিটিতে মিড এর পর যে টপিকগুলা পড়ানোর কথা ছিল এই গুলানিয়ে মুলত ভিডিও বানানো হইছে, আমার এই ব্লগ অনেকেই দেখি অনুসরণ করেন । হয়তো তাদের সবাই কনটেস্ট প্রোগ্রামিং এর সাথে যুক্ত । সমালোচনা মানুসজনকে আরোও ভাল করে তুলে, যেহেতু স্টুডেন্ট এর জন্য বানানো তাই তারা খুব একটা সমালোচনা করতেছে না, তাই এইখানে আমার চ্যানেলের লিংক দেওয়া , যারা ব্লগটা ফলো করেন তাদের সমালোচনা কাম্য , চ্যানেলের লিঙ্ক 

প্রোগ্রামিং কনটেস্ট , হতাশা এবং আমি

কয়দিন আগে ফেসবুক এ ফান থেকে সারাহ তে একাউন্ট খুলেছিলাম । সেখানে যতগুলা প্রশ্ন বা মন্তব্য পাইছি তার ২০% এর মত ছিল প্রোগ্রামিং কনটেস্ট নিয়ে সাজেশন বা হতাশা নিয়ে । ফেসবুক এ ও মাঝে মধ্যেই আমি এই রকম মেসেস পাই । কনটেস্ট করছি অনেকদিন কিন্তু ভাল হচ্ছে না , আমাকে দিয়ে কিছু হবে না । এখন কি কনটেস্ট করা ছেড়ে দিব , কনটেস্ট করতে গিয়ে সিজিপিএ তো বারটা বাজাইছি । আমি নিজে যখন এক্টিভ ভাবে প্রোগ্রামিং কনটেস্ট করতাম তখন এই ব্যাপারে কথা বলতে চাওয়া আমার নিজের কাছে কিছুটা বিব্রতকর লাগত কারণ আমি খুব একজন সাকসেসফুল কনটেস্টেইন না , এখন যদিও আমার চিন্তা ভাবনার অনেক চ্যাঞ্জ হয়েছে । সত্যিকার ভাবে বলতে অনেক হইছে আমার কাছে লাগে । আমি এখন লাইফটাকে যে ভাবে দেখি বা যে জিনিসগুলা মনে হয় এখন ইম্পরট্যান্ট তা কয়েক বছর আগেও অন্য রকম ছিল ।

আমি  লাইফে যা কিছু করতে চাই তা সঠিকভাবে করতে পারার জন্য নিচের সবগুলা পয়েন্ট এর উত্তর আমার কাছে মনে হয় জানা থাকা দরকার ।

১) লাইফে কি চাই এবং তা কেন চাই এর সম্পূর্ণ ক্লিয়ার ধারণা আমার কাছে আছে কিনা ।
২ ) যা চাই তা কিভাবে আমি পেতে পারি এইটা আমি জানি কিনা ।
৩ ) তা কিভাবে পাব এবং এর জন্য যে যে স্কিল আমার থাকা দরকার তা আমার আছে কিনা এবং যদি না থাকে তাহলে সময়ের সাথে সাথে আমি তা নিজের মধ্যে ডেভেলপ করতে পারব কিনা ।
৪ ) যদি উপরের সবগুলা পয়েন্ট আমার কাছে ক্লিয়ার থাকে এবং আমি যা চাই তা পেতে চাই তার জন্য যা যা করা দরকার, তা একটা লং টাইম হতাশ না হয়ে করার মত সক্ষমতা আমার কাছে আছে কিনা ।

এখন ধরি আমি চাই আমি অনেক ভাল প্রোগ্রামিং কনটেস্টেইন হবে । এর জন্য আমরা এক এক করে সবগুলা পয়েন্ট দেখি ।

প্রথম পয়েন্ট এ আমি জানি আমি কি চাই এখন প্রশ্ন হল তা কেন চাই । অনেকের কাছে এর অনেক উত্তর থাকতে পারে । কেউ যদি আগামীতে ভাল একটা জবের জন্য প্রোগ্রামিং কনটেস্ট করা অনেক উপকার দিবে মনে হয়, হয়তো এইটা অনেকাংশে ঠিক আছে । প্রোগ্রামিং কনটেস্ট যেহেতু অনেক কঠিন একটা প্রসেস যারা অনেক সময় ধরে এইটার সাথে থাকে তাদের জন্য জব পাইতে এইটা অনেক হ্যাল্প করে এবং সত্যিকার ভাবেই যারা কনটেস্ট প্রোগ্রামিং করে তাদের জন্য দেশে এবং বাহিরের অনেক অনেক ভাল কোম্পানিতে জব পাওয়া অনেক সহজ হয়ে যায় । কিন্তু এইটা ঠিক না যারা কনটেস্ট প্রোগ্রামিং করেন না তাদের কিছুই হবে না । জব ইন্টাভিউ এর জন্য যে সব প্রশ্ন জিজ্ঞাসা করা হয় তা ৬ - ৮ মাস ভাল ভাবে প্রাক্ট্রিস  করে পারা সম্ভব বলে আমার মনে হয় । তার চেয়ে প্রোগ্রামিং কনটেস্ট অনেক বেশী কঠিন কঠিন প্রবলেম সল্ভ করতে হয় তা অনেক পেইনফুল একটা জিনিস । এবং সত্যিকার অর্থেই যখন কেউ কোন প্রবলেম সল্ভ করতে পারে না এই ফিনিংশটা মোটেই ভাল কিছু না । তবে আমার নিজের কাছে এখন মনে হয় সিএসই তে যদি কারো ক্যারিয়ার করার ইচ্ছা থাকে এইটা সফটওয়্যার ফার্ম থেকে ভার্সিটির শিক্ষক বা একজন researcher সবার জন্যই লাইফে ১ থেকে ২ বছর কনটেস্ট প্রোগ্রামিং এর সাথে যুক্ত থাকা উচিত । এইখানে যে রকম মেন্টাল পেইন প্লাস নতুন নতুন জিনিস শিখার সুযোগ হয় তা সব কিছুতেই পরে অনেক হ্যাল্পফুল হবে ।

দ্বিতীয় পয়েন্ট কিভাবে ভাল কনটেস্ট প্রোগ্রামার হব ? প্রথমত কনটেস্ট এ allow করে এমন একটা প্রোগ্রামিং ল্যাঙ্গুয়েজ আমাকে ভালভাবে জানতে হবে যেইটাতে আমি কোন প্রবলেম এর সলুশ্যন পাইলে কোন প্রবলেম ছাড়াই তাতে কোড করে ফেলতে পারি । আমাকে অনেক আল্গরিথম , ট্রিক্স জানতে হবে । কোড অপিটিমাইস কিভাবে করতে হয় জানতে হয় যদি আইসিপি এর টার্গেট থাকে কিভাবে টিম করে প্রবলেম সল্ভ করতে হয় তা জানতে হবে এবং অনেক অনেক ভাল কঠিন এবং যে প্রবলেম গুলা সল্ভ করলে অনেক নতুন কিছু শিখা যায় তার সোর্স জানতে হবে এবং কিছু ভাল ফ্রেন্ড করতে হবে । এইসব ভাল ফ্রেন্ড শুধু নিজের ভার্সিটি না অন্য ভার্সিটি এমনকি বাহিরের দেশের মানুষজনও হইতে পারে। Don't just work hard, work smartly. একই রকম প্রবলেম ১০০টা সল্ভ করে কোন লাভ নাই তার চেয়ে ২/৩ ধরনের ৫টা প্রবলেম করেও অনেক কিছু শিখা যাইতে পারে এইটাও বুঝতে হবে।

আমার কাছে তৃতীয় পয়েন্ট টা অনেক গুরুত্বপূর্ণ মনে হয় । আমি নিজে যদি চার ফুট হাইট এর কেউ হই এবং আমার নিজের লক্ষ্য যদি থাকে আমি এনবিএ এর টপ বাস্ককেট বল প্লেয়ার হব অবশ্যই এইটা হওয়া টেন্স টু ইম্পসিবল । অনেক অনেক ভাল কঠিন প্রবলেম সল্ভ করার পরও বা করতে চেস্টা করার পরও অনেকে পক্ষে ভাল কনটেস্টেইন প্রোগ্রামার হওয়া সম্ভব নাও হইতে পারে। কোন সময়ই পেনিক না করা , সব সময় শান্ত থাকা এবং কোন প্রবলেম এর সল্যুশন বের করার জন্য সম্পূর্ণ আলাদা কয়ভাবে চিন্তা করতে পারাও অনেক গুরুত্বপূর্ণ । যেগুলা আসলে কেউ যদি চায় তবে নিজের মধ্যে ডেভেলপ করতে পারে । যার অনেক পেনিক হওয়ার অভ্যাস আছে বা  অল্পতেই মাথা গরম হয়ে যায় তার মেডিটেশন ট্রাই করা যদি । ধর্মীয় প্রাথনাও আমাদের অনেক শান্ত  এবং ধীরস্থির করে । ভাল কোডারদের কোড পড়ার অভ্যাস আমাদের একই প্রবলেম এর জন্য কিভাবে অন্য কয়েকভাবে চিন্তা করা যায় তা শিখায় । প্রবলেম নিয়ে ফ্রেন্ডদের সাথে আলাপ-আলোচনা থেকেও জিনিসগুলা শিখা যায় এবং অবশ্যই এর জন্য অন্যদের কথা শুনার অভ্যাস থাকতে হবে ।


উপরের সবগুলা পয়েন্ট ঠিকমত করার পরও আমি হয়তো ভাল কনটেস্ট প্রোগ্রামার নাও হইতে পারি যদি চার নাম্বার পয়েন্ট টা ঠিক ঠিক আল্পাই না করি । কনটেস্ট লাইফে অনেক হতাশা হবে , অনেক প্রবলেম ২/৩ দিন কি ৭/১০ দিন বা ১/২ মাসেও সল্ভ হবে না , টিমমেট প্রেম করা স্টার্ট করে কনটেস্ট ছেড়ে দিতে পারে কিন্তু তাও  দিনের পর দিন জিনিসগুলার ট্রাই করে যাওয়ার মানসিকতা থাকতে হবে । আমার মনে হয় ভাল কনটেস্টেইন হওয়ার জন্য অনেক আশাবাদি মানুষও হইতে হবে । লাস্ট মিনিটেও সল্ভ হইতে পারে এই আশা নিয়ে প্রবলেম সাবমিট করতে হবে । প্রোগ্রামিং কনটেস্ট এ ভাল রেজাল্ট কখন আসবে বা কখনই আসবে কিনা এর কোন আন্সার নাই । কেউ হয়তো মাত্র ৬/৮ মাসে অনেক ভাল ভাল রেজাল্ট পাইতে শুরু করতে পারে আবার কারো জন্য এইটা ২/৩ বছর পর গিয়েও হইতে পারে। আর লাইফে  সাফল্য নাও আসতে পারে । সাফল্য আসা এইটাও কি খুব একটা গুরুত্বপূর্ণ । কনটেস্ট করার টাইমে এইটা নিয়ে মন খারাপ থাকতে পারে । লাইফে কনটেস্ট করার শেষ করা পর যে এক্সপেরিয়াস পাওয়া হইছে, কনটেস্ট নিয়ে লাইফে যা ফান ইভেন্ট আছে এইসব মনে করে কোন একটা খারাপ সন্ধ্যা মুহূর্তেই ভাল হয়ে যাইতে পারে।  লাইফে অনেক সাকসেসফুল হবার চিন্তা করে বসে থাকলে সাকসেসফুল হওয়া যায় না তার চেয়ে কি কি প্রসেস নিয়মিত  ফলো করে গেলে আমরা তার কাছাকাছি যাইতে পারি এইটা সবথেকে গুরুত্বপূর্ণ ভুমিকা রাখে।



আমি লিখাটা শুরুতে লিখছিলাম ১/২ বছর আগেও যা আমি ভাবতাম এখন আমার চিন্তাভাবনার অনেক চ্যাঞ্জ আসছে । আমার কাছে এখন মনে হয় কোন একটা খারাপ কনটেস্ট করে যদি আমার মন-মেজাজ অনেক বেশী খারাপ হয়ে যায় যার ফলে আমার কাছে মানুসজনের সাথে আমি খারাপ ব্যাবহার করি তাহলে আমার কনটেস্ট না করাই ভাল । যতদিন পর্যন্ত না আমি আমার ভিন্ন ভিন্ন ইমোশনগুলাকে কিভাবে ঠিক করতে হয় তা নিজের মধ্যে ডেভেলপ করতে পারি । ভার্সিটি লাইফে আমার নিজের কাছে হয়তো কনটেস্টেই ছিল সব কিন্তু এখন মনে হয় আরো একটু সিরিয়াস বা অন্ধ না হইলে হয়তো সিজিপিএ টাও আরো একটু ভাল হইত । ভার্সিটি লাইফে আমি আমার ফাইনাল এক্সাম এর আগে দিন ন্যাশনাল কনটেস্ট করতে গেছি , সিএফ থাকলে তো কোনদিনও বাদ দেই নাই কিন্তু আগে থেকে যেহেতু সবকিছু গুছিয়ে রাখার অভ্যাস নাই মাঝখান থেকে ঐসব এক্সাম আমার খারাপই হইছে । এখন যা লাইফ থেকে চাই তার জন্য ব্যাপারগুলা নিয়ে একটি খারাপ লাগাও আছে , আরো ভাল সিজিপিএ আমি রাখতে পারতাম । নিয়মিত ক্লাস করলে , এক্সাম দিলে এবং স্যারদের কথা শুনলে অবশ্যই একটা ভাল গ্রেড পাওয়ার জন্য খুব একটা কস্ট করা লাগে না ।


মানুষ তার স্বপ্নের সমান বড় । আমরা লাইফে যা পেতে চাই আর জন্য কোন initiative না নেই আমরা কখনই তা পাব না । আমাদের লাইফে যা কিছু হয় বা হবে তার জন্য আমাদের আগে থেকে নেওয়া এবং এখন যে যে ছোট ছোট ডিসিশন নিব তা গুরুত্বপূর্ণ ভুমিকা রাখে । যদি কনটেস্ট প্রোগ্রামিং ভাল না লাগে কিন্ত সবাই করে আমাকেও করতে হবে এই মনোভাব নিয়ে কনটেস্ট করে গেলে কনটেস্ট প্রোগ্রামিং এ হয়তো বা খুব একটা ভাল করা হবে না তার চেয়ে যেইটা ভাল লাগে এইটা করা উচিত । ঐখানে সফলতা না আসলে একটা ভাল লাগা থেকে যাবে । সবার জীবন সুন্দর হোক ।

DP on Tree

ফেসবুক এ ব্লগ লিখা বা কনটেস্ট করার সুবিধার্থে অনেকের সাথে কথা হয় । অনেকবারই অনুরোধ ছিল 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 নিয়ে লিখার ইচ্চা আছে । 

0/1 BFS

shortest path বের করার গ্রাফ এর আল্গরিথম গুলোকে দুই ভাবে ভাগ করা যায় ।

   ১। এক নোড থেকে অন্য নোডে যাবার cost ১ ।
   ২। এক নোড থেকে অন্য নোডে যাবার cost যে কোন কিছু হইতে পারে।

যদি এক নোড থেকে অন্য নোডে যাবার cost ১ হয় তাহলে  এই প্রবলেম গুলা bfs বা dfs দিয়ে সল্ভ করা হয় যদি cost যে কোন কিছু হয় তাহলে floyd-warshal , Dijkstra বা Bellmanford ব্যাবহার করা হয় , যদি নেগেটিভ হয় cost তাহলে Bellmanford ব্যাবহার করা ।

bfs এর একটা ভ্যারিয়েশন হচ্ছে 0/1 bfs .  এইখানে এক নোড থেকে অন্য নোডে যাবার cost 0 বা ১ হতে পারে ।সচরাচর আমরা bfs এর প্রবলেম  এ queue ব্যাবহার করি , এইখানে আমরা করব deque .  যদি current node থেকে আমরা next node এ ০ cost এর কোন edge দ্বারা যুক্ত থাকি যা মানে হচ্ছে current node এ থাকা আর next node এ থাকা একই ব্যাপার তাহলে next_node কে deque এর front এ পুশ করব । যদি দেখা যায় current node থেকে next node এ যাবার cost ১ তাহলে আমরা deque এর back এ next_node কে পুশ করব । আর একটা ব্যাপার রয়েছে , bfs এ আমরা একটা নোড একবার আসা মানেই এতে minimum cost এ এসে গেছি এইখানে কিন্তু তা হয় , তাই নোড cost update এর কাজটা আমরা dijkstra এর মত করব , dijkstra তে প্রতি পুশ এর জন্য priority_queue বা sorting_order কাজ করতে হয় এতে push এর জন্য টাইম লাগে প্রায় logN এর মত , o/1 bfs তা o(1) এ হবে । বাকি সব কিছু আগের মতই হবে ।

practice problem : 1 

Programming Interview Tanvir Hasan Anick

ইন্টারভিউ সিরিজের আগের লিখাগুলা এই লিঙ্কে পাওয়া যাবে ।

প্রশ্ন ঃ প্রোগ্রামিং কন্টেস্ট এর ব্যাপারে প্রথম কিভাবে জানছিলা মনে আছে ? উত্তরঃ হুম। ভার্সিটিতে ভর্তি হবার আগে হালকা প্রোগ্রামিং শিখে ছিলাম। আমি একটু দেরিতে ভর্তি হবার কারণে আমার অন্যান্য ফ্রেন্ডরা একটু এগিয়ে ছিল। ওইসময় সাস্টের এক ফ্রেন্ড ইভান, (স্কুল ফ্রেন্ড মূলত) ওর কাছ থেকে প্রথম "uva peter smoke" প্রবলেমটার লিঙ্ক পাই।

সেইদিন থেকেই মূলত প্রোগ্রামিং কন্টেস্ট নাম এ কিছু একটা আছে। এই জিনিসটা জানা হয়েছিল।  প্রশ্নঃ প্রথম অনসাইট কনটেস্ট কথা মনে আছে ? 
উত্তরঃ হ্যাঁ ২০১২ সালে। আমার প্রথম অনসাইট ছিল ICPC-2012। ড্যাফোডিল ইউনির্ভাসিটিতে। কোনকিছুই তেমন করি নাই, শুধু এদিক ওদিক তাকিয়ে ছিলাম আর একটা চাইনিজ টিমের সল্ভ করার আনন্দ দেখেছি। প্রশ্নঃ কি টাইপের প্রবলেম সল্ভ করতে বেশি ভাল লাগে ? উত্তরঃ নাম্বার থিউরি আর ডিপি। প্রশ্নঃ কোন প্রবলেম সল্ভ এর সময় "Thinking Process" কি থাকে প্রবলেম পড়ার পর ? উত্তরঃ প্রবলেম পড়ার পরেই প্রথমে আগে ছোট ছোট কেস খাতায় লিখে একটা বেসিক আইডিয়া দাঁড় করানোর চেষ্টা করি। যদি দেখি যে ঠিকঠাক আছে তখন কোড করা শুরু করি। আর যেসব প্রবলেম মনে হয় প্যার্টান আছে, সেইগুলার জন্য আগেই একটা ব্রুটফোর্স কোড লিখে র্স্কিনে কিছু কেস রান করিয়ে খাতা কলম নিয়ে বসি প্যার্টান বের করার চেষ্টায়। প্রশ্নঃ UAP এর এসিএম ট্রনিং কিভাবে হয় ? উত্তরঃ Uap সাম্প্রতি সময়ে কন্টেস্ট এর রেজাল্ট ভাল করার জন্য অনেক আগ্রহী। সেইজন্য বর্তমানে সিনিয়র ও জুনিয়র দুই লেভেলের জন্য আলাদা আলাদা ট্রেইনার নিয়োগ দেয়া হয়েছে। সিনিয়রদের এখন শিপলু স্যার আর জুনিয়রদের সুপ্ত ভাই ট্রেইনিং করাচ্ছে। আর যেহেতু ভার্সিটি এখন পার্মানেন্ট ক্যাম্পাসে আছে, তাই সুযোগ সুবিধা আগে থেকেও এখন অনেক বেশি। প্রশ্নঃ আইওআই যারা না করে ভার্সিটি থেকে কনটেস্ট করে তারা দেখা যায় আইওআই যারা করেছেন তাদের থেকে পিছাইয়া থাকে , অনেক সময়ই পিছাইয়াই থাকে । যারা ভার্সিটি তে মাত্র কনটেস্ট নিয়ে জানল তাদের কি করা উচিত এই দুরুত্ব কমানোর জন্য ? উত্তরঃ যারা ioi করে তাদের জন্য অনেক স্পেশাল ট্রেইনিং হয় যার ফলে তারা স্বাভাবিকভাবে ভার্সিটিতে কন্টেস্ট করে তাদের থেকে অনেক এগিয়ে থাকে। সেই হিসেবে দেখা যায় ভার্সিটির সেই স্টুডেন্টকে তাদের লেভেল এ আসতে আসতে অনেক সময় লেগে যায়। সেই সময়ে হয়ত তাদের ভার্সিটি লাইফও শেষ হয়ে যায়। যেমনঃ আমি tongue emoticon:p আর আমি প্রাইভেট ভার্সিটিতে পড়তে গিয়ে একটা জিনিস দেখেছি, বেশিরভাগ স্টুডেন্ট ভর্তি হয় এখানে একটা হতাশা নিয়ে। তাদের সব-সময় এমন একটা মেন্টালিটি সেট করা থাকে যে আমি পাবলিক ভাল কোথায়ও চান্স পাই নাই তাই আমাকে নিয়ে এইসব কন্টেস্ট টাইপ জিনিস কোনদিন হবে না। তাই যারা ভার্সিটি ভর্তি হয়ে কন্টেস্ট সম্মন্ধে জানল বা কন্টেস্ট করার আগ্রহ আছে, তাদের প্রথমেই সকল হতাশা ঝেড়ে ফেলা উচিত। আর এমন একটা মনোভাব থাকা উচিত আমি পারবই। আর নিয়মিত প্র্যাকটিস। যেটা একটা ফরজ জিনিস কন্টেস্ট এর জন্য। তবে আমার ভার্সিটির অভিজ্ঞতা বলে নতুন যারাই আসে ভার্সিটির প্রথম সেমিস্টারে তারা কিভাবে কিভাবে যেন html css দিয়ে সাইট ডেভেলাপ করা যায় আর তা দিয়ে টাকা আর্জন করা যায় এমন একটা ধারনা পায়। আর পথে হাঁটতে গিয়ে বেশির ভাগ স্টুডেন্ট না শিখে প্রোগ্রামিং না হয় ভাল ডেভেলপার। প্রশ্নঃ tanvir002700.wordpress.com শুরু করার কথা কিভাবে ভাবলা , বাংলায় ব্লগ প্রোগ্রামিং নিয়ে খুব একটা নেই এখন যারা কনটেস্ট করে তাদের ব্লগিং কিভাবে তাদের হ্যাল্প করতে পারে , নতুন যারা ব্লগ লিখছে তাদের জন্য কোন সাজেশন ? উত্তর : tanvir002700.wordpress.com এইটা প্রথমে তেমন মহৎ চিন্তা নিয়ে শুরু করি নাই। প্রথম যখন python শেখা শুরু করি, দেখলাম যে আমরা কন্টেস্ট এ যেসব algorithm ব্যবহার করি সেইগুলা পাইথনে তেমন নেই, বা সহজে পাওয়া যায়। তারপর আমি কিছু algorithm পাইথনে লিখে ফেসবুকে একটা পোষ্ট আঁকারে দেই। ফেসবুক পোস্টে কোড দেয়া অনেক ঝামেলা। তারপর তখন মনে হল ব্লগে লিখি এইগুলা পরে আমি ভুলে গেলে নিজেও দেখতে পারব। তারপর ব্লগ খুলি। তারপর যখন শিপলু স্যারের কাছ থেকে suffix array শিখলাম তখন চিন্তা করলাম এই জিনিসত বাংলায় কোথায়ও ভাল রিসোর্স পাই নাই। এইটা সবার সাথে শেয়ার করি, নিজেও ভুলে গেলে আবার এইখান থেকে দেখে নেয়া যাবে আর অন্যরাও একটু হেল্প পাবে। এইভাবেই ব্লগ লেখা শুরু। যারা নতুন নতুন ব্লগ লেখছ, তাদের জন্য একটা উপদেশ প্রথম প্রথম হয়ত অনেকের কাছ থেকে অনেক কথা শুনবা। অনেকে হয়ত বলবে ফেমাস হওয়ার জন্য করছ। (আমি যে প্রবলেম ফেস করেছিলাম আরকি ) এইসব কান না দিয়ে নিজের মত করে লিখে যাও, কেউ কমেন্টে কোন সাজেশন দিয়ে সেইগুলা গ্রহণ করে লেখা উন্নত কর। জ্ঞান সবার মাঝে ছড়িয়ে দেয়ায় ক্ষতির কিছু নেই। প্রশ্নঃ Quora , Codefight এইসবগুলাতেও তুমি অনেক একটিভ । বাংলাদেশ এর এখনও এইসব সাইট এতটা জনপ্রিয়তা পায় নাই , এইগুলো তোমাকে কোন হ্যাল্প করতেছে ? উত্তরঃ Quora নিয়ে তেমন বিশেষ কিছু বলার নেই। খুব সম্প্রতি Quora তে একটিভ আমি। বাসায় বেকার বসে আছিতো, তাই অলস সময় একটু ইফেকটিভ কিছু করে কাটানোর একটা ছোট চেষ্টা মাত্র।
tongue emoticon আর Codefight, হ্যাঁ এই জিনিসটা আমার কোডের ডিবাগিং এবিলিটি অনেক বাড়িয়ে দিয়েছে। তবে মাঝে দিয়ে এই জিনিসের চরম নেশায় পড়ে গিয়েছিলাম। কোডফাইটের কয়েন দিয়ে টি-শার্ট কেনা যায় সেই টি-শার্টের লোভে সারাদিন ফাইট দিতাম। tongue emoticon তবে Codefight অনেক ভাল একটা জিনিস, যারা সারাদিন ক্ল্যাশ অফ ক্ল্যানে এটাক দাও তারা কিছুদিন Codefight এ ফাইট দিয়ে দেখতে পার, কোডিং ভাল লাগলে এই জিনিসের নেশায় পরে যাবা। আর এই জিনিস রিটার্নে তোমাকে ডিবাগিং এর কিছু এবিলিটি দিবে যেটা হয়ত অন্য গেম দেয় না। সব মিলিয়ে আমার কাছে খুবই ভাল একটা সাইট। প্রশ্নঃ অনেকেই ভার্সিটি লাইফে প্রোগ্রামিং কনটেস্ট এর চেয়ে freelancing এ জোর দেয় অনেক , এইটা আমি খারাপ বলছি না , এতে অনেক টাকাও পাওয়া যায় কিন্ত্ শিখার টাইমটা অনেক নস্ট হয় , এই ব্যাপারে তুমি কি বলবা ? উত্তরঃ freelancing!!! এই ব্যাপারে আমার মতামত খুবই নেগিটিভ। আমার ভার্সিটে দেখা অভিজ্ঞতা যদি বলি, বেশিরভাগ স্টুডেন্ট প্রথমেই সিএসইতে ভর্তি হয়ে যে জিনিসটা যানে সেইটা হল freelancing নামে একটা জিনিস আছে যেটা দিয়ে অর্থ উপার্জন করা যায়। সেই জিনিসের সুবাধে বেশিরভাগ স্টুডেন্ট ভার্সিটির প্রথম সেমিস্টার থেকেই হালকা html css শিখে টাকা কামায়ের ধান্দায় পরে যায়। এইভাবে করে দেখা যায় সে প্রোগ্রামিং এর বেসিক জিনিস ও এ্যালগরিদম ডাটাস্ট্রাকচার এইগুলা কিছুই শেখে না। সুতরাং আমার তবে freelancing করতে হলে ভার্সিটির প্রথম ৩ বছর নয়। ভার্সিটির প্রথম ৩ বছর শুধু cse রিলেটেড জিনিস পত্র শেখায় সময় দেয়া উচিত। প্রশ্নঃ প্রোগ্রামিং কনটেস্ট এ ইন্সপারেশন এর কেউ আছে , কাউকে ফলো করতে ? উত্তরঃ প্রোগ্রামিং কন্টেস্ট এর ইন্সপারেশন হল শিপলু স্যার। আমার ৪ বছরের পুরাটা সময় ধরতে গেলে স্যারের হাত ধরে চলতে শেখা। প্রোগ্রামিং কন্টেস্ট এর বেশিরভাগ জিনিস শিখেছি স্যারের কাছ থেকে। আর সবসময় স্যারকে ফলো করার চেষ্টা করতাম। স্যারের একটা জিনিস ভাল লাগে সেইটা হল কত স্টুপিডের মত কত উল্টাপাল্টা কাজ করেছি, কোনদিন বকা দেয় নাই:P :P প্রশ্নঃ নতুন যারা কনটেস্ট শুরু করতেছে তাদের কোন সাজেশন ? কিভাবে ভাল করবে ? উত্তরঃ যারা নতুন কন্টেস্ট করতেছে, তাদের জন্য সাজেশন হল লেগে থাক। প্র্যাকটিস বন্ধ করিও না, সফলতা আসবেই। প্রশ্নঃ অনেক সময় দেখা যায় কয়েকদিন কারো কনটেস্ট ভাল না হইলে অনেক এ হতাশ হয়ে কনটেস্ট ছেড়ে দেয় বা অন্যভাবেও বলা হয় সব কনটেস্টেন এর লাইফে হতাশার একটা পিরিয়ড থাকে , এই সময় কিভাবে নিজেকে মোটিভেট করা উচিত ? উত্তরঃ কন্টেস্ট ভাল না হওয়া/ আমি যেটাকে বাঁশ বলি tongue emoticon tongue emoticon:P সেইটা কি জিনিস আমার cf আইডি দেখলে বুঝা যায়। তারপর এত এত বাঁশ খাওয়ার পরেও কন্টেস্ট করা বন্ধ করি নাই। হতাশ হওয়া যাবে না। হতাশ হলে উল্টো বিপদ। হতাশ হলে পার্ফমেন্স দিন দিন আরও খারাপ হতে থাকে। যদি কোন কন্টেস্ট খারাপ হয় সেইটায় কি ভুল করেছ, বা যেগুলা সল্ভ হয় নাই সেইগুলা সল্ভ করার চেষ্টা কর। শিপলু স্যার সব সময় একটা কথা বলতেন আমি যখন cf শুরু করি, র‍্যাঙ্ক লিস্ট দেখ না, কন্টেস্ট শেষে তোমার লেভেলের যেসব প্রবলেম ছিল সেইগুলা সল্ভ করতে পেরেছ কিনা সেইটা দেখ। আর আমার মতে একটা অনেক গুলা অনলাইন কন্টেস্ট খারাপ হওয়া মানে, অফলাইন প্র্যাকটিসের অভাব। সুতরাং হতাশ হয়ে কন্টেস্ট অফ করে দিয়ে সেলেন্ডার করার চেয়ে, ভুল খুঁজে বের করে কাম ব্যাক করাই বুদ্ধিমানের কাজ। প্রশ্নঃ প্রোগ্রামিং বাদে কোন হবি ? ফ্রি টাইমে কি কর ? উত্তরঃ প্রোগ্রামিং বাদে আর যদি শখের কিছু থেকে থাকে সেইটা হল সাইক্লিং করা :P tongue emotico আর অবসর সময় দেখা যায় কখনও কোন ব্লগ/বই পড়ি অথবা টিভি সিরিজ দেখি।

Greedy Part - 3

greedy Algorithm এর উপর লিখা আমার আগের  পোষ্টগুলা এই লিঙ্ক এ পাওয়া যাবে ।

এই post এও কিছু interesting greedy problem নিয়ে  আলোচনা করর ।


Eternal Victory ::

এই প্রবলেমটাতে আসলে যা বলা হইছে আমাদের একটা ট্রি দেওয়া আছে (বিভিন্ন সিটি নিজেদের মধ্যে কনেক্টেড হয়ে ট্রি করছে ) । এই ট্রি এর সবগুলো নোডে আমরা মিনিমাম কত cost এ visit করতে পারি । আমরা ১ নাম্বার নোড থেকে যাত্রা স্টার্ট করব এবং যেকোন নোড এই থামতে পারব ।

যেহেতু এইটা ট্রি এর মানে হইল আমাদের কোন লুপ নেই । লুপ না থাকার কারণে আমরা জানি যে যেকোন একটা লিফ নোড এ আমরা থামব এবং  এইখানে কতগুলো রাস্তা আমাদের দুইবার যাতায়াত করতে হবে । যেহেতু আমরা সব থেকে মিনিমাম cost বের করছি আমরা চাব ১ নাম্বার নোড থেকে এর সব থেকে দুরের নোডে যেতে যে যে রাস্তা দিয়ে যাইতে হয় তারা যেন একবারই ভিজিট হয় আর বাকি সব নোড হবে দুইবার করে ।




ReplacingDigit ::
টপ কোডারের এই প্রবলেম এ বলা হয়েছে আমাদের কিছু product এর প্রাইজ ট্যাগ দেওয়া হবে এবং সাথে কিছু এক্সট্রা ডিজিট ও দেওয়া হবে আমারা চাইলে আমাদের কোন প্রোডাক্টের প্রাইজ ট্যাগর কোন ডিজিটকে বদলাতে পারি কিন্ত্ আমাদের কোন এক্সট্রা ডিজিট আমরা আমাদের প্রোডাক্টের প্রাইজ ট্যাগর সাথে যোগ করতে পারব না ।আমাদেরকে বলতে হবে হাইস্ট কত আমরা এই প্রোডাক্টগুলো থেকে পেতে পারি । লিমিট এ একটা জিনিস বলা আছে হাইস্ট 10^6 প্রোডাক্টের প্রাইজ হতে পারে ।
যদি ধরে নেই আমরা গ্রিডি সল্ভ করব তাহলে গ্রিডি সলুশ্যন এর সব থেকে গুরুত্বপূর্ণ পয়েন্ট হচ্ছে current stage এর highest possible gain । কি কি ফ্যাক্টর তা আমাদের দিবে এইটা আমাদের বের করতে হবে ।

১। most right digit থেকে আমরা দেখব আমরা কোন নাম্বার চ্যাঞ্জ করে বেশি লাভ করতে পারি কিনা ।
২। যদি পারি তাহলে সবথেকে smallest most right digit কে আমরা all possible extra digit থেকে highest possible value digit দ্বারা replace করব যা আমাদের highest profit ensure করবে ।
৩। একই প্রসেস আমরা সব ডিজিট এর জন্য ব্যাবহার করব ।

এখন আমাদের এই ব্যাপারগুলাকে  একসাথে merge করে answer বের করতে হবে ।




To Add or Not to Add::
কোডফরসেস এর এই প্রবলেম এ বলা হয়েছে আমাদের একটা N সংখ্যক number এর array দেওয়া আছে এবং সাথে একটা নাম্বার K ও দেওয়া আছে । K এর কাজ হল , আমরা K সংখ্যকবার চাইলে array এর কিছু element ( যদি খালি একটাও হয় ) ১ করে বাড়াতে পারি । আমাদেরকে এই array থেকে highest frequency এর নাম্বার প্রিন্ট করতে হবে , যদি একাধিক থাকে তাওলে সবচেয়ে ছোট নাম্বার প্রিন্ট করতে হবে ।

এই প্রবলেমটা অনেকভাবে সল্ভ করা যেতে পারে  এর মধ্যে two pointer technique use করে আমরা খুব সহজে করতে পারি ( two pointer technique কি এইটা জানা থাকলে এই ব্লগটা আগে পড়ে আসতে হবে ) । এরপর range এর মধ্যে commutative sum এর মাধ্যমে কোন নাম্বার এর জন্য হাইস্ট কতবার নাম্বারটা হতে পারে তা আমরা বের করতে পারি ।

প্রথমে আমরা sort করে নিব array টাকে , sort করাটা important কারন আমরা এর উপর range উপর কোন নাম্বার নিয়ে তা কতটা বানানো সম্ভব query করব , যা শুধু মাত্র একটা নাম্বার বানানোর জন্য এর সমান এবং সামান্য ছোট নাম্বারগুলাকে এর সমান বানাতে minimum কতটা adding দরকার হবে যা sorting sequence থেকেই আমরা পাই ।



two pointer এর মাধ্যমে প্রবলেম সল্ভ এর জন্য আমাদের দুইটা range পয়েন্ট থাকে , starting point and end point . আমরা যেহেতু iterative করে array এর প্রতিটি ভ্যালু নিয়ে দেখছি আমাদের উপরের কোডের 'i' হচ্ছে end point এবং 'p' হচ্ছে আমাদের starting পয়েন্ট । এখন p পয়েন্ট থেকে i পয়েন্ট পর্যন্ত যে নাম্বারগুলা আছে তাদের যদি আমরা 'i' পয়েন্ট এ যে নাম্বারটার সমান করতে চাই তাহলে যতবার adding operation লাগবে তা K( কোডে m ) এর ছোট বা সমান হচ্ছে কিনা তা 26 number লাইনের while loop দিয়ে চেক করা হচ্ছে , পরে answer update করা যায় কিনা check করা হচ্ছে ।

উপরের কোডের একটা মাত্র সাইন চ্যাঞ্জ করলে তা minimum number থেকে maximum number পাওয়া যাবে highest frequency এর জন্য , কোন সাইনটা চ্যাঞ্জ করতে হবে তা পাঠকদের খুঁজে বের করার জন্য ছেড়ে দিলাম ।

এই লিখাটা আর বড় করছি না , আমার মনে হয় প্রোগ্রামিং কনটেস্ট এ আগ্রহ থাকার পরও প্রোগ্রামিং কনটেস্ট এ অনেক এর ভাল করা সম্ভব হয় না quality problem solve না করার কারনে । ১০০টা same logic এর প্রবলেম সল্ভ করে যে লাভ টা হয় না , তার চেয়ে ৫টা different logic এর প্রবলেম সল্ভ করে অনেক কিছু জানা হয় । এখন একজনের পক্ষে হয়তো এই ৫টা different problem এর আইডি জানা কস্টকর , যে কাজটা একজন কোচ হয়তো করে দেন বা কোন সিনিয়র বড় ভাই ভার্সিটির যিনি নিজে অনেক টাইম দিছেন এইসব এর পিছনে । ভাল প্রবলেম এর আইডি মনে রাখা এমন মাঝে মধ্যেই এই প্রবলেম গুলার সল্যুশন লজিক দেখা important . যেইটা আমি নিজে অনেক পরে বুঝেছি বলে এখনও মাঝে মধ্যে আফসোস হয় । সব ভার্সিটির ট্রেনিং প্রসেস এক হওয়া সম্ভব না , এখন আমারা যারা নিজেরা সাফার করছি বা করিও নেই ( অনেক ভাল যারা করেছেন এবং করছেন ) তাদের দায়িত্ব হল এই প্রবলেম গুলার আইডিয়া বলে দেওয়া , সম্ভব হলে কিছু সল্ভ লজিক সহ যেন অন্য যে কেউ তা থেকে নিজে নিজে একটা শিখতে পারে । চীনা এবং রাশিয়ানরা কেন প্রোগ্রামিং কনটেস্ট এ এত ভাল করে তা একটা ভাল কারন ট্রেনিং ম্যাটেরিয়াল নিজেদের ভাষায় অনেক বেশি তাদের , যেইটা এখনও বাংলাতে নেই । যদি আমি গত ৪ বছর যাবত অনেক চ্যাঞ্জ দেখছি , আমি যখন স্টার্ট করি এক ফাহিম ভাইয়া এর ব্লগ বাদে কিছু ছিল না , পরে সাফায়াত ভাইয়া এখন প্রায় ব্যাসিক সব কিছু নিয়ে লিখে ফেলেছেন কিন্ত্ এখনো প্রবলেম ম্যাটেরিয়াল নিয়ে সবাই আগ্রহী না । আমার ব্লগের মাধ্যমে কারো কোন উপকার হইতে এইটা অনুরোধ থাকবে আপনিও বাংলাতে প্রবলেম সল্ভিং নিয়ে লিখা শুরু করুন । ইনশাল্লাহ আইওআই এবং এসিএম এর গোল্ড খুব একটা বেশি দূরে নয় :) 

LIS and variation

LIS ( Longest Increasing Subsequence ) যখন আমাদের কোন লিস্ট দেওয়া হবে যার numerical value আছে প্রতিটা element এর এবং  এই লিস্ট থেকে আমাদের এমন একটা সাব লিস্ট নিতে হবে যেই সাব লিস্ট sequentially increasing order এ হবে ,  যদি আমরা এমন একটা সাব লিস্ট নেই যেইটার length আমাদের all possible chosen sub list এর মধ্যে বৃহত্তর তাহলে সেই সাব লিস্টটাকে LIS বলে । যদি উদারণ দেই , ( 3 , 4 , 1 , 8) যদি আমাদের লিস্ট হয় তাহলে { 3 } , { 4 } , { 1 } , { 8 } , { 3 , 4 } , { 4 , 8 } , { 1 , 8 } , { 3 , 4 , 8 } এইগুলো আমাদের all possible sub list যা increasing order এ আছে এদের মধ্যে { 3 , 4 , 8 } এই লিস্ট এর length সবথেকে বৃহত্তর তাই এইটা আমাদের LIS ।

LIS বের করার জন্য যেহেতু একটা single element এর value ( LIS length ) তার আগের element গুলার উপর নির্ভর করে , LIS কে তাই dynamic programming algorithm ( DP ) বলা যায় । আমার কাছে LIS সবথেকে সহজতর (বুঝার জন্য) ডায়নামিক প্রোগ্রামিং আল্গরিথম । তবে প্রোগ্রামিং কনটেস্ট এ খুব কমই আমরা সরাসরি কোন প্রবলেম পাব যেখানে খালি LIS বের করতে  বলছে । আমাদের অনেক প্রবলেম সল্ভ করতে হবে যেখানে দৃশ্যমান বা অদৃশ্যমান LIS লুকাইয়া থাকবে । এই লিখাটার উদ্দেশ্য হচ্ছে LIS এর সব ধরণের ভ্যারিয়েশন এর একটা প্রাথমিক ধারণা তুলে ধরা ।  

LIS এর সব থেকে naive solution হচ্ছে O(n^2) । আমরা যদি LIS বের করতে চাই প্রাথমিক ভাবে সব element এর LIS length 1 দিব , তারপর iterate করে current element এর অবস্থান থেকে এর আগের সব element এর মধ্যে দেখব কোন element টা আমাদের current element থেকে ছোট বা সমান ( ক্ষেত্রে বিশেষ এ , অনেক সময় বলাই থাকে কোন duplicate element থাকবে না  ) যদি এমন কোন element পাই তাহলে check করে দেখব আমাদের current element এর LIS ভ্যালু আপডেট করা যায় কিনা , এইভাবে আমারা সব element এর LIS ভ্যালু পেয়ে যাব এদের মধ্যে যার ভ্যালু ম্যাক্সিমাম এইটাই আমাদের LIS ।





অনেক ক্ষেত্রেই O(n^2) solution আমাদের জন্য খুব একটা ফলপ্রসূ নাও হতে পারে যদি দেখা যায় আমাদের 10^5 or 10^6 সংখ্যক element এর জন্য LIS বের করতে বলা হচ্ছে তাহলে আমাদের টাইম লিমিট দেখে আরো better কিভাবে আমরা LIS  পাব তা নিয়ে ভাবতে হবে। LIS এর একটা ছোট এবং ফাস্ট একটা সলুশ্যন হচ্ছে C++ এর বিল্ট ইন set ব্যাবহার করে nlg(n) এ সল্ভ করা । তবে এইখানে বলে রাখা ভাল যদি আমরা যদি set use করি তাহলে এইখানে duplicate কোন ভ্যালু LIS এ থাকবে না ।



আমরা একটা উদারন দিয়ে বুঝতে পারি এইটা কিভাবে কাজ করে । ধরি { ১ , ৩ , ২ , ৪ } হচ্ছে আমাদের প্রাথমিক লিস্ট । স্বাভাবিকভাবে আমরা প্রথম element থেকে সামনে আগাবো । প্রথমে আমরা ১ আমাদের সেট এ পুশ করি , তাহলে set এর length হচ্ছে ১ । যদি তা একটা নরমাল array এর সাথে compare করি ( 0 index starting ) তাহলে LIS নামক array এর 0 index এ আছে ১ , এবং যখন আমরা find operation টা করছি  এর মাধ্যমে আসলে আমরা ১ যেখানে আছে এর index খুঁজে বের করছি । যেহেতু ১ এখন ০ নাম্বার ইনডেক্স এ আছে তাই আমরা it value এখন ০ পাব , এখন যদি  এর ভ্যালু ১ বাড়িয়ে দেখি ১ নাম্বার ইনডেক্স এর কোন অস্তিত্ব LIS array তে নাই বা ১ এই হচ্ছে আমাদের সর্বশেষ ভ্যালু যদি আমরা ১ পর্যন্ত প্রাপ্ত সব ভ্যালুকে sorted আকারে দেখি । তারপর ৩ set এ insert করার পরও আমরা একই অবস্থা পাব । তখন { ১ , ৩ } হবে আমাদের set array । কিন্তু যেহেতু set এ সর্ট আকারে সব ভ্যালু থাকে যখন ২ insert হবে আমাদের set array হবে { ১ , ২ , ৩ } এখন যখন আমরা find দিয়ে ২ এর অবস্থান খুজব আমরা পাব ১ নাম্বার ইনডেক্স এবং এর থেকে ১ পজিশন বাড়িয়ে দেখলাম যেমন এখন ২ , ২ নাম্বার ইনডেক্স এর অস্তিত্ব আছে , যাতে আছে ৩ । এর মাধ্যমে আমরা বুঝি আমরা এমন কোন কিছু পেয়েছি যেটার মাধ্যমে আমাদের set array এর length বেড়েছে কিন্তু element টা শেষ পজিশনে আসেনি । অর্থাৎ আমাদের প্রাপ্ত LIS হয়তো আপডেট হবে না কিন্তু এর একটা পজিশনে আমারা কম value এর কিছু insert করতে পারি যা পারে হয়তো আমাদের জন্য পরে লাভবান হতে পারে , তাই আমরা ৩ রিমুভ করে দিব । ফলে set array হবে { ১ , ২ } , এরপর যখন ৪ insert হবে আমাদের set array হয়ে যাবে { ১ , ২ , ৪ } । এইখানে ৩ রিমুভ যদি নাও করতাম তাহলেও তো অনেক এর কাছে লাগতে পারে { ১ , ৩ , ৪ } এমন কিছু পাইতাম যা লেংথ ও ৩ যা এই লিস্ট এর জন্য হাইস্ট । কিন্তু যদি আমাদের লাস্ট element , ৪ না হয়ে ৩ হত তাহলে ??? তাহলে কিন্ত ৩ এর পর কোন আপডেট লেংথ পেতে পাইতাম না , তাই যখনই কোন পজিশনের জন্য আপডেট ভ্যালু পাওয়া যাবে আপডেট করাটা জরুরী ।

এইভাবে কোড অনেক ছোট হচ্ছে কিন্তু একটা প্রবলেম থেকে যায় এইখানে duplicate ভ্যালু allow না । অনেক এর মনে হতে পারে তাওলে আমরা multiset use করব । আইডিয়া ঠিক আছে multiset duplicate value allow করলেও কিন্তু find আসলে lower_bound হিসাবে কাজ করে যখনই কোন duplicate value পাবে তার পজিশন এর জন্য ঠিক ভাবে কাজ করবে না ।  আমাদের তাই upper_bound ব্যাবহার করতে হবে find এর বদলে । multiset এবং সাথে upper_bound করে আমরা duplicate value এর জন্যও LIS পেয়ে যেতে পারি ।

এখন আমরা LIS দ্বারা কিছু ইন্টারেস্টিং প্রবলেম এর সলুশ্যন ট্যাকনিক দেখব ।

LIS দিয়ে আমরা classical DP problem LCS সল্ভ করতে পারি এবং মজার ব্যাপার হচ্ছে better time limit এ । একটা প্রবলেম দিয়ে দেখি এইটা ।

XMEN
প্রবলেমটাতে আমাদের আমাদের একটা লিমিট N দেওয়া হবে এবং ( 1 - N ) পর্যন্ত দুইটা list দেওয়া হবে এদের মধ্যে থেকে আমাদের common longest sequence এর length বলতে হবে । classical LCS problem , কিন্তু লিস্ট length ( 10^5 )  পর্যন্ত হতে পারে এবং এর জন্য যদি আমারা LCS দিয়ে ট্রাই করি ( O(N^2) ) solution এর জন্য TLE পেয়ে যেতে পারি যা আমরা প্রায় nlg(n) এ LIS দিয়ে করে ফেলতে পারতাম । এই কাজের জন্য আমরা যেকোন একটা list কে base list ধরে ( 1 - N ) পর্যন্ত ভ্যালুর জন্য কিছু dummy value( serial number of that set ) সেট করব যার উপর আমরা যদি অপর লিস্ট এর উপর LIS করি তাহলে আমরা LCS পেয়ে যাব । ব্যাপারটা কিভাবে সম্ভব হবে আমারা একটা টেস্ট কেইজ দিয়ে দেখি । ধরে নিলাম আমাদের দুইটি sequence হচ্ছে { ৪ , ২ , ১ , ৩ } এবং অপরটা হচ্ছে { ১ , ৪  , ২ , ৩ } । যদি আমরা প্রথমটাকে আমাদের বেস ধরি তাহলে ,
৪ -> ১
২ -> ২
১ -> ৩
৩ -> ৪

যদি এই ভ্যালু গুলা দিয়ে সেকেন্ড লিস্টটা রিপ্লেস করি তাহলে { ১ , ৪ , ২ , ৩ } হয়ে যাবে { ৩ , ১ , ২ , ৪ } যার মধ্যে যদি LIS দেখি { ১ , ২ , ৪ } হচ্ছে আমাদের বৃহত্তর sequence যা { ৪ , ২ , ৩ } আমাদের LCS দুইটা sequence এর মধ্যে ।

এমন একটি প্রবলেম হচ্ছে 10635 - Prince and Princess ।

Looking for a Subsequence

এইটা অনেক ভাল একটা প্রবলেম LIS এর উপর । এইখানে আমাদের LIS sequence ও  print করতে হবে , যদি কোন কারনে টাই হয়ে যায় তাহলে আমারা সব সময় left পজিশন এর ভ্যালু নিব । টাই প্রিন্ট এর ব্যাপারটা যদি না থাকত তাহলে আমরা খুব সহজেই হয়তো stack বা list বা vector কোন কিছুতে ভ্যালুগুলো রেখে তা প্রিন্ট করে ফেলতে পারতাম । একটা মজার ব্যাপার দেখি যেকোন LIS sequnce এ যদি আমরা value invert করে দেই তা LDS হয়ে যায় ( Longest decreasing sequence ) যদি LDS কে reverse order represent করি তাহলে কিন্ত্ আমরা আমার LIS order পেয়ে যাই । এইটা একটা fact .যেমন মাইনাস মাইনাস গুন করলে আমরা পজিটিভ কিছু পাব । আমরা তাই reverse order এ LDS করব যা আমাদের প্রতিটা পজিশন এর জন্য LIS এর ভ্যালু দিবে ( অবশ্যই reverse order এ ) । যা থেকে খুব সহজেই আমরা আমাদের sequence print করতে পারি বা দেখতে পারি এমন কোন sequence possible কিনা ।

এই লিখাটা এইখানেই শেষ । কোন প্রশ্ন থাকলে কমেন্ট সেকশনে বা আমাকে সরারসি ফেসবুক , ইমেল এ যোগাযোগ করলেই হবে :)