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 Continue reading

Advertisements
Posted in Contest, Data structure | Tagged | 4 Comments

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 করে নিতে হয়। Continue reading

Posted in Contest, Top coder | Tagged | 6 Comments

KMP (Knuth-Morris-Pratt algorithm)


KMP কি?

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

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

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

Posted in algorithm | Tagged , | 3 Comments

Suffix Array


Suffix Array কি? 

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

Posted in Data structure, Programming | Tagged | 10 Comments

Python: ইন্সটলেশন


Python setup:

যারা Linux অথবা Mac ব্যবহার করেন, তাদের নতুন করে পাইথন ইন্সটল করার প্রয়োজন নেই। কারনে এই দুইটা অপারেটিং সিস্টেমে built-in পাইথন সেটআপ করা থাকে।
Windows এর জন্য পাইথন ডাউনলোড করা যাবে এইখান থেকে।
পাইথন ডাউনলোড করার পর, সাধারন software এর মত ডাবল ক্লিক করে, next next দিয়ে ইন্সটল করে নিতে হবে। Continue reading

Posted in Python | Tagged | Leave a comment

Python: শুরুর আগের কিছু কথা।


Python কি ??

Python বর্তমানে বহুল ব্যবহৃত একটি High level পোগ্রামিং ল্যাংগুয়েজ. Python মূলত একটি Interpreted প্রোগ্রামিং ল্যাংগুয়েজ। C/C++, Java সাথে Python এর মূল পার্থক হল এখানেই। C/C++, Java হল Compiled ল্যাংগুয়েজ, Python হল Interpreted ল্যাংগুয়েজ. Compiled ল্যাংগুয়েজ গুলো পুরো প্রোগ্রামকে একবারে machine code এ compile করে executable file এ সেভ করে। কিন্তু Interpreted প্রোগ্রামিং ল্যাংগুয়েজ গুলো রান টাইমে লাইন বাই লাইন machine code এ কনর্ভাট করে প্রোগ্রাম রান করে। তাই python অন্যান্য প্রোগ্রামিং ল্যাংগুয়েজের তুলনায় একটু ধীরগতির। তবে চিন্তার কোন কারন নাই, বর্তমানে আমাদের কম্পিউটার গুলো অনেক গতিসম্পন্ন। তাই Python এর এই ধীরগতি আমলে না নিলেও চলবে। 😛 😛 Continue reading

Posted in Python | Leave a comment

Python: Build .py file to .exe


নরমালি যেসব পিসিতে পাইথন সেট-আপ করা আছে, সেখানে সরাসরি .py ফাইল রান করানো যায়। কিন্তু যেসব পিসিতে পাইথন সেট-আপ করা নাই সেখানে .py ফাইলকে নরমাল টেক্স ফাইলের মত করে দেখায়।
এখন কোন প্রোগ্রামার পাইথনে একটা প্রোগ্রাম লিখে  সবাইকে দেয়ার সময় এইটা বলবেনা যে এই আমার .py ফাইল এইবার এইটা রান করার জন্য আপনার পিসিতে পাইথন সেট-আপ দিয়ে নেন। 😛 😛
তাহলে এইটার সহজ সমাধান হল প্রোগ্রামকে কম্পাইল করে এমন একটা ফাইল সিস্টেমে নেয়া যেটা পাইথন না থাকলেও চলবে। সেই রকম একটা সিস্টেম হল .exe ফাইল। মানে executable ফাইল বানানো। Continue reading

Posted in Python | Tagged | 3 Comments

Python: Graph Theory Algorithm


পাইথনের ডাটা-স্ট্রাকচার ব্যবহার করে কিভাবে গ্রাফ থিওরির এ্যালগরিদম ইমপ্লিমেন্ট করতে হয়, তা দেখানো হয়েছে। এখান থেকে গ্রাফ থিওরি সর্ম্পকে তেমন কিছু জানা যাবে না কিন্তু গ্রাফ থিওরি জানা থাকলে এই কোড গুলা থেকে কিভাবে ইমপ্লিমেন্ট করতে হয় তা ধারনা পাওয়া যাবে। Continue reading

Posted in Python | Tagged , , | Leave a comment

Python: Sorting Algorithm


আশা করি এই কোড দেখে পাইথনের ডাটাস্ট্রাকচার সর্ম্পকে কিছু ধারনা নেয়া যাবে।

পাইথনের কোড বুঝার আগে মনে রাখার মত কিছু জিনিসঃ  Continue reading

Posted in Python | 1 Comment