Randomized Algorithm – Competitive Programming – Part 2

আজকের এই পর্বে একটা string related প্রবলেম নিয়ে আলোচনা করা হবে। Problem Statement:  তোমাকে 1000 টা unique string দেয়া হবে। প্রতিটা string এর সাইজ 6। এই 1000 টা string এর মধ্যে একটি string আছে যেটাকে বলা হবে secret string। এই secret string কোনটা,সে ব্যাপারে তুমি কিছুই...

Randomized Algorithm – Competitive Programming – Part 1

Randomized Algorithm! হ্যালো! আজকের এই পর্বটি সাজানো হয়েছে Competitive Programming এর একটি কম আলোচিত বিষয় নিয়ে। Randomized Algorithm নিয়ে প্রথম পড়েছিলাম Codeforces এর blog থেকে। এরপর Famous Contestant Errichto এর ইউটিউব ভিডিও গুলো দেখে খুব মুুুুুগ্ধ হয়েছিলাম, বিশেষ...

গ.সা.গু. এবং ল.সা.গু. – Mind Blown

নামটা ইচ্ছা করেই এমন দেয়া। আজ এমন একটা সমস্যা ( আচ্ছা,সমস্যা তো একটা না,দুইটা ) নিয়ে আলোচনা করবো,যেটার নাম শোনার পর যে কারো মনে হবে যে এটা অদ্ভূত রকম সহজ একটা সমস্যা,তবে প্রথমবার সমাধান করতে গেলে কিছুটা বিপাকে পড়ে যেতে হয় মাঝেমধ্যে। সমস্যাটা তাহলে বলিঃ আরেকটা হচ্ছেঃ  ...

ফ্লয়েড ওয়ার্শাল – সব নোড থেকে সব নোডে যাওয়ার সর্বনিম্ন দুরত্ব

গবলিনদের সাথে তো এই দুই পর্বে ভালই টেক্কা দিলাম। তারা দুই দুইটা গোল খেয়ে খুবই রেগে। তারা ছুড়ে দিল আরও কঠিন এক চ্যালেঞ্জ। এবার তোমাকে বলতে হবে এক ভল্ট থেকে অন্য যেকোনো ভল্টে যাওয়ার সর্বনিম্ন দুরত্ব কত। আরে এ আর এমন কী? সব ভল্টে গিয়ে ডায়াক্সট্রা করে দিয়ে আসবো! কিন্তু...

নেগেটিভ সাইকেল খুজে বের করা – বেলম্যান ফোর্ড

আগের পর্বে আমরা দেখেছি কীভাবে ডায়াক্সট্রার এলগরিদম ব্যবহার করে গ্রিনগটসের সব ভল্টে যাওয়ার সর্বনিম্ন দুরত্ব বের করা যায়। আমাদের এত সহজে তাদের সব রহস্য জেনে যাওয়া গবলিনদের পছন্দ হলো না। কারণ কোনো গবলিনই স্বীকার করতে চায় না যে তারা মানুষের সাহায্য নিয়েছে! তারা নতুন এক...

Combinatorics and Chill

হ্যালো। আজকে আমরা কম্বিনেশনের একটি প্রব্লেম নিয়ে আলোচনা করব।   প্রব্লেমঃ ধর, তোমাকে একটি শব্দ বানাতে হবে। এটার জন্য তুমি কোন letter EXACTLY কতবার ব্যবহার করতে পারবে তা বলা আছে। এখন তোমাকে বলতে হবে কতভাবে তুমি এই letter গুলা ব্যবহার করে word বানাতে পারবে। তবে একটা...

ডায়াক্সট্রা, ডিজক্সাত্রা নয়! (Dijkstra’s Algorithm for Shortest Path)

হ্যারি পটারের কথা তো সবাই শুনেছি। তো উইজার্ডদের ব্যাংক হল গ্রিনগটস, যার ভল্টগুলো কি না মাটির নিচে। সেখানে এক ভল্ট থেকে আরেক ভল্টে যেতে হয় কার্টে করে, যার দায়িত্বে থাকে একজন গবলিন। এত হাজার হাজার ভল্টের কোনটায় যেতে হলে কোন পথে যেতে হবে, তা তারা মনে রাখে কীভাবে? জাদুকরী...

পর্যায়ক্রমিক Permutation!

হ্যালো বন্ধুগণ। এটা আমার প্রথম পোস্ট। কিন্তু এই ব্যাপারে গল্প আরেকদিন করা যাবে। আজকে চলে যাই গণিতের একটি মজার ব্যাপারে! এর নাম Permutation বা বিন্যাস!  আমরা সবাই কমবেশি গণিতের “বিন্যাস” (permutation) টপিকটি সম্পর্কে জানি। আজকে সেই বিন্যাসের একটি মজার বৈশিষ্ট্য নিয়ে...

সাইকেল খুজে বের করা – ফ্লয়েডের খরগোস এবং কচ্ছপ এলগরিদম

আমরা বাস্তব জীবনে অনেক সময়ই এমন ফাংশন দেখি, যেগুলোতে কিছুদূর পর পর একই মান পুনরাবৃত্তি হতে থাকে। কথা না বাড়িয়ে একটি উদাহারণ দিয়ে ফেলি। ধরা যাক, আমাদের কাছে একটি ফাংশন আছে এমনঃ f(x) = (f(x-1) * 2) % 10, for n > 0। এখানে % হল মডুলাস অপারেশন। আর ফাংশনের বেস কেস হল...

LightOJ 1137 – Expanding Rods – গভীরে গিয়ে আলোচনা

সবাইকে সালাম। আমাদের আজকের পর্বটা প্রোগ্রামিং এবং জ্যামিতি নিয়ে তৈরী করা হয়েছে,তবে যে কেউ চাইলে কিংবা আগ্রহ থাকলে এটা পড়তে পারো। LightOJ অনলাইন জাজের কথা মনে হয় অনেকেই শুনে এসেছো। না শুনে থাকলেও সমস্যা হবেনা। আজকের আলোচ্য সমস্যাটা হচ্ছেঃ ” তোমাকে একটা ধাতব রড...