Square Root Decomposition

problem: একটি N size এর Array তে কিছু নাম্বার দেয়া হল। এখন প্রতিবার x থেকে y রেঞ্জ এর মধ্যে কুয়েরি করে বের করতে হবে minimum নাম্বার কত।
এখন একদম brute force উপায়ে যদি বের করি তাহলে complexity হবে প্রতি query তে x to y iterate করতে হবে. Array size যদি N হয় এবং query যদি N টা হয়। তাহলে worst case complexity হচ্ছে O(N²)। যা খুবই costly.

Square root decomposition:

এখন total Array কে square root size block এ ভাগ করতে হবে।
Array size যদি N হয় তাহলে পুরো Array কে √N size block এ ভাগ করে নিব। এবং প্রতি Block এ √N টা element এর result থাকবে। square root যদি perfect না হয়, তাহলে একদম শেষ Block এ square root থেকে কম element এর রেজাল্ট থাকবে।

এখন যদি 100 size এর একটা Array কে square root decompose করা হয় তাহলে, total block size হবে √100=10 এবং প্রতি Block এ থাকবে 10 টা element এর result.

Top Coder Arena Setup

TC Contest:

টপকোডারে কন্টেস্ট সিস্টেম অন্যান্য online judge গুলা থেকে একটু ভিন্ন। এখানে কন্টেস্ট করতে হয় Top Coder Arena তে। Solution Code এ কোন Input/Output দিতে হয় না। Top Coder Arena problem এর একটা class generate করে দেয়। তাতে একটা method থাকে, তারমধ্যে solution code লিখতে হয়। method এর parameter, return type কি হবে তা problem description এ দেয়া থাকে।
তাই  Top Coder Arena setup দেয়ার পর কিছু configuration করে নিতে হয়।

Method এর parameter, return type বিভিন্ন রকমের STL হয়ে থাকে। তাই Top Coder এ কন্টেস্ট করার আগে একটু STL ও C++ ধারনা নিয়ে শুরু করা ভাল।

TC Arena Setup:

Top Coder Arena জন্য প্রথম ৩ টি জিনিস লাগবে।

1. JRE
2. Top Coder Arena
3.  KawigiEdit-pfa-2.4.0

প্রথমে JRE Download করে নরমাল software এর মত next, next দিয়ে install করে নিতে হবে।
তারপর pc তে একটা new folder open করতে হবে Topcoder নামে। (অন্য নাম দিলেও সমস্যা নাই)। New folder এ Top Coder Arena, Kawigiedit download করে রাখতে হবে।

KMP (Knuth-Morris-Pratt algorithm)

KMP কি?

kmp স্ট্রিং ম্যাচিং এ্যালগরিদম। Kmp লিনিয়ার টাইমে একটা স্ট্রিং T তে একটা প্যাটার্ন স্ট্রিং P কতবার আছে এবং কোন কোন পজিশনে আছে তা বের করে।

KMP কিভাবে কাজ করে?

Kmp কিভাবে কাজ করে তা বুঝার আগে একটা স্ট্রিং T থেকে প্যাটার্ন স্ট্রিং P কতবার ও কোথায় আছে তার naive solution টা দেখে নেয়া জরুরী।

Naive solution:

উপরে solution এ T এর প্রতি পজিশন থেকে P স্ট্রিং ম্যাচ করে দেখা হচ্ছে এবং কোথাও ম্যাচ না পেলে আবার P স্ট্রং এর প্রথম পজিশনে গিয়ে ম্যাচ করে দেখা হচ্ছে।
Kmp এ্যালগরিদম ম্যাচ না পেলে P স্ট্রিং এর বার বার প্রথম পজিশন এ গিয়ে ম্যাচ করানোর জিনিস টা স্কিপ করে।
Kmp এ্যালগরিদমে একটা ফাংশন থাকে যাকে prefix/π/failure ফাংশন বলা হয়ে থাকে।
এই ফাংশন একটা π এ্যারে তৈরী করে দেয়, যাতে প্যাটার্ন স্ট্রিং P এর সব পজিশনে কতটুক প্রিফিক্স ম্যাচ করে তা থাকে।