C++ STL & Tricks-1

C++ এ কিছু build in লাইব্রেরী আছে, যাদেরকে বলা হয় standard template library. এইসব STL ব্যবহার করে অনেক প্রবলেম অনেক সহজে করে ফেলা যায়। যেমন কোন প্রবলেমে যদি stack,queue এইগুলা ব্যবহার করা লাগে, এইগুলার জন্য নতুন করে কোড লেখার প্রয়োজন পরে না। stack,queue stl ব্যবহার করেই প্রবলেম সল্ভ করা যায়।

vector:

ভেক্টর নরমাল এ্যারের মতই। এর সুবিধা হল যখন ইচ্ছে সাইজ পরিবর্তন করা যায়।

vector declare:

vector ব্যবহার করার জন্য header file vector include করতে হবে।
vector < type > Name;

TopCoder offline practice.

অনেকেই প্রথমে topcoder এ অফলাইনে প্র্যাকটিস করতে গিয়ে যে সমস্যার মুখোমুখি হয় তাহল, “কোডত সাবমিট দিলাম, এখন verdict দেখব কিভাবে!!!“। তাই নতুনদের বুঝার সুবিধার্তেই এই ২ মিনিট ৪৮ সেকেন্ড এর ভিডিও।

Code Book

Programming contest লাইফে এখন পর্যন্ত যত Data structure এবং Algorithm শিখেছি তার সকল কালেকশন এই PDF এ পাওয়া যাবে।

 

 

                   ~ Happy coding ~

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 এর সব পজিশনে কতটুক প্রিফিক্স ম্যাচ করে তা থাকে।

Suffix Array

Suffix Array কি? 

suffix array হল এমন একটা array যেখানে কোন স্ট্রিং এর সবগুলা suffix string এর index Sorted আকারে থাকবে। আরও সোজা করে বললে, একটা স্ট্রিং এর সাইজ যদি N হয় তাহলে তার N টা suffix string পসিবল। এখন suffix string গুলাকে যদি lexicographical ভাবে সর্ট করি তাহলে suffix starting এর যে index গুলা array আকারে পাব তাকেই suffix array বলা হচ্ছে। যেমন একটাস্ট্রিংঃ mississippi এর সবগুলা suffix string হলঃ