Bappy's Blog

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

Problem: এই প্রব্লেমে একটি n <= 10^5 সাইজের অ্যারে দেয়া থাকবে। এবং q <= 10^5 টি কুয়েরী এন্সার করতে হবে। প্রতি কুয়েরী তে একটি সংখ্যা X দিবে। অ্যারের এমন একটি সংখ্যার সাথে X কে এক্সর করতে হবে যাতে X^ara[i] সর্বোচ্চ হয়। Solution:  Suggested Problem:  Click here Another one

Problem: এই প্রব্লেমে আমাদেরকে দুটি রুটেড ট্রি ইনপুট হিসেবে দেয়া থাকবে। বলতে হবে, ট্রি দুটি Identical(একই) কি না? অর্থাৎ, রুট ফিক্সড রেখে একই নোডের Child নোডগুলোর সাবট্রি এদিক সেদিক করার পর ট্রি দুটি দেখতে একই হবে কি না।  Solution:

 Problem Description  here Problem: একটি স্ট্রিং দেয়া থাকবে ঐ স্ট্রিং এর সর্বোচ্চ কত লেন্থ এর একটি সাবস্ট্রিং নির্বাচন করা সম্ভব যা একটি প্যালিন্ড্রোম।  Solution: এই প্রব্লেমে স্ট্রিং এর দৈর্ঘ্য যদি ১০০০ এর আশেপাশে হয়, সেক্ষেত্রে এই প্রব্লেম এর একটি ডিপি সল্যুশন সম্ভব যা আমি  পূর্বের এই পর্বে  আলোচনা করেছিলাম। কিন্তু, স্ট্রিং এর দৈর্ঘ্য ১০০০০০ এর মতো হলে আর পূর্বের সল্যুশন কাজ করবে না। সেক্ষেত্রে, আমাদের স্ট্রিং হ্যাশিং দিয়া চিন্তা করতে হবে!  ১) স্ট্রিং টি র সম্ভাব্য সকল প্রিফিক্স এর হ্যাশ ভ্যালু আমাকে প্রিক্যালকুলেট করে রাখতে হবে।  ২) স্ট্রিং টি র সম্ভাব্য সকল সাফিক্স এর হ্যাশ ভ্যালু প্রিক্যালকুলেট করে রাখতে হবে।  ৩) এখন, আমরা জানি সকল প্যালিন্ড্রোম এর সেন্টার পয়েন্ট থাকলে। প্যালিন্ড্রোম এর লেন্থ বিজোড় হলে সেন্টার ১টি। লেন্থ জোড় হলে সেন্টার ২টি।  ৪) প্রতি পজিশন (জোড় লেন্থ এর জন্য দুটি এডজাসেন্ট পজিশন) কে প্যালিন্ড্রোম এর সেন্টার ধরে সর্বোচ্চ কত রেডিয়াস/লেন্থ এর প্যালিন্ড্রোম বানানো যায় সেটি দেখবো। ভালোভাবে লক্ষ্য করলে দেখবে যে, প্রতি পজিশন কে সেন্টার ধরে বাইনারী সার্চ চালালেই আমরা সর

Problem Description  here Problem: একটি স্ট্রিং দেয়া থাকবে। ঐ স্ট্রিং থেকে সর্বোচ্চ কত লেন্থ এর সাবসিকুয়েন্স নেয়া সম্ভব যেটি একটি প্যালিন্ড্রোম হবে?  Solution:

Problem: একটি স্ট্রিং দেয়া থাকবে। ঐ স্ট্রিং এর সর্বোচ্চ কত লেন্থ এর সাবস্ট্রিং সম্ভব যেটি একটি প্যালিন্ড্রোম।  Solution: Suggested problem Happy Coding

এই পর্বে আমরা খুবই ইন্টারেস্টিং একটি বিষয় নিয়ে আলোচনা করবো।  মনে করো, তোমাকে একটি  n * m সাইজের গ্রীড দেয়া আছে। গ্রীডের প্রতিটি সেল এর ভ্যালু,   grid[i][j] = i+j তাহলে, একটি ৩ * ৩ সাইজের গ্রীড দেখতে যেমন হবেঃ  একটি মজার বিষয় লক্ষ্য করেছো কী? কোন একটি সেলের ভ্যালু যদি জোড় হয় তবে তার এডজাসেন্ট সেলগুলোর ভ্যালু বিজোড়। আর কোন সেলের ভ্যালু যদি বিজোড় হয় তবে তার এডজাসেন্ট সেলের ভ্যালু জোড়। এখানে দুটি সেল তখনই এডজাসেন্ট বিবেচ্য হবে যখন তারা একটি সাইড শেয়ার করে।  গ্রীডের এই প্রোপার্টি টা খুবই সিম্পল। কিন্তু, আমরা অনেকেই হয়তো খেয়াল করি নি এর আগে। আর এটি কতোটা গুরুত্বপূর্ণ প্রোপার্টি তা  এই প্রব্লেম  সলভ করতে গিয়ে অনুধাবন করেছি 😛 হ্যাপি কোডিং 😊

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 Coding 😊