Part 1: LightOJ Beginner Category | Community | Notre Dame Information Technology Club

“আমি C/C++ বেশকিছুদিন হল শিখেছি, অমুক অমুক ছোটখাটো algo ও পারি। কিন্তু Codeforces/Codechef এ প্রব্লেম solve করতে পারিনা, CF এ green/ash হয়ে বসে আছি।”

তোমার অবস্থা কি এইরকম? তাহলে আমার প্রথম কথা হবে, LightOJ এর Beginners Category এর 39 টা প্রবলেম solve করে ফেল। আমার মতে এই প্রবলেমগুলো তোমার বেসিক implementation skill আর fundamental tricks রপ্ত করতে সাহায্য করবে। (ওহ তুমি already সব করে ফেলেছ? তাহলে বসে আছ কেন? আরো 395 টা প্রবলেম আছে ওখানে, সব করে ফেল 😀 একটা একটা করে টপিক শিখতে থাক)

কিন্তু আমার focus (আপাতত) হবে ঐ 39 টা প্রবলেম এর Editorial দেয়া। যাতে এটা নতুনদের জন্য কাজে আসে।

/* পুরো সিরিজ জুড়ে আমি হয়ত অনেক topic এর নাম বলব আর সাথে হয়ত অন্য কোন tutorial এর link ও দিয়ে দিব, কারন সবকিছুই আমার এখানে আলোচনা করার প্রয়োজন নেই, অনেক কিছুর blog/tutorial আগেই অন্য কেউ বানিয়ে রেখে দিয়েছে। আর সেটা থেকেই যে দেখতে হবে এমন কোন কথা নেই, google করলে আরো অনেক source পাবে। */

1000 – Greetings from LightOJ

হ্যা হ্যা, আমি জানি, বলা লাগবে না, এইটা তোমার solve করা আছে -_- But সব প্রবলেম এর Editorial রাখার স্বার্থে এটাও আলোচনা করব।

প্রবলেম হল, দুইটা সংখ্যা দেয়া আছে, যোগফল নির্ণয় করতে হবে। প্রবলেমটা দেয়ার main কারন হতে পারে লোকজনকে Test case এর সাথে পরিচয় করানো। এইটায় যোগফল এর জায়গায় গুনফল আর সংখ্যাগুলোর limit $\leq 10^9$ দিয়ে একটা মজা করা যায়। তাহলো, অনেক নতুন প্রোগ্রামার তখন long long ব্যবহার না করে int ব্যবহার করার কারনে WA খায় 😛

1001 – Opposite Task

আরো একটা খুবই সহজ প্রবলেম। একটা সংখ্যা $n \leq 20$ দেয়া আছে। একে দুইটা সংখ্যার যোগফল আকারে লিখতে হবে যারা $\leq 10$ . খুবই সহজ technique হল $n/2$ আর $n - n/2$ print করা ( $n$ অবশ্যই double হবেনা, কারন আমরা এখানে integer division টাকে কাজে লাগাব)।

1006 – Hex-a-bonacci

আচ্ছা প্রবলেম এ দেয়া ঐ code কেন কাজ করে না? খেয়াল কর, যদি তুমি $f(10)$ call কর, তাহলে এটা তার আগের ছয়জনকে call করে। তাদের প্রত্যেকে আবার তাদের আগের ছয়জনকে call করে। এভাবে আসলে একটা value calculate করার জন্য, একই $f(x)$ অনেকবার call হয়। তাই, ঐ code submit করলে TLE খাবে।

Read about complexity tutorial here. (অনেক জরুরি, কারন সামনের সব প্রবলেমেই Complexity উল্লেখ করা হবে)

তো কি করা যায়? এই প্রবলেমটা solve করতে যে technique লাগে, তাহলো Dynamic Programming. চাইলে এটা পড়ে ফেলতে পার, DP basic আরকি। আমি একটু আলাদা way তে দেখাই, যাতে DP নিয়ে ঘ্যানঘ্যান না করে, খুব সহজে বোঝানো যায়।

ধর, $n$ তম Fibonacci বের করবে। তাহলে কিভাবে করা যায়? আমরা জানি, $f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)$ তাহলে এভাবে code লিখা যায়,

int f[10010]; // Since max n = 10000, I take a bit more than that
f[0] = 0; f[1] = 1;
for(int i = 2; i < 10010; i++)
f[i] = (f[i – 1] + f[i – 2]) % 10000007;
printf(“%d\n”, f[n]);

তাহলে শুরুতে $6$ variable দিয়ে initialize করে, $f(i) = f(i - 1) + ... + f(i - 6)$ use করলেই হল 🙂

Final Complexity হবে $O(TN)$

1008 – Fibsieve`s Fantabulous Birthday

এটা খুবই সুন্দর একটা প্রবলেম, তোমাকে এখানে pattern টা বুঝতে হবে।

খেয়াল কর, সকল বর্গ সংখ্যা সবসময় বোর্ড এর edge এ থাকে। এখন প্রত্যেক আলাদা আলাদা colored region কে এক একটা lair চিন্তা কর। অর্থাৎ, lair 1 = 1, lair 2 = [2, 4], lair 3 = [5, 9] …

এখন কোনো সংখ্যা $n$ দিলে খুব সহজেই $\sqrt n$ দেখে সহজেই তার lair নাম্বার বের করতে পারবে। ধর $n$ সংখ্যাটি $k$ তম lair এ আছে। তাহলে, $k$ টা lair এর আগে, $(k - 1)$ টা lair এ $(k - 1)^2$ টা সংখ্যা আছে। তাহলে $n$ হল, $k$ th lair এর, $n - (k - 1)^2$ তম সংখ্যা।

এবার দেখ, $k$ তম lair এ কয়টা সংখ্যা থাকে? খুব সহজ, $2k - 1$ . তাহলে মাঝখানের সংখ্যাটা (যেগুলা board এর কর্ন বরাবর আরকি) কত তম? $\lceil \frac{2k - 1}{2} \rceil$ তম। আর কোন $k$ যদি জোড় হয়, তাহলে প্রথম সংখ্যাটি board এর নিচে থাকে, আর বিজোড় হলে বামে। এইতো, অনেক তথ্য।

প্রবলেমটার বেশিরভাগই দেখলে, তেমন কিছুই লাগে না, উপরে সম্পূর্ণ solution বলি নি আসলে, বাকি যে কাজটা আছে, সেটুকু হল if-else আর যোগ-বিয়োগ এর খেলা। আসলে এইধরনের প্রবলেমে অনেক ধরনের solution idea পাওয়া সম্ভব। তুমি কিভাবে কর, সেটা তোমার উপর নির্ভর করে। তাই শুধুমাত্র core concept টাই বললাম।

1022 – Circle in Square

Problem টার mathematical solution পাওয়া খুব কঠিন নয়। Answer টা হল, $(2r)^2 - \pi r^2$ . একটা জিনিস বলা উচিত এখানে, অনেকে দেখা যায়, code এ, pi = 22/7 বা 3.14159 এইরকম কিছু use করে। কিন্তু তুমি এভাবে আসলে $\pi$ এর ধারে কাছের মান ও পাবা না। ফলে WA খাবা। কখনো কোন প্রবলেম এ $\pi$ ব্যবহার করতে হলে এটা ব্যবহার করবে,

double pi = acos(-1);// lets test what this is
printf(“%.10lf”, pi);
print করলে দেখবে, এটা $\pi$ এর খুব নিখুঁত মান (atleast lot better than before) দিচ্ছে। এবং যেসব প্রবলেম এ দশমিক সংখ্যা print করা লাগে, সেখানে যত সম্ভব নিখুঁত মান নিয়ে কাজ করতে হয়, কারন একটা ছোট ভুলই হয়ে যেতে পারে অনেক বড় বিপদ।

Part 1 এ পর্যন্তই। যেগুলো করা হয় নি সেগুলো তাহলে করে ফেলো 😀 পরের part এ আরো কয়েকটা প্রবলেম নিয়ে কথা বলব।