Bappy's Blog

 Problem Description  here Problem: সহজ ভাষায় বললে, এই প্রব্লেমে আমাদেরকে একটি গ্রীড দেয়া থাকবে। গ্রীডে দুই ধরণের সেল আছে। একধরনের সেলের উপর দিয়ে যাতায়াত সম্ভব এবং অন্য ধরণের সেলের উপর দিয়ে যাতায়াত সম্ভব নয়। আমাদেরকে বের করতে হবে Upper Left সেল থেকে Lower Right সেলে যাওয়ার জন্য কয়টা পাথ আছে যারা সোর্স এবং ডেস্টিনেশন ব্যাতীত অন্য কোন সেলে মিলিত হয় না।  এবং আমরা শুধু নিচে অথবা ডানে মুভ দিতে পারবো।  Solution: ১) একটু ভালোভাবে লক্ষ্য করলে বোঝা যায় যে, উপরোল্লিখিত পাথের সংখ্যা হবে সর্বোচ্চ ২। ২) এখন আমরা একটি ডিএফএস ছেড়ে একটা ভ্যালিড পাথ পাওয়া গেলে সেটি ভিজিট করে ফেলবো। ৩) আবারও ডিএফএস ছেড়ে কোন ভ্যালিড পাথ পাওয়া যায় কি না দেখবো। এক্ষেত্রে পূর্বের প্রাপ্ত(যদি পেয়ে থাকি) পাথের কোন সেল ভিজিট করা যাবে না যদি না সেটি সোর্স অথবা ডেস্টিনেশন সেল না হয়।    Similar Problem Happy Coding 😊

Problem Description  here Prerequisite of this problem  DFS ,  Strongly Connected Component(SCC) Problem: সহজ ভাষায় বলতে গেলে এই প্রব্লেমে মূলত বলা হয়েছে, আমাকে অনেকগুলো এজ দেয়া থাকবে। ০ নোড থেকে যাত্রা শুরু করে সবগুলো এজ এক্সেক্টলি ১ বার ভিজিট করা সম্ভব কি না বের করতে হবে।  Solution: ১) SCC সম্পর্কে ধারণা থাকলে এবং একটু চিন্তা করলেই দেখবে যে, SCC এর যেকোন নোড থেকে যাত্রা শুরু করে সবগুলো এজ এক্সেক্টলি ১বার ভিজিট করা সম্ভব।  ২) তাহলে, এই প্রব্লেমে আমার প্রথম কাজ হচ্ছে, গ্রাফটিকে অনেকগুলো SCC তে ভাগ করা। এখন, প্রতিটি কম্পোনেন্টকে একটি নোড কল্পনা করলে দেখবে যে একটি DAG(Directed Acyclic Graph) তৈরী হয়।  ৩) এখন, নতুন এই DAG এর জন্য আমাকে দেখতে হবে ০ নোড থেকে যাত্রা শুরু করে সবগুলো এজ এক্সেক্টলি ১বার ভিজিট করা যায় কি না? অর্থাৎ, আমাকে দেখতে হবে যে DAG এর প্রতিটি নোডের Child সর্বোচ্চ একটির মধ্যে সীমাবদ্ধ কি না এবং ০ থেকে যাত্রা শুরু করে সকল নোড ভিজিট করা যায় কি না।  আশা করি এখন প্রব্লেমটি নিজে নিজেই সলভ করা সম্ভব। তাও ব্যার্থ হলে কোড দেখতে পারোঃ  Happy C...

 Problem Description  here এই প্রব্লেমটি আমার তৈরী করা একটি প্রব্লেম যেটি মূলত  Intra CoU Programming Contest 2020  এর জন্য সেট করা।  প্রব্লেমঃ প্রব্লেমটিতে বলা হয়েছে একটি n সাইজের ট্রি দেয়া থাকবে। যার প্রতিটি নোডে কিছু ক্যারেক্টার থাকবে। ট্রি এর রুট নোড হচ্ছে ১। বলতে হবে, এই ট্রি এর রুট থেকে লিফ পর্যন্ত এমন কোন পাথ আছে কি না যে পাথ "tareq&shawon" এই স্ট্রিং টা কে সাবসিকুয়েন্স হিসেবে ধারণ করে। যদি এমন পাথ থাকে তবে Lexicographically Smallest পাথটি প্রিন্ট করতে হবে।  সল্যুশনঃ এই প্রব্লেমটির একটি ডিপি সল্যুশন সম্ভব।  ১) যেহেতু, Lexicographically Smallest পাথ বের করতে হবে তাই শুরুতেই প্রতিটি নোড এর জন্য তার এডজাসেন্সি লিস্ট টি Sort করে নিবো।  ২) ডিপি অ্যারের কাজ হবে প্রতিটি নোড থেকে লিফের দিকে যতোগুলো পাথ গেছে তাদের কোন একটি পাথ ধরে এখন পর্যন্ত স্ট্রিং এর যে ক্যারেক্টারগুলো সাবসিকুয়েন্স হিসেবে পেয়েছি সেগুলো ছাড়া বাকি সাফিক্সটুকু সাবসিকুয়েন্স হিসেবে পাওয়া যায় কি না সেটি ক্যালকুলেট করা।  ৩) এরপর, ডিপি অ্যারে ব্যাবহার করে ডিপি সল্যুশন প্রিন্...

 Problem Description  here এই প্রব্লেমটি আমার তৈরী করা একটি প্রব্লেম যেটি মূলত  Intra CoU Programming Contest 2020  এর জন্য সেট করা। এই প্রব্লেম সলভ করতে যা যা জানা দরকার তা হলোঃ Sparse Table ,  Segment Tree ,  DFS ,  Binary Search প্রব্লেমঃ প্রব্লেমটিতে বলা হয়েছে n সাইজের একটি ট্রি দেয়া থাকবে যার প্রতি নোডে কিছু ফুল আছে। এখন, তোমাকে q টা কুয়েরী এন্সার করতে হবে। কুয়েরী আবার দুই ধরণের হতে পারে। ১) u     v     x           v থেকে u এর দিকে সর্বনিম্ন কয়টা নোড ভিজিট করে কমপক্ষে x সংখ্যক ফুল কালেক্ট করা যায় তা বের করতে হবে যেখানে u হচ্ছে v এর এন্সেস্টর(পূর্বসুরী) । ২) u      y u নোডের ফুল সংখ্যা আপডেট করতে হবে। y পজিটিভ হলে যোগ হবে, নেগেটিভ হলে বিয়োগ।  হিন্টসঃ   ১) স্পার্স টেবিল ডাটা স্ট্রাকচার শিখে থাকলে এখন তুমি একটি ট্রি এর প্রতিটি নোডের জন্য এর kth প্যারেন্ট বের করতে পারবে নিশ্চয়ই! এর জন্য তোমার log(n) কমপ্লেক্সিটি লাগবে।  ২) প্রব্লেমে একটা ব্যাপার লক্ষ্য করেছো কি?...

Problem Description  here প্রবলেমঃ প্রবলেমটিতে মূলত বলা হয়েছে, n সংখ্যক নোডের একটি ট্রি দেয়া থাকবে। সর্বনিম্ন কতগুলো নোড বাদ দিলে ট্রি এর ডায়ামিটার সর্বোচ্চ k হবে।  একটি ট্রি এর ডায়ামিটার বলতে বুঝানো হয় ট্রি এর যেকোন দুইটি নোডের মধ্যবর্তী দূরত্বগুলোর সর্বোচ্চ মান।  সল্যুশন আইডিয়াঃ  ১) প্রতিটি ডায়ামিটার এর একটা সেন্টার থাকে। সেন্টার থেকে দুইদিকের দূরত্ব সমান হয়।  ২) ডায়ামিটার এর দৈর্ঘ্য জোড় হলে সেন্টার হবে একটা নোড। আর বিজোড় হলে সেন্টার হবে একটা এজ।  ৩) এখন, ট্রি এর প্রতিটি নোড অথবা এজকে (k এর মান এর উপর নির্ভর করে) ডায়ামিটার এর সেন্টার ধরে দেখবো এই নোড বা এজ সেন্টার হলে কতগুলো নোড রাখা যায় অথবা কতগুলো নোড বাদ দিতে হয়? এভাবে, প্রতিটি নোড হিসেব করে সর্বনিম্ন কয়টা বাদ দেয়া যায় সেটা বের করা সম্ভব। 

Problem Description  here Topic Of This Problem: Dijkstra ১) এই প্রব্লেম সলভ এর জন্য আমরা দুইটা গ্রাফ বানাবো। একটা গ্রাফ ইনপুটে দেয়া থাকবে। আরেকটা গ্রাফ হবে ইনপুটে দেয়া গ্রাফটার রিভার্স(উল্টো) গ্রাফ। ২) অরিজিনাল গ্রাফ ব্যাবহার করে সোর্স থেকে সকল নোডে যাওয়ার ক্ষুদ্রতম দূরত্ব বের করে নিবো। আর রিভার্স গ্রাফ ব্যাবহার করে ডেস্টিনেশন থেকে সকল নোডে যাওয়ার ক্ষুদ্রতম দূরত্ব বের করে নিবো। ৩) এখন, ইনপুটে দেয়া সকল এজ [ U,V ] এর জন্য দেখবো, সোর্স থেকে U নোডের দূরত্ব + [U,V] এজ এর কস্ট + ডেস্টিনেশন থেকে V নোডের দূরত্ব <= P হয় কি না। যদি হয় তার মানে, [U,V] এজ ব্যাবহার করে একটা পসিবল পাথ আছে যার মোট কস্ট P এর সমান অথবা ছোট। তখন, Cost  [U,V] আমার একটা পসিবল এন্সার। এভাবে, সর্বোচ্চ কস্টের যে এজ টা নিয়ে পাথ সম্ভব সেই এজের কস্ট ই হবে আউটপুট। ডায়াক্সট্রা সম্পর্কে জানতে  ক্লিক করুন Happy Coding -_-

Problem Description  here Topic Of This Problem: Dijkstra ১) প্রথমত, অলরেডি এক্সিস্টিং রোড এবং নতুন রোড দুইটি আলাদা ভেক্টরে রাখতে হবে। এবং তাদের কস্টও আলাদা আলাদা ভেক্টরে রাখতে হবে। ২) সাধারণত, ডায়াক্সট্রা তে আমরা প্রায়োরিটি কিউ তে দুইটি ইনফরমেশন রাখি। একটি নোড এবং স্টার্টিং নোড থেকে এই নোডে আসার কস্ট। এখানে আরো একটি ইনফরমেশন রাখা লাগবে। আর তা হলো, এই নোডে আসতে নতুন কয়টা রোড আমি ব্যাবহার করেছি। ৩) স্টার্টিং নোড থেকে প্রতিটি নোডের দূরুত্ব রাখার জন্য আগে আমরা 1D array ব্যাবহার করতাম। আর এখন ব্যাবহার করবো 2D Array . অ্যারের arr[x][y] - নির্দেশ করে স্টার্টিং নোড থেকে x নোডে , y সংখ্যক নতুন রোড ব্যাবহার করে আসার কস্ট। ৪) এরপর আমরা প্রায়োরিটি কিউ এর প্রতিটি এলিমেন্ট ব্যাবহার করে, প্রথমে ওই এলিমেন্ট থেকে এক্সিস্টিং রোড দ্বারা যতোদিকে যাওয়া যায়, গিয়ে কস্ট আপডেট করে দিবো। এরপর, ওই এলিমেন্ট থেকে নতুন রোড দ্বারা যতোদিকে যাওয়া যায় গিয়ে কস্ট আপডেট করবো। সবশেষে ডেস্টিনেশন নোডে ০ থেকে d সংখ্যক নতুন রোড ব্যাবহার করে যেসব কস্টে পৌঁছানো যায় তাদের মধ্যে সর্বনিম্ন কস্ট ই এন্সার। ডায়াক্সট্...

Topic Of This Problem: DFS or BFS Problem Description:  here ১) প্রব্লেম ডেসক্রিপশন অনুযায়ী প্রতিটি নোডের সর্বোচ্চ দুইটা অবস্থা থাকতে পারে।  -> এই নোডে তারা উভয়েই এককভাবে দৌড়ে প্রবেশ করবে।  -> হানজো অন্যজনকে ক্যারি করে প্রবেশ করবে।  ২) টেস্ট কেসে সাইকেল থাকলে একই নোডে একবার তারা প্রথম স্টেট অনুযায়ী প্রবেশ করে তো অন্যবার ২য় স্টেট অনুযায়ী প্রবেশ করতেও পারে।  ৩) এখন আমরা DFS চালিয়ে বর্তমান নোডে আমি যেই অবস্থায় প্রবেশ করেছি, তার এডজাসেন্ট নোডগুলোতে তার ঠিক উলটো অবস্থায় প্রবেশ করার চেষ্টা করবো যদি না এই উলটো অবস্থায় অলরেডি ওই এডজাসেন্ট নোডে প্রবেশ করে না থাকি।  ৪) সবশেষে হিসেব করবো যে স্টেট-২ এর জন্য কয়টি নোড ভিসিট করা হয়েছে। ডিএফএস সম্পর্কে জানতে  ক্লিক করুন  বিএফএস সম্পর্কে জানতে  ক্লিক করুন

Topics of this problem: Strongly Connected Component(SCC) ১) প্রথমেই গ্রাফটির স্ট্রংলি কানেক্টেড কম্পোনেন্ট বের করতে হবে। এবং প্রতিটি কম্পোনেন্ট এর সাইজ এবং ওই কম্পোনেন্ট এ থাকা নোডগুলোর মধ্যে সর্বনিম্ন নোড টি মনে রাখতে হবে।  ২) এরপর, যেই অর্ডার এ গ্রাফটির SCC বের করা হয়েছে তার ঠিক উলটো অর্ডার এ আবার DFS চালাতে হবে। ( মানে তুমি যদি SCC তে স্ট্যাক ব্যাবহার কর, এবার QUEUE ব্যাবহার করবে -_- ) DFS চালিয়ে দেখতে হবে এই কম্পোনেন্ট কোন কোন কম্পোনেন্ট কে স্পর্শ করে। অর্থাৎ, এই কম্পোনেন্ট থেকে কোন কোন কম্পোনেন্ট এ যাওয়া যায়। সেইসব কম্পোনেন্ট এর সাইজকে এই কম্পোনেন্ট এর সাইজের সাথে যোগ করে দিবো। ৩) এবার দেখবে, প্রতিটি কম্পোনেন্ট এর সাইজ কত? যে কম্পোনেন্ট এর সাইজ সর্বোচ্চ সে কম্পোনেন্ট এর সর্বনিম্ন নোড টি আউটপুট হবে। যদি একাধিক কম্পোনেন্ট এর সাইজ সমান পাওয়া যায়, তবে তাদের নোডগুলোর মধ্যে সর্বনিম্ন নোড টি হবে আউটপুট। SCC সম্পর্কে জানতে  ক্লিক করুন