Rezwan's CP Blog

সহজ কথায় Palindromic Tree হল একটা Data Structure যেইটা কোন String এর সব Palindrome এ Fast access করার সুযোগ করে দেয়। [Read More]

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

History: IOI 2016 এর Day 2 এ একটা প্রবলেম ছিল, Aliens নাম এ। সেই প্রবলেম টাতে একটা বিশেষ 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]

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

আজকে 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]