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 হলঃ

  

Python: ইন্সটলেশন

Python setup:

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

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 এর এই ধীরগতি আমলে না নিলেও চলবে। :P :P