Bappy's Blog

Code: Related Problem Happy Coding

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে একটি ইন্টিজার অ্যারে দেয়া থাকবে যেখানে দুটি সংখ্যা ব্যাতিত বাকি সংখ্যাগুলো দুইবার করে থাকবে এবং ঐ দুটি সংখ্যা একবার করে থাকবে। বলতে হবে সংখ্যা দুটি কি কি? আমাদেরকে এই কাজ O(n) Time Complexity এবং O(1) Memory Complexity তে করতে হবে।  Solution: আমরা জানি, একই সংখ্যাকে জোড় সংখ্যক বার এক্সর করলে ফলাফল শূন্য হয়। ধরে নেই, অ্যারেতে একবার করে থাকা সংখ্যা দুটি x এবং y । তাহলে, z = a[1] ^ a[2] ^ ... ^ a[n] = x ^ y এখন, যেহেতু সংখ্যা দুটি একবার করে আছে তার মানে x এবং y দুটি ভিন্ন সংখ্যা! সুতরাং, তাদের এক্সর করলে অন্তত এমন একটি বিট থাকবে যে বিট সংখ্যাদ্বয়ের মধ্যে তফাৎ গড়ে দিবে! তাই, z = x ^ y হলে z এর সর্বডানের কোন বিট টি অন আছে সেটি দেখবো। মনে করি, z = x^y এর সর্বডানের অন বিট টি হলো kth Bit এখন, তাহলে অ্যারের যেসব সংখ্যার kth Bit অন তাদের এক্সর করলে সেটি হবে দুটির সংখ্যার একটি সংখ্যা x । কারণ , x ভিন্ন অন্য কোন সংখ্যার kth Bit ON থাকলেও সেটি দুইবার থাকবে যেকারণে সেখানে শুধু x ই থেকে যাবে।  এখন অপর সংখ্যা y...

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে একটি ইন্টিজার অ্যারে দেয়া থাকবে যেখানে একটি সংখ্যা বাদে বাকি সংখ্যাগুলো এক্সেক্টলি দুইবার করে থাকবে এবং ঐ সংখ্যাটি একবার থাকবে।  আমাদেরকে একবার থাকা সংখ্যাটি বের করতে হবে। O(n) Time Complexity এবং O(1) Memory Complexity তে কাজটি করতে হবে।  Solution: বিটওয়াইজ অপারেশনগুলো নিয়ে মোটামুটি ধারণা আছে এমন যেকেউ প্রথম দেখায় প্রব্লেমটি সলভ করতে পারবে। আমরা জানি, 1 XOR 1 = 0 0 XOR 0 = 0 1 XOR 0 = 1 0 XOR 1 = 1 বিটওয়াইজ এক্সর এর ফর্মুলা গুলো জানা থাকলে দেখবে যে একই সংখ্যা দুইবার এক্সর করলে ফলাফল শূন্য! আসলে, দুইবার নয়। যেকোন জোড় সংখ্যকবার একটি সংখ্যাকে এক্সর করলে ফলাফল শূন্য। যেহেতু, অ্যারে তে ১টি সংখ্যা বাদে বাকিসব সংখ্যা ই দুইবার করে আছে সেহেতু অ্যারের সবগুলো সংখ্যা এক্সর করলে যে সংখ্যাটি পাওয়া যায় সেটিই আমাদের কাঙ্ক্ষিত সংখ্যা। 

এই পর্ব পড়ার আগে  Range GCD & Point Update  পর্বটি পড়া আবশ্যক।   Problem: এই প্রব্লেমে আমাদের একটি অ্যারে দেয়া থাকবে n সাইজের এবং q সংখ্যক কুয়েরী এন্সার করতে হবে। দুই ধরনের কুয়েরী থাকবে।  1 L R                অ্যারের L থেকে R Index পর্যন্ত সংখ্যাগুলোর GCD বের করতে হবে। 2 L R x              অ্যারের L থেকে R ইনডেক্স পর্যন্ত সংখ্যাগুলোর ভ্যালু x বাড়াতে হবে।  Solution: আমরা জানি,  GCD(a , b) = GCD(a , b-a) = GCD(a-b , b) = GCD(abs(a-b) , a) = GCD(abs(a-b) , b) GCD(a , b , c) = GCD(a , GCD(b , c)) উপরোক্ত দুটি সমীকরণ থেকে লিখতে পারি, GCD(a , b , c) = GCD(a , GCD(b-a , c-b)) অর্থাৎ, GCD(a[l] , a[l+1] , a[l+2] , ... , a[r]) = GCD(a[l] , a[l+1]-a[l] , a[l+2]-a[l+1] , ... , a[r]-a[r-1]) এখন, এই প্রব্লেম এ আমরা দুটি সেগমেন্ট ট্রি ব্যাবহার করবো।  ১) ১ম সেগমেন্ট ট্রি তে আমরা মূল অ্যারের বর্তমান অবস্থা কি সেটার হিসাব রাখবো। অর্থাৎ, মূল অ্যারের কোন ইনডেক্সের ভ্যালু বর্তমানে...

 Problem: এই প্রব্লেমে আমাদের একটি অ্যারে দেয়া থাকবে n সাইজের এবং q সংখ্যক কুয়েরী এন্সার করতে হবে। দুই ধরনের কুয়েরী থাকবে।  1 L R           অ্যারের L to R index পর্যন্ত সংখ্যাগুলোর GCD বের করতে হবে।  2 pos x         অ্যারের pos তম পজিশনের ভ্যালু x বাড়িয়ে দাও।  Solution: সেগমেন্ট ট্রি এর রেঞ্জ কুয়েরী এবং পয়েন্ট আপডেট সম্পর্কে ধারনা থাকলেই এই প্রব্লেম সলভ করা সম্ভব। তাই বিস্তারিত আলোচনা না করে সরাসরি কোডে যাচ্ছিঃ  Suggested problem Happy Coding 

শুরুতেই বলে রাখি এই এপিক টপিক আমি শিখেছি এই  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 মিনিমাইজ করা। ভালোভাবে লক্ষ্য করলে দেখবে যে, এর মানে হচ্ছে উভয় প্লেয়ার  চায় তার নিজের স্কোর যতোটা সম্ভব বাড়াতে। ২) কিন্তু, আমরা একই সাথে উভয় প্লেয়ার এর স্কোর নিয়ে কাজ করতে পারি না। তাহলে উপায়? আরেকটি ব্যাপার কি লক্ষ্য করেছো? অ্যারের যেসব ভ্যালু ১ম প্লেয়ার নিবে না সেগুলো অবশ্যই ২য় প্লেয়ার নিবে!  তাহলে, ব্য...