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

Persistent Segment Tree (Part - 02)

পূর্বের পর্বে Persistent Segment Tree এর Basic Idea নিয়ে বলেছিলাম। আজকে এর কিছু Basic Problem নিয়ে অলোচনা করব। Problem 1 You are given an array with $N$ elements. You need to do $Q$ queries in form - l r k: Count how many numbers from index $l$ to $r$ in the array is less than $k$. [Read More]
Category: Data Structure