Tower of Hanoy গনিতের জগতে অন্যতম সুন্দর একটি সমস্যা। উনবিংশ শতাব্দীতে ফ্রান্সের গনিতবিদ এডওয়ার্ড লুকাস এই সমস্যা বা ধাঁধাটির উৎপত্তি ঘটান। এই সমস্যায় তোমাকে তিনটা পিলার দেয়া হবে এবং একটি পিলারে কিছু ডিস্ক সাজানো থাকবে বড় থেকে ছোট অনুসারে। তোমাকে ওই একটি পিলারের সব ডিস্ক সরিয়ে অন্য ডিস্কে নিতে হবে। তবে শর্ত হলো তুমি শুধু উপরের ডিস্কটা সরাতে পারবে এবং ছোট ডিস্কের উপর বড় ডিস্ক রাখতে পারবেনা। মজার ব্যাপার হলো, লুকাস বলেছিলেন, 84 টা ডিস্ক নিয়ে খেলাটা খেললে খেলা শেষ হতে হতে পৃথিবী ধ্বংস হয়ে যাবে। এটা কেন বলেছিলেন সেটা আমরা একটু পরেই জানতে পারবো। এই সমস্যার সমাধান পদ্ধতি ব্যাবহার করে আরো অনেক মজার মজার সমস্যা সমাধান করা যায়। তাই দেরি না করে চলো দেখে ফেলি।
.........[Read More]
এই আর্টিকেলটি স্ক্রট ট্রি এর কামকাজ নিয়ে রচিত। এখানে স্ক্রট ট্রি কী, কেনো, কিভাবে, কোথায়, আসলেই কী ইত্যাদি প্রশ্নের উত্তর দেওয়ার চেষ্টা করেছি।
.........[Read More]
এই আর্টিকেলটি মৌলিক সংখ্যা যাচাই করার ওরফে প্রাইমালিটি টেস্ট করার বিভিন্ন কৌশল নিয়ে রচিত। এখানে আমি বর্গমূল পর্যন্ত সব সংখ্যা দিয়ে ভাগ করা, ফার্মার উপপাদ্য ব্যবহার করে প্রাইমালিটি টেস্ট ও মিলার-র্যাবিন প্রাইমালিটি টেস্ট নিয়ে আলোচনা করবো।
.........[Read More]
অনেকেই সেগমেন্ট ট্রি ব্য়বহার করে কিভাবে একটা সমস্য়া সহজে offline এ সমাধান করা যায় জানে না । offline বলতে বোঝানো হচ্ছে আমরা সবগুলো Query আগেই ইনপুট নিয়ে নিব । তারপর সবগুলো Query সমাধান করে একবারে আউটপুট দিব । এখানে Query গুলো ইনপুট নেওয়ার সাথে সাথে সমাধান না করে Query জমা রেখে দিয়ে পরে সমাধান করছি তাই এটাকে Offline Solution বলা হয় ।
.........[Read More]
Josephus Problem হলো গনিতের জগতে একটি সুপরিচিত সমস্যা। এই সমস্য়াটি নিয়ে একটি গল্পও প্রচলিত আছে। গল্পের নায়ক জোসেফাস এক দারুন গানিতিক সমস্য়ার সমাধানের মাধ্য়মে প্রানে বেঁচে গিয়েছিলেন। তবে সবথেকে সুন্দর বিষয়টি হচ্ছে প্রব্লেমটি নিজেই। এই জোসেফাস প্রব্লেমের সলিউশনটা অনেকে দারুন এবং এটির আইডিয়া ব্যাবহার করে আমরা অনেক ধরনের সমস্যা সমাধান করতে পারি। তাই দেরি না করে শুরু করা যাক।
.........[Read More]
Posted by Ahnaf Shahriar Asif on February 29, 2020
Data Structure ,
Graph ,
tree ,
set
আগের পোস্টে আমি DSU এর Rank Compression এবং সেটির Complexity নিয়ে কথা বলেছি। আজকে দেখবো Path Compression কি এবং এটির Complexity কেমন। আমরা আগের মতো এটিরও Complexity বের করবো, তবে গানিতিকভাবে না। অনেকটা কমন সেন্স ব্যাবহার করে জিনিসটার Complexity অনুভব করার চেষ্টা করবো। আশা করি এটি পড়ার পর তোমরা জিনিসটা অন্তত একটু ফিল করতে পারবে। তাই আর দেরি না করে শুরু করা যাক।
.........[Read More]
Posted by Ahnaf Shahriar Asif on February 25, 2020
Data Structure ,
Graph ,
tree ,
set
Disjoint Set Union(DSU) সম্পর্কে আমরা মোটামুটি সবাই কমবেশি জানি। ডাটা স্ট্রাকচার-অ্যালগরিদম জগতের সবথেকে মজার এবং রহস্যময় জিনিসগুলোর মধ্যে একটি। এটির কাজকর্ম দেখলে মনে হয় যাদুর খেলা দেখছি। আমার নিজের সবথেকে প্রিয় ডাটা-স্ট্রাকচার হলো DSU. আজকে আমি DSU এর Rank Compression আর এটির Complesity নিয়ে আলোচনা করবো। এটি কেন একটি জাদুকরী ডাটা স্ট্রাকচার সেটিও আমরা খুব তাড়াতাড়িই জানতে পারবো। তাই দেরি না করে শুরু করা যাক।
.........[Read More]
Posted by Ahnaf Shahriar Asif on September 26, 2019
contest analysis ,
data structure ,
graph ,
math
কোডফোর্সেসে আমরা নিয়মিত প্রোগ্রামিং কন্টেস্ট নিয়ে থাকি। এরকমই একটা কন্টেস্টের এডিটোরিয়াল এটি। codeforces এর BDOI Practice Group থেকে কন্টেস্টি দেখে নাও। কন্টেস্টের টাইটলে "BDOI Practice Contest-2"। কন্টেস্টটি দেখে নাও। তারপর এডিটোরিয়াল দেখা শুরু করা যাক।
.........[Read More]
কোডফোর্সেসে আমরা নিয়মিত প্রোগ্রামিং কন্টেস্ট নিয়ে থাকি। এরকমই একটা কন্টেস্টের এডিটোরিয়াল এটি। codeforces এর BDOI Practice Group থেকে কন্টেস্টি দেখে নাও। কন্টেস্টের টাইটলে "BDOI Practice Contest-1"। কন্টেস্টটি দেখে নাও। তারপর এডিটোরিয়াল দেখা শুরু করা যাক।
.........[Read More]