Bappy's Blog

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

Problem Description  here প্রব্লেমটিতে মূলত বলা হয়েছে, একটা ডিকশনারি দেয়া থাকবে যেখানে n টি শব্দ থাকবে। প্রতিটি শব্দের ১ম এবং শেষ ক্যারেক্টার ছাড়া বাকি ক্যারেক্টার গুলো যেভাবে ইচ্ছা সাজানো যায়। এরপর একটি বাক্য দেয়া থাকবে। এই বাক্যের শব্দগুলোও একইভাবে সাজানো যায়। বলতে হবে ডিকশনারি থেকে শব্দ নিয়ে ব্যাকটি কতভাবে গঠন করা যায়?  সলুশ্যন আইডিয়াঃ ১) প্রতিটি শব্দ ডিকশনারী তথা ট্রাই তে ইনসার্ট করার সময়ই ঐ শব্দের ২য় থেকে সর্বশেষ ক্যারেক্টার এর আগ পর্যন্ত সর্ট করে নিবো লেক্সিকোগ্রাফিক্যালি। এবং ট্রাই তে প্রতিটি নোডে কতটা স্ট্রিং শেষ হয়েছে সেটা ক্যালকুলেট করে রাখবো।  ২) এরপর, বাক্যের প্রতিটি শব্দও একইভাবে সর্ট করবো এবং দেখবো ডিকশনারী তে এই শব্দটি কতবার ইনসার্ট আছে। প্রতিটি শব্দের ফ্রিকুয়েন্সী গুণ করে গুণফলই হবে এন্সার।  এখন, প্রব্লেমটি তোমার নিজে নিজে সলভ করার চেষ্টা করা উচিৎ। এরপরও না পারলে নিজ দায়িত্বে সলুশ্যন দেখতে পারো। বিঃদ্রঃ সলুশ্যন দেখে প্রব্লেম সলভ করা ভালো প্র্যাকটিস না। 

Problem Description  here সহজ ভাষায় বলতে গেলে, একটা অ্যারে দেয়া থাকবে। এই অ্যারে থেকে এমন একটা সাবঅ্যারে সিলেক্ট করতে হবে যাতে এই সাবঅ্যারের সব সংখ্যাগুলোর XOR সর্বোচ্চ হয়। একইভাবে, এমন একটা সাবঅ্যারে সিলেক্ট করতে হবে যাতে এই সাবঅ্যারের সংখ্যাগুলোর XOR সর্বনিম্ন হয়। সর্বোচ্চ এবং সর্বনিম্ন সংখ্যাটি প্রিন্ট করতে হবে।  সলুশ্যন আইডিয়াঃ সাবঅ্যারের XOR কথাটি আসলেই মূলত  PrefixXOR এর আইডিয়া আসে।  ১) অ্যারেটির PrefixXOR বের করে রাখবো। এখন, অ্যারের l to r ইনডেক্সের XOR মানে কী?  PrefixXOR[r] ^ PrefixXOR[l-1] ২) ক্রমানুসারে প্রতিটি PrefixXOR এর বিট গুলো নিবো MSB থেকে LSB। আমি যদি এখন PrefixXOR অ্যারের ith পজিশনে থাকি তাহলে ট্রাই তে 0 to (i-1) পজিশন পর্যন্ত PrefixXOR অ্যারের প্রতিটা এলিমেন্ট এর বিট সিকুয়েন্স স্টোর করা আছে।  এখন, বর্তমান এলিমেন্ট এর জন্য এর পূর্বের অল পসিবল সাবঅ্যারের XOR এর কাজটা আমরা ট্রাই তে স্টোরড ডেটা থেকে করতে পারি। কীভাবে? বর্তমান বিট সিকুয়েন্স এর একটা পজিশনে যদি ০ থাকে আমি চেষ্টা করবো ট্রাই এর বর্তমান নোড থেকে ১ এর পথে যেতে। বিট সিকুয়েন্সে যদি...