Bappy's Blog

শুরুতেই বলে রাখি এই এপিক টপিক আমি শিখেছি এই  CF Blog  থেকে।  SOS DP: SOS(Sum Over Subset) মূলত একটি সংখ্যার সবগুলো সাবমাস্ক এফিসিয়েন্টলি ইটারেট করে।  সাবমাস্ক কি?           একটি সংখ্যা x এর একটি সাবমাস্ক হবে y যদি x & y = y হয়।            সহজ ভাষায় বললে, একটি সংখ্যার kth বিট যদি 0 হয় তবে তার সাবমাস্ক এর kth বিট অবশ্যই 0               হবে এবং যদি সংখ্যাটির kth বিট 1 হয় তবে তার সাবমাস্কের kth বিট 0 অথবা 1 যেকোন কিছু হতে           পারে।                    তাহলে, একটি সংখ্যার On bit যদি k টা হয় তবে তার সাবমাস্ক হতে পারে 2^k টা। এখন ধরে নেই, S(mask) = {x : x & mask = x} অর্থাৎ, S(mask) হচ্ছে mask সংখ্যাটির সাবমাস্কের সেট।  S(mask , i) হচ্ছে মাস্কের এমন সব সাবমাস্কের এর সেট যাদের 0th to ith পজিশনের বিটগুলো শুধু পরিবর্তন হতে পারবে।  এখন, S এবং সাব...

 Problem Description  here Problem: এই প্রব্লেমে তোমাকে n সংখ্যক থালা দেয়া হবে। প্রতিটি থালা তে ১টি, ২টি অথবা ৩টি করে খাবার থাকবে। যতোক্ষণ না পর্যন্ত সবগুলো থালার সবগুলো খাবার শেষ না হয় ততোক্ষণ পর্যন্ত তুমি একটি ছক্কার গুটি নিক্ষেপ করবে যেখানে 1 to n পর্যন্ত সংখ্যাগুলো দেখানোর সম্ভাব্যতা সমান। ছক্কা নিক্ষেপে যদি i সংখ্যাটি উঠে তাহলে তুমি i তম থালার একটি খাবার খাবে। যদি i তম থালায় কোন খাবার না থাকে তাহলে কিছুই করা লাগবে না। তোমাকে বলতে হবে সবগুলো থালার সব খাবার শেষ করতে এক্সপেক্টেড কত সময় লাগবে?  এই প্রব্লেমটি সলভ করতে  Expected Value  সম্পর্কে জানা জরুরী।  Recursive Solution: Next Episode  

 Problem Description  Click here এটি ইন্টারভাল ডিপির আরো একটি প্রব্লেম।  Problem: একটি সারিতে তোমাকে n টি Slime দেয়া আছে। এবং তাদের সাইজের অ্যারে a[n] দেয়া আছে। এখন তোমাকে সবগুলো Slime কম্বাইন করে একটি বড় Slime তৈরী করতে হবে। দুটি Slime শুধুমাত্র তখনই কম্বাইন করা যাবে যখন তারা পাশাপাশি অবস্থিত হবে। এবং দুটি Slime এর কস্ট X এবং Y হলে তাদেরকে কম্বাইন করার কস্ট হবে X+Y। বলতে হবে, সর্বনিম্ন কত কস্টে সবগুলো Slime কম্বাইন করা যায়?  Recursive Solution: ১) আমরা প্রব্লেমটিকে একটু উল্টোভাবে চিন্তা করি। অর্থাৎ, ধরে নেই শুরুতে সবগুলো Slime কম্বাইন করা আছে। আমাকে বের করতে হবে সবগুলো Slime আলাদা করার সর্বনিম্ন কস্ট।  একটি Slime কে দুইভাগে ভাগ করার কস্ট হবে ঐ Slime এর মোট সাইজ। ২) স্টেট হবে দুটি। স্টেট-১ঃ lft          (Starting position of this combined slime) স্টেট-২ঃ rgt         (Ending position of this combined slime) dp[lft][rgt] মানে হচ্ছে, ara[lft...rgt] সবগুলো Slime কম্বাইনড অবস্থায় আছে। তাদেরকে আলাদা করার কস্টই dp[lft][rg...

 Problem Description  here Problem: এই প্রব্লেমে দুইজন প্লেয়ার একটি গেম খেলবে। যেটা হবেঃ একটি পাথরের স্তূপ আছে যেখানে K সংখ্যক পাথর আছে। এবং n টি সংখ্যার একটি অ্যারে দেয়া আছে। প্রথম চাল দিবে ১ম জন, ২য় চাল ২য় জন, ৩য় চাল ১ম জন, ৪র্থ চাল ২জন, এভাবে খেলা চলতে থাকবে। প্রতি চালে একজন প্লেয়ার অ্যারে থেকে যেকোন একটি সংখ্যা নিবে এবং এক্সেক্টলি ততোগুলো পাথর স্তূপ থেকে ফেলে দিবে। যদি কোন প্লেয়ার তার চালে কোন পাথরই না ফেলতে পারে তবে সে হারবে।  বলতে হবে, দুইজন প্লেয়ারই অপ্টিমালি খেললে কে জিতবে?  Recursive Solution:  ১) এই প্রব্লেমে আমাদের স্টেট নিতে হবে দুটি।     স্টেট-১ঃ বর্তমানে স্তুপে কয়টি পাথর অবশিষ্ট আছে।     স্টেট-২ঃ এখন কোন প্লেয়ার চাল দিবে।  ২) সল্যুশনে আমরা প্রথম প্লেয়ার কে ০তম এবং ২য় প্লেয়ার কে ১তম প্লেয়ার হিসেবে বিবেচনা করেছি। ৩) বেস কেসে পৌঁছানো মানে এখন আর চাল দেয়া সম্ভব নয়। অর্থাৎ, বেস কেসে যদি ১ম প্লেয়ার পৌঁছায় তার মানে ২য় প্লেয়ার উইনার আর যদি ২য় প্লেয়ার পৌঁছায় তার মানে ১ম প্লেয়ার উইনার।  ৪) বেস কেস ভিন্ন, যেহেতু দুইজন প্লেয়ার অপ্...

 Problem Description  here Problem: এটি মূলত ইন্টারভাল ডিপির একটি প্রব্লেম। এই প্রব্লেমে দুইজন প্লেয়ার একটি গেম খেলবে। গেমটা হচ্ছে, n সাইজের একটি অ্যারে দেয়া আছে। প্রতি চালে একজন প্লেয়ার অ্যারের সর্ববামের অথবা সর্বডানের ভ্যালুটা নিবে এবং সেটি অ্যারে থেকে বাদ দিবে। ১ম প্লেয়ার এর মোট স্কোর X এবং ২য় প্লেয়ার এর মোট স্কোর Y হলে, ১ম প্লেয়ার চাইবে X-Y ম্যাক্সিমাইজ করতে এবং ২য় প্লেয়ার চাইবে X-Y মিনিমাইজ করতে। ২জন প্লেয়ার অপ্টিমালি খেলবে।  উল্লেখ্য যে, ১ম চাল ১ম প্লেয়ার এর, ২য় চাল ২য় প্লেয়ার, ৩য় চাল ১ম প্লেয়ার, ৪র্থ চাল ২য় প্লেয়ার এভাবে চলবে।  Recursive Solution: ১) এই প্রব্লেমে প্রথম প্লেয়ার এর টার্গেট হচ্ছে X-Y ম্যাক্সিমাইজ করা এবং ২য় প্লেয়ার এর টার্গেট হচ্ছে X-Y মিনিমাইজ করা। ভালোভাবে লক্ষ্য করলে দেখবে যে, এর মানে হচ্ছে উভয় প্লেয়ার  চায় তার নিজের স্কোর যতোটা সম্ভব বাড়াতে। ২) কিন্তু, আমরা একই সাথে উভয় প্লেয়ার এর স্কোর নিয়ে কাজ করতে পারি না। তাহলে উপায়? আরেকটি ব্যাপার কি লক্ষ্য করেছো? অ্যারের যেসব ভ্যালু ১ম প্লেয়ার নিবে না সেগুলো অবশ্যই ২য় প্লেয়ার নিবে!  তাহলে, ব্য...

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে n সাইজের একটি অ্যারে দেয়া হবে। K সংখ্যক ক্যান্ডি n সংখ্যক বাচ্চাদের মধ্যে এমনভাবে ভাগ করে দিতে হবে যাতে ith বাচ্চার প্রাপ্ত ক্যান্ডির সংখ্যা 0 থেকে a[i] এর মধ্যে হয়। এবং কোন ক্যান্ডি বাকি থাকা যাবে না। বলতে হবে, কতভাবে ক্যান্ডিগুলো বিতরণ করা যাবে? Solution: ইতোপূর্বে লিখা ডিপি অপ্টিমাইজেশনের পর্বগুলো পড়ে থাকলে এই প্রব্লেমটি সলভ করা অনেকটা সহজ যে কারণে এই প্রব্লেম নিয়ে আর বিস্তারিত আলোচনা করছি না। সল্যুশন দেখা যাকঃ Next Episode Happy Coding

 Problem Description  here Problem: এই প্রব্লেমটি সাধারণ একটি ন্যাপসেক প্রব্লেম যা দিয়েই মূলত আমরা ডিপি শেখা শুরু করি। যেকারণে, এই প্রব্লেমের বিস্তারিত আলোচনা করবো না।  Recursive Solution: Iterative Solution: Next episode Happy Coding

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে দুটি স্ট্রিং দেয়া থাকবে। আমাদেরকে স্ট্রিং দুটির Longest Common Subsequence প্রিন্ট করতে হবে। যদি LCS এর লেন্থ বের করতে বলতো তাহলে শুধু ডিপি করা পর্যন্তই সীমাবদ্ধ থাকতো। কিন্তু, এখানে ডিপি সল্যুশন প্রিন্ট করতে হবে।  Recursive Solution: ১) এই প্রব্লেমের জন্য আমাদের দুটি স্টেট রাখতে হবে। একটি হচ্ছে আমি বর্তমানে প্রথম স্ট্রিং এর কোন পজিশনে আছি এবং অন্যটি হচ্ছে আমি এখন দ্বিতীয় স্ট্রিং এর কোন পজিশনে আছি।  ২) যদি s1[pos1] == s2[pos2] হয় তবে এই ম্যাচটি কাউন্ট করে দুটি স্টেট এর ভ্যালু ১ বাড়িয়ে পরবর্তী ট্রাঞ্জিশনে যাওয়া ই বেটার। ৩) অন্যথায়, একবার pos1 কে বাড়িয়ে দেখবো এবং আবার pos2 কে বাড়িয়ে দেখবো। এবং LCS ম্যাক্সিমাইজ করবো।  এবার সল্যুশন প্রিন্ট কিভাবে করবো?  যেকোন রিকার্সিভ ডিপি প্রব্লেমের সল্যুশন প্রিন্ট এর ধাপগুলোঃ ১) হুবহু ডিপি ফাংশনটি কপি করে আরেকটি ফাংশন বানাবো যার রিটার্ণ টাইপ হবে void. ২) বেসকেসে শুধু return লিখবো। ৩) dp[state-1][state-2]...[state-k] != -1 হলে ক্যালকুলেটেড ভ্যালুটি রিটার্ণ করো এই লাইনদ...

 Problem Description  here Problem: এই প্রব্লেমে আমাদের মূলত একটি DAG দেয়া থাকবে। Longest Directed Path এর লেন্থ বের করতে হবে।  Solution: এই প্রব্লেমে আমরা মূলত প্রতিটি নোড থেকে DFS ছেড়ে দেখবো যে কত Depth এ যাওয়া সম্ভব। এভাবে প্রতিটি নোডের জন্য প্রাপ্ত ভ্যালু নিয়ে এন্সার ম্যাক্সিমাইজ করবো।  Next Episode Happy Coding 

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে n * m সাইজের একটি 2D গ্রীড দেয়া থাকবে যার কিছু সেল ফাঁকা এবং কিছু সেল ব্লকড। ফাঁকা সেলগুলো দিয়েই শুধু হাঁটা সম্ভব। তোমাকে বের করতে হবে (1,1) সেল থেকে (n,m) সেলে যাওয়ার মোট কয়টি পাথ আছে যদি তুমি শুধুমাত্র নিচের এবং ডানের সেলে মুভ করতে পারো।  Recursive Solution: ১) এই প্রব্লেমে স্টেট হবে দুটি। একটি আমি বর্তমানে গ্রীডের কত নং সারিতে আছি এবং অন্যটি কত নং কলামে আছি। ২) এরপর আমি বর্তমান সেল থেকে নিচের সেলে মুভ দিবো যদি সেটি ফাঁকা এবং গ্রীডের ভিতরে অবস্থিত হয় এবং বর্তমান সেল এর ডানের সেলে মুভ দিবো যদি সেটি ফাঁকা এবং গ্রীডের ভিতরে অবস্থিত হয়। ৩) যখন আমরা (n,m) সেলে পৌছাবো সেটি হবে বেস কেস। এবং বেস কেসে ১ রিটার্ন করবো।  Iterative Solution: গত পর্বগুলো সব পড়ে আসলে এতোক্ষণে তুমি নিশ্চয়ই ইটারেটিভ ডিপি ভালোই বুঝো। যেকারণে বিস্তারিত ব্যাখ্যায় গেলাম না 😛 Next Episode Happy Coding 

 Problem Description  here Problem : n সংখ্যক কয়েন দেয়া আছে। যেখানে ith কয়েন টস করলে হেড উঠার সম্ভাব্যতা P[i] এবং টেল উঠার সম্ভাব্যতা 1 - P[i] সবগুলো কয়েন টস করলে টেল এর থেকে হেড বেশি পাওয়ার সম্ভাব্যতা কত সেটি বের করতে হবে।  Recursive Solution: ১) এই প্রব্লেমে আমাদের স্টেট নিতে হবে ২টি। একটি হচ্ছে, এখন কত তম কয়েন টস করবো অর্থাৎ পজিশন এবং অন্যটি হলো এখন পর্যন্ত কয়টি কয়েন এ হেড পেয়েছি। ২) বেস কেসে এ চেক দিবো যে টেল এর থেকে বেশি সংখ্যক হেড পেয়েছি কি না। যদি পাই তাহলে ১ রিটার্ন করবো। অন্যথায় ০ রিটার্ন করবো। ০ রিটার্ন করার অর্থ হচ্ছে ডিপি ট্রি এর রুট নোড থেকে বর্তমান নোড পর্যন্ত যে পাথ সেটি ভ্যালিড কোন পাথ না। ৩) প্রতিটি সাব-প্রব্লেম এ হেড উঠলে টেল অপেক্ষা বেশি হেড পাওয়ার সম্ভাব্যতা কত বের করবো এবং টেল উঠলে টেল অপেক্ষা হেড বেশি পাওয়ার সম্ভাব্যতা কত বের করবো। এবং দুটি ফলাফল যোগ করবো।  ভালোভাবে লক্ষ্য করলে বুঝবে যে এখানে আমরা টেল অপেক্ষা হেড বেশি পাওয়ার যে সম্ভাব্যতা সেটি রিটার্ন করছি সর্বদা। dp[i][j] বলতে বোঝানো হচ্ছে 1st to ith পজিশন পর্যন্ত j সংখ্যক হেড পেলে টেল অপেক্ষা ...

Problem Description  here Problem: এই প্রব্লেমটির সঙ্গে আগের প্রব্লেমের পার্থক্য হচ্ছে, আগের প্রব্লেমে একঘর অথবা দুইঘর জাম্প দেয়া যেতো কিন্তু এই প্রব্লেমে সর্বোচ্চ k ঘর জাম্প দিতে পারবো।  Recursive Solution: ১) এই প্রব্লেমেও আমাদের স্টেট থাকবে পজিশন।  ২) এরপর প্রতি পজিশন থেকে ১ঘর, ২ঘর,..., k ঘর জাম্প করে দেখবো কত খরচ হয়। এদের মধ্যে মিনিমাম খরচ টি ই রিটার্ন করবো।  বুঝতেই পারতেছো প্রতিবার সর্বোচ্চ k ঘর জাম্প দেয়ার জন্য k সাইজের একটি ইনার লুপ ব্যাবহার করতে হবে। Iterative Solution: এই প্রব্লেমের ইটারেটিভ সল্যুশন প্রায় আগের প্রব্লেমের সল্যুশন এর মতোই। শুধুমাত্র একটি অতিরিক্ত ইনার লুপ ব্যাবহার করতে হবে k ঘর পর্যন্ত জাম্প করার জন্য।  Next episode Happy Coding

 Problem Description  here Problem: এই প্রব্লেমে বলা হয়েছে, তুমি n দিনের ছুটিতে যাবা। ছুটির প্রতিটি দিন তুমি প্রব্লেমে উল্লেখিত ৩টি কাজের যেকোন একটি করতে পারবে। ১ম কাজ করলে তুমি a[i], ২য় কাজ করলে তুমি b[i], ৩য় কাজ করলে c[i] পয়েন্ট পাবা। এখন তোমাকে বের করতে হবে সর্বোচ্চ কত পয়েন্ট পাওয়া সম্ভব যদি তুমি পরপর দুইদিন একই কাজ না কর।  Recursive Solution: ১) এই প্রব্লেমে আমাদের দুটি স্টেট লাগবে। একটি হচ্ছে বর্তমানে আমি কোন পজিশনে আছি এবং অন্যটি হচ্ছে ঠিক আগের পজিশনে আমি উল্লেখিত ৩টি কাজের মধ্যে কোনটি করে আসছি। ২) এরপর, প্রতি পজিশনের জন্য আমি ৩টি কাজের মধ্যে সেসব কাজের জন্য মোট পয়েন্ট বের করবো যে কাজ ঠিক আগের পজিশনে করা হয় নি।  এবং সেখান থেকে মোট পয়েন্ট এর পরিমাণ ম্যাক্সিমাইজ করবো।  Iterative Solution: ১) একটু ভালোভাবে লক্ষ্য করলে দেখবে যে ১ম পজিশনে আমরা যেকোন একটি কাজ করতে পারি। শর্ত চলে আসে ২য় পজিশন থেকে। ২য় পজিশনে আমরা সেই কাজটি করতে পারি না যা অলরেডি ১ম পজিশনে করে এসেছি। ২) তার মানে ২য় থেকে পরবর্তী পজিশন গুলোতে আমি ১ম কাজ করলে ১ম কাজের জন্য প্রাপ্ত পয়েন্ট এর সাথে যোগ ...

কিছু কথাঃ DP Series এ আমি মূলত  At Coder Educational DP  কন্টেস্টের প্রব্লেমগুলো নিয়ে আলোচনা করবো এবং সেই সাথে ডিপি সল্যুশন প্রিন্ট, ডিপি অপটিমাইজেশনসহ আরো কিছু বিষয় নিয়ে আলোচনা করবো।  এই সিরিজ টি পড়া শুরু করার আগে সবার ব্যাসিক ডিপি সম্পর্কে ধারণা থাকা আবশ্যক।  এজন্য  শাফায়েতের ব্লগ  থেকে ডাইনামিক প্রোগ্রামিং এর সবগুলো পর্ব পড়ে নেয়ার জন্য অনুরোধ করছি।  Problem Description  here Problem: প্রব্লেমটিতে বলা হয়েছে, আমাদেরকে n টি পাথর দেয়া থাকবে। এবং প্রতিটি পাথরের উচ্চতা দেয়া থাকবে।  একটি ব্যাঙ শুরুতে ১নম্বর পাথরে আছে। ব্যাঙ টি একঘর অথবা দুইঘর জাম্প করতে পারে। অর্থাৎ, i তম পাথর থেকে i+1 or i+2 তম পাথরে যেতে পারে। ith থেকে jth পাথরে যেতে তাকে দুইটি স্টোনের উচ্চতার পার্থক্যের সমান টাকা খরচ করতে হয়।  বের করতে হবে n তম পাথরে পৌঁছাতে তাকে সর্বনিম্ন কত খরচ করতে হবে?  Recursive Solution: ১) এই প্রব্লেমের জন্য আমাদের কয়টি স্টেট লাগবে? ভালোভাবে লক্ষ্য করলে বুঝবে শুধুমাত্র পজিশন ই স্টেট হিসেবে রাখা যথেষ্ট।  ২) এরপর, প্রতি পজিশন থেকে আমি একবা...

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

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

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে n সংখ্যক ডাইস দেয়া থাকবে। প্রতিটি ডাইসের k সংখ্যক তল থাকে যাদেরকে 1,2,3,....,k দ্বারা সংখ্যায়িত করা হয়। আমি ডাইসগুলো যেকোনভাবে সাজাতে পারি। সাজানোর পর যদি সকল ডাইসের উপরের তলের সংখ্যাগুলোর যোগফল S এর সমান হয় তবে স্কোর হবে উপরের তলের সংখ্যাগুলোর গুণফলের সমান।  এখন, আমাকে যতোগুলো ভ্যালিড ওয়ে তে সাজানো যায় সবগুলোর জন্য স্কোর এর যোগফল হিসেব করতে হবে।   এই প্রব্লেমটি আমার সলভ করা ডিপি অপটিমাইজেশনের অন্যতম মজার একটি প্রব্লেম। এই প্রব্লেম সলভ করার আগে আমি ডিপি অপটিমাইজেশন নিয়ে যে পর্বগুলো লিখেছি সবগুলো পড়ে আসতে হবে। এবং DICE-1 প্রব্লেমটি সলভ করে আসতে হবে।  DP Optimization-1 DP Optimization-2 DP Optimization-3 DP Optimization-4 Light OJ 1145 Solution: ১) Prerequisite গুলো পূরণ করে আসলে দুইটা প্রব্লেম ই সিমিলার মনে হবে শুরুতেই। DICE(I) এর সল্যুশনে প্রথম যে ফাংশনটি লিখেছিলাম আমি ঠিক সেরকম একটি ফাংশন লিখতে পারবা এই প্রব্লেমের জন্য যাতে ছোট Constraint এর জন্য কাজ করে?  আগের প্রব্লেমের সল্যুশনে ২৯ নাম্বার লাইনটি ...

 Problem Description  here এই প্রব্লেমটি নিয়ে বিস্তারিত আলোচনা করবো না। কারণ ইতোমধ্যেই আমি ডিপি অপটিমাইজেশন এর যে পর্বগুলো লিখেছি সেগুলো যথেষ্ট এই প্রব্লেম সলভ করার জন্য।  DP Optimization-1 DP Optimization-2 DP Optimization-3 DP Optimization-4 তোমার উচিৎ উপরোক্ত পর্বগুলো পড়ে প্রব্লেমটি নিজে নিজে সলভ করার চেষ্টা করা।  এরপরও ব্যার্থ হলে নিচের কোড দেখতে পারো। কোডটিকে ধাপে ধাপে অপটিমাইজ করার চেষ্টা করেছি যাতে ভালোভাবে বুঝতে পারো।  Next Episode Happy Coding😊

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

 Problem Description  here Problem: এই প্রব্লেমে আমাকে একটি স্ট্রিং s দেয়া থাকবে এবং একটি পজিটিভ সংখ্যা d দেয়া থাকবে। বলতে হবে স্ট্রিং টির এমন কতটি পারমুটেশন সম্ভব যা d দ্বারা ডিভিজিবল। Solution: ১) Constraint এর দিকে লক্ষ্য করলে দেখবে স্ট্রিং লেন্থ মাত্র ১০। বুঝতেই পারতেছো এটি মূলত বিটমাস্ক ডিপির একটি প্রব্লেম।  ২) এই প্রব্লেমে আমার দুটি স্টেট নেয়া দরকার।       স্টেট-১ঃ এখন পর্যন্ত স্ট্রিং এর কোন কোন পজিশনের ডিজিট টি ব্যাবহার করেছি।     স্টেট-২ঃ এখন পর্যন্ত বানানো সংখ্যাটি কে d দ্বারা মড করলে মড ভ্যালু কত।  এখানে, মড ভ্যালু ক্যালকুলেট করবো কিভাবে? নিজে নিজে চিন্তা কর।  ৩) আমি যদি সবগুলো ডিজিট ব্যাবহার করে ফেলি তাহলে রিকার্শন থামাতে হবে। যদি মড ভ্যালু ০ হয় তার মানে আমার বানানো সংখ্যাটি d দ্বারা বিভাজ্য তাই ১ রিটার্ন করবো। অন্যথায়, ০ রিটার্ন করবো। এটি হবে Base Case।  ৪) সমস্যা কিন্তু এখনো সমাধান হয় নি! কম্বিনেটরিক্স এর সামান্য একটু কাজ বাকি আছে। আশা করি সেটি তুমি নিজেই পারবে।  বিটমাস্ক ডিপি সম্পর্কে ধারণা থাকলে এখন প্রব্লেম...