Divide and Conquer for solving Insert-Query Problems Offline

আজকে একটা Divide and Conquer Trick নিয়ে কথা বলব। কোন Data Structure এ Insert-Query ধরনের Problem এর জন্য এই Trick কাজে লাগবে। এই Trick ব্যবহার করা যাবে যখন আমরা Data Structure টা সহজেই Statically Build করতে পারি (সব Insert সব Query এর আগে থাকে), কিন্তু Alternatively Insert আর Query করতে পারি না। [Read More]

Dynamic Programming Optimization - IOI'16 Aliens Trick

History: IOI 2016 এর Day 2 এ একটা Problem ছিল, Aliens নাম এ। সেই Problem টাতে একটা বিশেষ DP Optimization এর প্রয়োজন হয়েছিল 100 points এর Solution এর জন্য। যদিও 60 points তুলতেই অনেক Observation লাগে। অবশ্য এই Trick এর পূর্বেও Chinese দের মধ্যে প্রচলিত ছিল, WQS-Binary-Search নামে। WQS আসছে Qingshi Wang থেকে, যে Trick টা Chinese Contestants এর মধ্যে Popularize করেছেন। তবে Formally এই Trick টা Lagrange Multiplier নাম... [Read More]

Dynamic Programming Optimization - Convex Hull Trick

Convex Hull Trick (DP Optimization), সংক্ষেপে CHT নামটা হয়ত অনেকেই শুনে থাকবেন। সবার মনেই প্রথম প্রশ্ন জাগে “আমি তো Convex Hull ই পারি না, তাহলে CHT শিখব কি করে :thinking:”। আসলে Geometry এর Convex Hull আর Dynamic Programming এর Convex Hull Trick আসলে ২টা একেবারেই ভিন্ন জিনিস। [Read More]

Fast Fourier Transform

আজকে Fast Fourier Transform নিয়ে লিখব। Fast Fourier Transform মূলত Polynomial Multiplication এর জন্য ব্যবহার করা হয়। এই Tutorial এর মূল উদ্দেশ্য আসলে সেটাই। শুরুতে কিছু Formal Defination দেখা যাক - Discrete Fourier Transform DFT কে এইভাবে Define করা যায় - DFT একটা Function, যেটা $\mathbb{C}^n$ থেকে $\mathbb{C}^n$ এ সংজ্ঞায়িত। এইটা $[a_0, a_1, a_2, \cdots, a_{n-1}]$ কে $[A_0, A_1, A_2, \cdots, A_n]$ এ রূপান্তর করে যেখানে - [Read More]
Category: Discrete Math