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 . যেইটা আমি নিজে অনেক পরে বুঝেছি বলে এখনও মাঝে মধ্যে আফসোস হয় । সব ভার্সিটির ট্রেনিং প্রসেস এক হওয়া সম্ভব না , এখন আমারা যারা নিজেরা সাফার করছি বা করিও নেই ( অনেক ভাল যারা করেছেন এবং করছেন ) তাদের দায়িত্ব হল এই প্রবলেম গুলার আইডিয়া বলে দেওয়া , সম্ভব হলে কিছু সল্ভ লজিক সহ যেন অন্য যে কেউ তা থেকে নিজে নিজে একটা শিখতে পারে । চীনা এবং রাশিয়ানরা কেন প্রোগ্রামিং কনটেস্ট এ এত ভাল করে তা একটা ভাল কারন ট্রেনিং ম্যাটেরিয়াল নিজেদের ভাষায় অনেক বেশি তাদের , যেইটা এখনও বাংলাতে নেই । যদি আমি গত ৪ বছর যাবত অনেক চ্যাঞ্জ দেখছি , আমি যখন স্টার্ট করি এক ফাহিম ভাইয়া এর ব্লগ বাদে কিছু ছিল না , পরে সাফায়াত ভাইয়া এখন প্রায় ব্যাসিক সব কিছু নিয়ে লিখে ফেলেছেন কিন্ত্ এখনো প্রবলেম ম্যাটেরিয়াল নিয়ে সবাই আগ্রহী না । আমার ব্লগের মাধ্যমে কারো কোন উপকার হইতে এইটা অনুরোধ থাকবে আপনিও বাংলাতে প্রবলেম সল্ভিং নিয়ে লিখা শুরু করুন । ইনশাল্লাহ আইওআই এবং এসিএম এর গোল্ড খুব একটা বেশি দূরে নয় :) 

Greedy Part - 2

Greedy Problem নিয়ে এইটা আমার দ্বিতীয় ব্লগ । কেউ প্রথমটা দেখতে চাইলে এই লিঙ্ক  পাওয়া যাবে । এইখানে ইচ্ছা আছে কিছু ভাল greedy problem solution নিয়ে কথা বলার ।

The Double HeLiX :::

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

এইখানে সিকুয়েন্স এর লিমিট বলা হইছে <= ১০০০০ । আমরা এখন যদি চাই কোন কোন পয়েন্ট এ তারা ইন্টারসেকশন করছে তাহলে Naive process এ দুইটা ফর লুপ চালাইয়া পেয়ে যাব । রান টাইম O( n * m ) ( যেখানে 'n' একটা সিকুয়েন্স এর লেন্থ আর 'm' অন্য একটা সিকুয়েন্স এর লেন্থ ) । যদি A[] , B[] দুইটা সিকুয়েন্স নাম্বার হয় তাহলে A[n-1] & B[m-1] ইন্টারসেকশন করুক আর না করুক আমরা ধরে নিব এরা ইন্টারসেক্ট করছে ।  এখন কিছু Observation থেকে আমরা Greedy solution টা develop করতে পারি ।

 1. প্রথম এ লক্ষ্য করি কেন এইটা greedy process এ solve হবে । ধরি array A[] এর ইনডেক্স 'i' এবং array B[] এর ইনডেক্স 'j' intersect করছে । তাহলে অবশ্যই যদি A[0] - A[i] এর sum value B[0] - B[j] এর sum value থেকে বড় হয় তাহলে আমাদের সব সময়ই A সিকুয়েন্স থেকে যাত্রা করা লাভ যখন হবে । এবং এইভাবে যদি দেখি আমাদের প্রত্যকটা ইন্টারসেকশন independently এই ভাবে কাজ করতে পারে ।
২। এইখানে সব সময়ই এখন যেখানে আসি ( মানে ইন্টারসেকশন ইনডেক্স , যদি কোন ইন্টারসেকশন নাও থেকে থাকে আমরা n-1 , m-1 এর একটা dummy intersection করেছি বলে কম্পেয়ার করতে পারব ।
৩। রান টাইম কি হবে ? আমরা এইখানে যদি A[] array এর  ইনডেক্স ফিক্সকড করে ক্যালকুলেশন করি তাহলে m টা ইন্টারসেকশন পেতে পারি , যেখানে আমরা লিনিয়ার ভাবে মারজ করে ভ্যালু চেক করছি । মানে এই চ্যাকিং এবং কম্পায়ের কাজে আমাদের O(n+m) টাইম লাগবে । আমাদের ইন্টারসেকশন পয়েন্ট গুলা বের এর জন্য লাগছে O(n*m) . অর্থাৎ আমরা O(n*m) ( কোন কোডে যত অপারেশন হয় এর হাইস্ট যেটাতে টাইম লাগে ঐটাই কোন কোড এর রান টাইম ) greedy solution develop করতে পারি ।

কোড

Expedition :

এইটা খুব সুন্দর একটা প্রবলেম । priority_queue use কেন অনেক প্রবলেম solve সহজ করে দেয় , তা বুঝা যায় এই প্রবলেমটা করলে । এইখানে বলা হইছে গরু গাড়ি চালাইতে পারে :P ওরা একটা ট্রাক দখল করছে ,  এই ট্রাক এ করে নিকটবর্তী শহরে যাবে । যার দূরত্ব দেওয়া আছে । কিন্তু যেহেতু তারা ভাল মত গাড়ি চালাতে পারে না তারা গাড়ির ফুয়েল লিক করে ফেলছে , এখন কারেন্ট ফুয়েল দিলে ১ unit যাওয়া যায় । শহর আছে ট্রাকের অবস্থা থেকে d unit দূরে , এবং তাদের গাড়িতে ফুয়েল আছে f unit . এখন আরোও কিছু রিফ্রাইনিং স্টেশনের ইনফরমেশন দেওয়া আছে , এইটা কত দূরে ( শহর থেকে গাড়ি থেকে নয় , আমাদের এদের দূরত্ব গাড়ি থেকে প্রথমে বের করে নিতে হবে ) এবং কতটুকু ফুয়েল আছে ( গরুতে মেলা টাকা পয়সা :p তারা কতটা ফুয়েল করবে এইটা ব্যাপার না ) । এই প্রবলেম এ এই ইনফরমেশন গুলা নিয়ে বলা হইছে মিনিমাম কতটা ফুয়েল স্টেশনে থেমে গরুর দল নিকটবর্তী শহরে যাবে বা আদ্যও যাবে কিনা ।

• আচ্ছা স্বাভাবিক ভাবেই আমরা ফাস্ট এ যে যে স্টেশনে আছে তাদের দূরত্ব দিয়ে সর্ট করে নিব । ক্যালকুলেশন এর সুবিধার জন্য আমরা শহরকে এড দিব যেন দেখতে পারি শহরে পৌঁছাতে পারছি কিনা । 
• এইখানে অবশ্যই অবশ্যই যে যে স্টেশনে আমাদের কাছে এখন যা ফুয়েল আছে তা দিয়ে যাওয়া যায় তাদের মধ্যে থেকে ম্যাক্সিমাম যে যে স্টেশনে আছে তাদের থেকে ফুয়েল নিব ( যা না নিলেই নয় )  । এই কাজটা আমাদের priority_queue অনেক সহজে করে দেয় । 
• আমরা যদি কোন স্টেশনে না যেতে পারি মানে হইল আমাদের পক্ষে  শহরে যাওয়া পসিবল না । 
কোড :

এই কোডের রান টাইম হবে O( nlg(n) ) .

GERGOVIA :

এই প্রবলেমটা অনেক সহজ একটা প্রবলেম , একই প্রবলেম আমি Uva তেও দেখছি । এমন কি codechef , hacckerrank এর কনটেস্ট এও আসতে দেখছি । তাই এইখানে include করলাম ।

খুবই simple idea এর প্রবলেম । solution টাই হইল 'Think simple" । এই প্রবলেম এ একটা city এর সামগ্রিক অবস্থা তুলে ধরা হইছে । এইখানে একজন salesman বিভিন্ন বাড়িতে ওয়াইন দেয় বা কিনে , যদি ইনপুট '-' হয় তাহলে কিনবে যদি '+' হয় তাহলে কিনে ঐখানে  বিক্রি করবেন । এক বাড়ি থেকে অন্য বাড়ি যতটা ওয়াইন সরবরাহ করতে তার মিনিমাম কত unit কাজ করতে হবে ।

এই প্রবলেম এ বলাই আছে চাহিদা এবং  যোগান সমান থাকবে । এইটাই আমাদের ক্লু । একটা সাম ভ্যারিএবল নিব । এখন প্রথম বাড়িথেকে শেষ বাড়িতে ক্রমানয়ে যাব সাথে সাথে তাদের যা লাগবে ( কেউ কিনবে বা কেউ বিক্রি করবে টা যোগ করতে থাকব ) সাথে সাথে আমরা আমাদের ans current sum value এর absolute value add করতে থাকব । এইটাই আমাদের আন্সার হবে ।

আমরা চাইলে এইটা প্রুভ করতে পারি কেন কাজ করে । ধরে নেই শুধু মাত্র দুইটা বাড়ি আছে  তাহলে কি হবে
 5 -5 তাহলে এক বাড়ি থেকে অন্যবাড়িতে শুধু 5 unit কাজ করলেই হবে ।  consecutive sum করার ফলে ফাস্ট এ 5 পরের বার ০ এড হবে । এখন যদি আরো একটু বড় কেইজ নেই । 3 2 -5 . এইখানে আমাদের 7 unit কাজ করতে হয় , আমরা যে খান থেকে শুরু করি প্রথম থেকে বা শেষ থেকে consecutive sum করে যেতে থাকলেই আমরা রেজাল্টটা পাই । এই অবজারবেশন থেকে আমরা প্রবলেমটা সল্ভ করতে পারি ।

এই প্রবলেম Uva এবং codechef এ ছিল । এখন আইডি আমার মনে আসতেছে না । আমি চেস্টা করব আইডি গুলা এড করে দেবার জন্য পরে ।

এই লিখাগুলা লিখার পিছনে অনেকে কস্ট করে কমেন্ট করতেছে , ভাল ভাল কথা লিখতেছে :p যেইটা শুনতে তো ভালই লাগে । তাই লিখা ভাল লাগলে অবশ্যই জানাইতে ভুলবেন না :D আরো কিভাবে লিখাগুলাকে ভাল করা যায় বলবেন । আশারাখি সামনেই তৃতীয় পর্বটা আসবে ।  

two pointer

বিশেষ করে codeforces এর অনেক প্রবলেম এর ট্যাগে দেখা যায়  "two pointer" ট্যাগ করা আছে । স্বাভাবিক ভাবেই যেহেতু পয়েন্টার কথাটা আছে নামের সাথে আমি অনেকটা সময় ধরে ভাবতাম এই প্রবলেমগুলা হয়তো পয়েন্টার ব্যাবহার করে করা হয় । অনেকটা ছয় অন্ধের হাতি দেখা গল্পের মত । পরে কোডফরসেস এর একটা কমেন্ট এ একজন এর এক্সপ্লেনেশন দেখি । এরপর একদিন বুয়েট ওনিয়ন টিমের সাকিব ভাইয়াকেও জিজ্ঞাসা করছিলাম এই জিনিসটা কি । ভাইয়া একটা প্রবলেম দিয়ে এর সলুশ্যন বলছিলেন কিভাবে হচ্ছে , এই ট্যাকনিক টাই two pointer । এইখানে  বলে রাখা ভাল অনেক এর এই ট্যাকনিকে স্লাইডিং উইন্ডো ( যেহেতু একটা বাউন্ডারির মধ্যে কাজ করতে হয় এবং বাউন্ডারিটা একটা রেঞ্জ এর মধ্যে উত্তর দেয় তাই ) বলা হয় , দুইটা আসলে একই জিনিস । two pointer সম্পর্কে আরও কিছু বলার আগে আমরা একটা প্রবলেম দেখি ।

আমাদের বলা হল আমাদের কাছে দুইটা সর্টেট array আছে , আমাদের বলতে হবে এই দুইটা array থেকে একটা একটা ভ্যালু নিয়ে আমরা কতভাবে একটা নাম্বার M বানাতে পারি যাদের কোন মধ্যে কোন ডুপলিকেট ভ্যালু নেই ।

যদি আমরা একটু Naive Method দেখি -
এইখানে আমরা inner এবং outer for loop এর দুইটা relation এর মাধ্যমে খুব সহজে Ans বের করে দিতে পারি ।


আমরা  এইখানে N পর্যন্ত দুইটা লুপ চাল্লাচ্ছি । তাই আমাদের টোটাল রানটাইম হয়ে যাচ্ছে  O( N ^ 2 ) । আমরা যদি একটু Modification করি আমরা এইটা কমিয়ে O(N) এ নিয়ে আসতে পারি ।  আমরা দুইটা পয়েন্ট নেই ।
Say low and high । low পয়েন্ট করতেছে আমাদের A array এরটার starting point কে এবং high পয়েন্ট করতেছে আমাদের B array এর ending পজিশনটাকে ।

Observation number one ::

আমরা যদি দেখি A[low] + B[high] > M তাহলে আমরা একটা জিনিস সিউর ভাবে বলতে পারব । আমাদের অবশ্যই B এর ভ্যালু কমাতে হবে । কারণ যেহেতু A[low] হচ্ছে A এর সবথেকে ছোট ভ্যালু সুতরাং  তাকে আর কমিয়ে কখনই B[high] এর সাথে add করে M বানানো যাবে না ।

Observation number two :::

আমরা যদি দেখি A[low] + B[high] < M তাহলে আমাদের অবশ্যই low এর ভ্যালু বাড়াতে হবে । কারণ high হচ্ছে B এর সবথেকে বড় ভ্যালু এর থেকে বড় ভ্যালু নাই । high থেকে আমরা কোন ভ্যালু বাড়াতে পারছি না । তাই অবশ্যই আমাদের এখন low থেকে বাড়াতে হবে ।

এইখানে একটা খটকা লাগতে পারে Observation one এ  যেহেতু A[] array তে left to right যাওয়া হচ্ছে current low ভ্যালু মানে low যাকে right now point করছে A[] array তে তার থেকেও তো কম ভ্যালু আমার array তে থাকতে পারে । আমরা নিচের কোডটা একটু ভাল মত খেয়াল করলেই দেখতে পাব যে যদি থেকে থাকে এবং তার সাথে যদি high B[] array এর এড যদি M এর সমান হয় তাহলে তা আগেই Ans এর সাথে এড হয়ে আসবে ।  একদমই একই কাজ হচ্ছে B[] array তেও । এইখানে আমরা condition দিয়ে দুইটা পয়েন্টকে নিয়ন্ত্রণ করছি ।

এইখানে আমরা low and high দুইটা পয়েন্ট merge করে আগাচ্ছি । এই ধরনের ট্যানিক এ প্রবলেম সল্ভ করাই হচ্ছে two pointer method .

এখন আমরা আরেকটা প্রবলেম এর মাধ্যমে two pointer এর মাধ্যমে কিভাবে প্রবলেম সল্ভ করা হয় এইটা দেখব ।
problem  এইখানে আমাকে N টা নাম্বার দেওয়া থাকবে এবং একটা ভ্যালু দেওয়া থাকবে say S । আমাকে minimum length এর consecutive sub sequence  বের করতে হয়ে যাতে এই consecutive sub sequence এর sum, S এর থেকে বড় বা সমান হয় ।

এই প্রবলেম অনেক এপ্ররোচে আমাদের করা যাবে মনে হইতে পারে । কিন্ত o(n) runtime আনা ব্যাতিত্ব এই প্রবলেম সল্ভ হবে না । o(n) runtime আমরা two pointer ট্যাকনিক এর মাধ্যমে আনতে পারি ।

একই ভাবে আগের প্রবলেম এর মত এইখানে আমরা দুইটা পয়েন্ট নিব । low , high । প্রাথমিক ভাবে দুইটা পয়েন্ট এই given number array এর starting point indicate করে । যতক্ষণ পর্যন্ত না low থেকে high এর sum  , M এর ভ্যালু ক্রস না করে আমরা high এর ভ্যালু বাড়াইয়া যাব । যখনই ক্রস করবে বা সমান হবে তখনই আমরা current length check করব ( high - low + 1 ) যদি minimum ans update করা যায় তাহলে update করব ।  যখনই sum  এর ভ্যালু M এর থেকে বড় হয়ে যাবে তখন আমরা low এর ভ্যালু বাড়ানো সাথে সাথে sum এর ভ্যালু ও adjust করতে থাকব ।

কোডটা দেখলে ব্যাপারটা ক্লিয়ার হয়ে যাবে

এখন যদি আমরা এই কোডটার রান টাইম দেখি । কোডটা high = 0 থেকে high < len পর্যন্ত চলছে । মানে O(n) এ ।

two pointer এর আরো একটা problem হচ্ছে এইটা  । এইখানে আমাদের given array দেওয়া হ্য়নি । আমাদের given formula দিয়ে input ready করে নিতে হবে । এইটা বাদে almost same প্রবলেম হিসাবে মিলে যাচ্ছে আগের প্রবলেমটার সাথে ।

two pointer এর আরো প্রবলেম আইডি এইখানে কমেন্ট জানালে আমি এড করে দিতে পারব । বা কোন ট্যাকনিক কমেন্ট এ দিলে সবাই জানতে পারবে ।

Happy coding :)

Practice Problem :: 1 , 2 .

Greedy Method

Greedy কি ? 

 প্রথমেই আসা যাক , greedy কি ? greedy হল ভবিষ্যতের এর কথা চিন্তা না করে বর্তমান অবস্থা গুলা বিবেচনা করে বেস্ট একশনটা নেওয়া । হয়ত এইটা পরবর্তীতে সবথেকে optimal নাও  হতে পারে । greedy solution তো optimal না তাহলে কেনই বা আমি greedy solution নিতে চাব । প্রথমত greedy solution time efficient । এমন অনেক ক্ষেত্রেই ধরে নেওয়া হয় greedy solution টাই best possible Ans . greedy solution যেহেতু  implement করা সহজ তাই অনেক optimized problem এর solution এর জন্য greedy use করা হয় । 

কিছু পরিচিত greedy process Change Making , kruskal Algorithm , Activity Selection . 

Change Making : 

        Change Making problem এ বলা হয় আমার কাছে অনেক গুলা বিভিন্ন মানের মুদ্রা আছে । আমাকে কোন সব থেকে কম মুদ্রা ব্যবহার করে Change দিতে হবে । আমি কিভাবে কাজটা করব । 

      এর প্রসেস হচ্ছে আমি সবসময় সবথেকে বড় মুদ্রাটা থেকে স্টার্ট করব এবং যতক্ষণ পর্যন্ত না এর ভ্যালু আমার change  ( একটা নিয়ে Total change  ভ্যালু থেকে subtract করা তো আছেই ) এর amount থেকে বড় হয়ে যাবে আমি নিতে থাকব , যদি তা বড় হয়ে cross হয়ে যায় তাহলে এর পরের value দিয়ে কাজ করার চেস্টা করতে থাকব । 

Code টা কিছুটা এমন

 আবারও বলে থাকা ভাল coin change এর জন্য greedy solution optimal না , optimal হল  dp   solution . কিন্তু  টাইম লিমিট অনেক সময় dp solution এর থেকে greedy solution      টাকেই optimal ধরে নেওয়া হয় । যদি এমন দেখা যায় coin গুলোকে ascending order এ সর্ট করার পর 2*coin[i] <= coin[i+1] তাহলে দেখা যাবে greedy solution best optimal result এই দিচ্ছি । 

Activity Selection Problem :

      Activity selection problem টা এমন আমাকে অনেক গুলা কাজ দেওয়া আছে । start time ও end time সহ । আমি একটা সময় শুধু মাত্র একটা কাজ এই করতে পারি । আমাকে যদি Nটা কাজ দেওয়া হয় তাহলে আমি সব চেয়ে বেশী  কয়টা কাজ করতে পারব । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন কাজ শুরু করতে পারব না  । এই প্রবলেম এর solutionটা অনেক সুন্দর । আমি কাজগুলাকে তাদের end time এর বেসিস এ sort করব । এর পর আমি যে কাজটা সবার আগে আসবে তা করব । এমন এর পর এ সেই কাজটা শুরু করব যার start time এই কাজের end time এর থেকে বেশী । 

Codeটা কিছুটা এমন
    

          এখন দেখা যাক এইভাবে করলে আমি কেন সব সময় বেস্ট Ans পাচ্ছি । আমি যদি end time  ধরে সর্ট করে
          কাজ স্টার্ট এর জন্য নেই আমি সবসময় সেইসব কাজ এই নিব যাদের end time অন্য কাজগুলা থেকে আগে      শেষ হচ্ছে   মানে আমি best option পাচ্ছি আরো বেশী কাজ স্টার্ট  করার ।

Active selection problem থেকে বুঝা যায় আসলে greedy কেন আসলে মাঝে মধ্যে dp থেকে ভাল ।  ধরুন আমার N টা কাজ এর লিস্ট আছে যাদের থেকে আমার বেস্ট লিস্ট করতে হবে যাতে আমি সবথেকে বেশী কাজ শেষ করতে পারি । DP এর জন্য আমার possible option 2^N . এখন N এর মান যদি অনেক বড় হয় তাহলে তা strict time limit জন্য খুব একটা ভাল উপায় না । আমি TLE খাব অনেক code এই । তাই মাঝে মধ্যে greedy is good .

Interval scheduling  problem :
 Interval scheduling ( Greedy ) problem এ আমাকে  অনেক গুলা কাজ এর start এবং end time দেওয়া হইছে । আমাকে প্রতিটা কাজ এর জন্য একটা  program assign করতে হবে । আমাকে বলতে হবে কিভাবে করলে সব থেকে কম  program assign করতে হবে । এইখানে overlapping possible না মানে একটা কাজ শেষ না করে কোন প্রোগ্রাম ফ্রী হবে না । মানে ৬ মিনিট এ যদি কোন কাজ শেষ হয় আর অন্য একটা কাজ ৬ মিনিট থেকে start হয় তাহলে ৬ মিনিট এর কাজ না শেষ করে যেহেতু অন্য কাজ শুরু করা যাবে না তাই এইখানে দুইটা প্রোগ্রাম লাগবে । আমি এইখানে sort করব । sort করার সময় end point , start point কে আলাদা ভাবে mark করব । start point priority পাবে মানে sorting এ সেম পয়েন্ট এ end , start থাকলে start আগে থাকবে । 

          

   কোডিং এ আমি চেক করব current position maximum কয়টা program স্টার্ট আছে , এইটাই আমার Ans . কারন এই সময় এই আমার সব থেকে প্রোগ্রাম রান করে রাখতে হবে । এর চেয়ে কম নিলেও আমার হবে না বেশী নিলে এক্সট্রা প্রোগ্রামগুলা বসে থাকবে ।

   Minimum Spanning Tree ( kruskal ) : 
  minimum spanning tree ও greedy problem এর জন্য ভাল উদারন । শাফায়াত ভাইয়া অনেক ভাল টিউটরিয়াল লিখছে kruskal . আশা রাখি এইখান থেকে একটু দেখলেই সবার clear হয়ে যাবে ।


কিভাবে আইডিয়া পাব এইটা greedy solution হতে পারে ?   যেকোন প্রবলেম এর solution idea পাবার পূর্বশর্ত হল এইরকম প্রবলেম অনেক সল্ভ করা । আমি যদি দেখি Ans গুলা current best option থেকে আসসে তাহলে আমি greedy solution এর কথা ভাবতে পারি । অনেক greedy problem এর সর্টিং , বাইনারি সার্চ এর দরকার হয় মানে সর্টিং , বাইনারি সার্চ করে বেস্ট পসিবল উত্তর পাওয়া যায় । এইসব ব্যাপার মাথায় রাখতে হবে । অনেক Dp প্রবলেম টাইম লিমিট এর মধ্যে করার জন্য code optimized করার প্রয়োজন হয় । তখন অনেক কেস greedy process থেকে বাদ দেওয়া হয় । তাছাড়া কোন প্রবলেম dp ,আর কোনটা  greedy তার মধ্যে difference করার জন্যও আমাদের greedy ভাবনা ভাবতে হবে । greedy মানে আমি নরমাল এই বেস্ট পসিবলের জন্য যা  চিন্তা করি ( human brain current stage থেকে একটা certain stage পর্যন্ত ভ্যালু ভাবতে পারে , তাই আমাদের চিন্তার ধরন greedy ) .  Uva আর Light Oj তে অনেক প্রবলেম আছে greedy এর জন্য । এইগুলা কিছু করলেই আরোও idea clear হবে সবার ।
problem
Uva Problem
Light Oj

সবাইকে অনেক শুভ কামনা :)