Dev Skill: Another Bigmod Problem

Problem link: Another Bigmod Problem

In this problem, we are given three integers A, B, C; we need to calculate A^B % C.

Solution: We can calculate it by using modular arithmetic. We know

• (a * b) % c = ( (a % c) * (b % c) ) %c 
• (a + b) % c = ( (a % c) + (b % c) ) %c 
• a^b = a * a^(b-1)

So with this we can write this following code to calculate A^B % C

This algorithm is called classical bigmod algorithm. But in this problem, we still have problem. Look at line 9 : x = ( x * x ) % c;

Here, since c can be as large as 10^18, the value of x can be (10^18 - 1 ). When we multiply x with x, it will overflow. For example, try with input a = 10^18 - 1, b = 2, c = 10^18.

So how do we calculate ( x * x ) % c, without overflowing? We use the same divide and conquer approach like above. But this time we will use addition instead of multiplication. It's called bigmultiplication, we will write the function as following:

So finally our full code would look like this:

কম্বিনেশন ( Combination )

কোন বড় গ্রুপ থেকে কিছু সংখ্যক জিনিস নিয়ে ছোট ছোট গ্রুপে ভাগ করাই হল কম্বিনেশন। এখানে পারমুটেশন এর মত অর্ডার এর কোন প্রভাব থাকেনা। যেমনঃ ৩ টি জিনিস থেকে আমরা ২ টি জিনিস নিতে পারি এভাবেঃ
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।

অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)

বাইনোমিয়াল কো-এফিশিয়েন্ট ( Binomial Coefficient )

বাইনোমিয়াল কোএফিশিয়েন্ট হল অর্ডার বিবেচনা না করে ভিন্ন ভিন্ন সম্ভাবনাকে নেয়া। শুনতে কঠিন লাগলেও ব্যাপারটি আসলে কিছুইনা। আমরা n জিনিস থেকে k জিনিস নিবো, অর্ডার বিবেচনা না করে। এটিকে কতভাবে নেয়া যাবে, এটিই বাইনোমিয়াল কোএফিশিয়েন্ট, অর্থাৎ কম্বিনেশন। 

আমরা কিছু সিরিজ এর এক্সপানশন দেখিঃ

(x + y)⁰ = 1
(x + y)¹ = x + y

(x + y)² = x² + 2xy + y²

(x + y)³ = x³ + 3x²y + 3xy² + y³

(x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

এসব সিরিজ কে আমরা এভাবে লিখতে পারি কমন ফর্মেঃ 

আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) ⁿ
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ

আমরা n = 4 নিয়ে দেখিঃ

(1 + x)⁴ = x⁴ + 4x³ + 6x² + 4x + 1
এখন কো-এফিশিয়েন্টগুলি হবেঃ 1  4  6  4  1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ

(x + y)ⁿ = (nC0)(xⁿy⁰) + (nC1)(x^n-11y¹) + (nC2)(x^n-22y²) + ... + (nCn)(x⁰yⁿ);  [nCk = combnation of k element from n or n choose k]

আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ

১। ফ্যাক্টরিয়াল ( Factorial )

আমরা সরাসরি nCk ফর্মুলা ব্যবহার করে nCk বের করতে পারি।
ফর্মুলাঃ nCk  =  [ n! ] / [  k! * (n-k)! ]

কিন্তু এভাবে আমরা সর্বোচ্চ ২১-২২ ফ্যাক্টরিয়াল পর্যন্ত হিসাবে করতে পারবো। এর চেয়ে বেশি আমরা সি++ এ করতে গেলে আমাদের বিগ-ইন্টিজার লাইব্রেরি ব্যবহার করতে হবে। তবে পাইথন এ আমরা হিসাব করতে পারবো এবং এই হিসাবের কমপ্লেক্সিটি হল O(n).
আমরা বড় বড় কম্বিনেশন এর জন্য, nCk mod m এরকম কিছু একটা করে রেজাল্ট একটি নির্দিষ্ট লিমিটের মাঝে রাখতে পারি।

২। রিকার্সন ( Recursion )

nCk বের করার রিকার্সন ফর্মুলা হলঃ nCk (i,k) = nCk (i-1,k-1) + nCk (i-1,k);

আমাদের টাইম এবং স্পেস কমপ্লেক্সিটি হবেঃ O(n*k) for nCk

আমরা একে একটু মডিফাই করে স্পেস কমপ্লেক্সিটি কমিয়ে আনতে পারি। আমরা আগের সারি চেক করবো, কারন আমাদের ঐ সারিগুলো আসলে দরকার হবেনা পরে আর।

৩। কম্বিনেশন এর বিস্তার ( Expansion of Combination )

আমরা জানি, nCk  =  [ n! ] / [  k! * (n-k)! ], অর্থাৎ

               [ n(n-1)(n-2) ... (n-k+1) ] [ (n-k) ... (1) ]

-------------------------------------------------------------------------

                  [ (n-k) ... (1) ] [ k(k-1)(k-2) .... (1) ]

আমরা লব এবং হর থেকে [ (n-k) ... (1) ] টার্ম কেটে ফেলতে পারি, তাহলে আমাদের ফাইনাল টার্ম হবেঃ

 n       (n-1)      (n-2)      (n-k+1)

---  *  ------  *  ------  *  ----------

 k       (k-1)      (k-2)          (1)

আমরা একে এভাবে লিখতে পারিঃ

nCk (n,k) = 1                                             ; if k == 0

                     else  (n/k) * nCk (n-1, k-1)

৪। প্রাইম এর পাওয়ার ( Power of Prime )

আমরা ফ্যাক্টরিয়াল এর কোন প্রাইম এর পাওয়ার বের করতে পারি এভাবেঃ

P_prime = floor[ n/prime ] + floor[ n/prime² ] + .....

এখানে n = factorial, prime = the prime whose power in n-factorial we are calculating
আমরা nCk এর মাঝে p প্রাইম এর পাওয়ার বের করবো এভাবেঃ
power = fact(n, p) - fact(r, p) - fact(n-r, p)
এরপরে আমরা p^power করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।

৫। চাইনিজ রিমেইন্ডার থিওরেম  ( Chinese Remainder Theorem )

যদি আমাদের এরকম বের করতে বলা হয়ঃ nCk mod m where m is not prime , সেক্ষেত্রে আমরা m কে প্রাইম এ ফ্যাক্টরাইজ করার পরে CRT(Chinese Remainder Theorem) ব্যবহার করে মান বের করবো।

বাইনারি ইন্ডেক্সড ট্রি অথবা ফেনউইক ট্রি ( Binary Indexed Tree or Fenwick Tree )

কোন অ্যারের সংখ্যাগুলোর যোগফল বের করতে, কোন ইনডেক্স আপডেট করতে আমরা বাইনারি ইন্ডেক্সড ট্রি ব্যবহার করি। এসব কাজ আমরা সেগমেন্ট ট্রি দিয়েও করতে পারি, কিন্তু Binary Indexed Tree (BIT) দিয়ে কোড করা অনেক সহজ এবং খুব দ্রুত কোড করে ফেলা যায়। আসলে এই BIT ঠিক কি কাজে লাগে? 

• কোন অ্যারের 0 থেকে N পর্যন্ত যোগফল, মিনিমাম, ম্যাক্সিমাম ইত্যাদি বের করা
• কোন ইন্ডেক্স আপডেট করা

লক্ষ্য রাখতে হবে যে, BIT দিয়ে আমরা 0 থেকে যেকোন রেঞ্জ এর কিছু অপারেশন ক্যাল্কুলেট করবো। এখানে আমরা 1 বেস ইনডেক্স নিয়ে আলোচনা করবো।
আমরা নরমালি যোগফল লুপ চালায়ে বের করতেই পারি, কিন্তু BIT আমাদের এই কাজকে O(logN) এ করে দেয়।

BIT শুরু করার আগে একটু bit নিয়ে কাজ করা যাক। 

আমরা যেকোন একটি নম্বর এর সর্বশেষ সেট(1) বিটকে সরানোর চেষ্টা করি, কেন করছি, তা পরে বলি।
ধরি, একটি নম্বর = 14. একে বাইনারি তে নিলে হবে = 1110 (যেহেতু বিট এর হিসাব সব বাইনারিতে হয়, আমরা বাইনারি নিয়ে বেশি মাথা ঘামাবো)

এখন এই 1110 এর সর্বশেষ সেট বিট হচ্ছে 1 নং পজিশন এ।

এখন আমাদের কাজ হল এই 1 পজিশন এর বিট 1 কে সরানো। আমরা এটি করতে পারি এভাবেঃ x & (-x)

এখানে x = 14; অর্থাৎ আমরা একটি অ্যান্ড অপারেশন এর মাধ্যমে এটি করতে পারি।

x = 14 = 1110

x = -14 = 0010

x & (-x) = 1110 & 0010 = 10 (আমরা এভাবে সর্বশেষ সেট বিট কে আলাদা করে ফেললাম)

এখন কথা হচ্ছে, কেন আমরা এভাবে আলাদা করে ফেললাম? একটু পরেই আমরা বুঝতে পারবো। এখন আমরা সরাসরি BIT এর মাঝে চলে যাবো।

বাইনারি ইন্ডেক্সড ট্রি ( Binary Indexed Tree )

আমরা জানি, যেকোন সংখ্যা কে ২ এর পাওয়ারের যোগফল আকারে লিখা যায়। আমরা ধরে নেই আমাদের একটি অ্যারে আছে যার নাম BIT অ্যারে। এখানে আমরা যেকোন ইনডেক্স এ অ্যারের কিছু সংখ্যার যোগফল রাখবো। অর্থাৎ এটি আমাদের একটি পারশিয়াল সাম ট্রি হিসাবে কাজ করবে।

ধরি আমাদের একটি অ্যারে আছে A[ ]. এবং আমাদের partial sum সেভ করে রাখার জন্য আছে BIT[ ] অ্যারে। ধরি আমাদের A[ ] অ্যারের ইনডেক্স ১ বেসড। এখনঃ
A [ ] = { 1, 2, 3, 4, 5, 6 }

এবং আমাদের BIT অ্যারে হবে এরকমঃ

BIT [ 1 ] = A [ 1 ] = 1

BIT [ 2 ] = A [ 1 ] + A [ 2 ] = 1 + 2 = 3

BIT [ 3 ] = A [ 3 ] = 3

BIT [ 4 ] = A [ 1 ] + A [ 2 ] + A [ 3 ] + A [ 4 ] = 10

BIT [ 5 ] = A  [5 ] = 5

BIT [ 6 ] = A [ 5 ] + A [ 6 ] = 11

এটি একটি বাইনারি ইন্ডেক্সড ট্রি এবং BIT [ index ] এর মাঝে আমাদের A অ্যারের partial sum সেভ করা আছে।

অর্থাৎ,

BIT [ n ] =   A [ n ] ; if n is odd

                     A [ 1 ] + A [ 2 ] + ... + A [ n ]; if n is power of 2

আমরা প্রতিবার আমাদের BIT অ্যারেকে আপডেট করার মাধ্যমে ভ্যলুগুলি জেনারেট করবো। প্রতিবার আমরা A অ্যারের প্রতি ইনডেক্স এর জন্য আমাদের update(int index,int value) call করবো।
এখন প্রশ্ন আসতে পারে, যদি n এর মান বিজোড় কিংবা 2 এর পাওয়ার না হয়, তাহলে আমরা কি করবো? আমরা জানি যেকোন নম্বরকে 2 এর পাওয়ার হিসেবে লিখা যায়। আমাদের আপডেট ফাংশন 2 এর পাওয়ার না পেলে, তার ঠিক পরের 2 এর পাওয়ার পর্যন্ত ভ্যালুকে আপডেট করতে থাকবে। হাতে কলমে সিমুলেশন চালায়ে ব্যাপারটি দেখতে পারেন আপনারা।

ধরি আমরা update(5,2) call করলাম। এরমানে হচ্ছে, আমরা 5 ইনডেক্স কে 2 দিয়ে আপডেট করবো।
এখন, 5 = 101, BIT [ 5 ] += 2
আমাদের BIT [ 6 ] এও আপডেট করতে হবে, কাজেই আমরা যখন index & (-index) ব্যবহার করবো,
101 & 011 = 1; যা কিনা দশমিক এ 1। কাজেই আমরা 1 বারিয়ে দিব আমাদের কারেন্ট ইনডেক্স এর মান, এবং নতুন ইনডেক্স পাবো 6, কাজেই BIT [ 6 ] += 2 করে দিবো। এরপরে আমরা আবার একই কাজ করবো,
110 & 010 = 10; দশমিক এ ২, কাজেই নতুন ইনডেক্স = 6+2 = 8; কিন্তু 8 > 6, কারন আমরা A আ্যরের সাইজ নিয়েছি 6. এভাবে আমাদের আপডেট ফাংশন কাজ করে।

এখন কুয়েরি অপারেশন দেখা যাক।

এখানে 1 থেকে index পর্যন্ত সংখ্যার যোগফল রিটার্ন করবে এই কুয়েরি ফাংশন। যেখা যাক কিভাবে কাজ করে,
আমরা 1 to 4 যোগফল চাই, তাহলে query_sum( 4 ) call করবো।
sum = 0
sum += BIT [4] = 0 + 10 = 10
4 = 100
so, 100 & 100 = 100 = 4 (decimal)
so index = index - 4 = 4 - 4 = 0 ; finally return sum;

আপডেট এবং কুয়েরি ২ ক্ষেত্রেই আমরা প্রতিটি ইনডেক্স এর বিট নিয়ে কাজ করছি, কাজেই উভয়খেত্রে আমাদের কমপ্লেক্সিটি O(logN)

কোডঃ

এতক্ষন আমরা দেখলাম 1-D অ্যারের মাঝে যোগফল বের করা। আমাদের যদি 2-D অ্যারের মাঝে এরকম কোন কিছু করতে বলা হয়? তাহলে আমরা কিভাবে আপডেট এবং কুয়েরি চালাবো? ব্যাপারটি খুবি সোজা, যেভাবে আমরা 1-D এর জন্য করেছি, একই কাজ আমরা 2-D এর জন্যেও করবো ২ বার করে। বেশি কিছু না বলে কোড দেখা যাকঃ

এখানে i&(i+1)-1 এবং i|(i+1) দেখে ভয় পাবার কিছু নেই। আমরা এতক্ষন যা করেছি বিট দিয়ে, এখানেও তাই করা হয়েছে। একটু নিজে ঘাটাঘাটি করে দেখার অনুরোধ রইল।

প্র্যাকটিস প্রব্লেম ( Practice Problems )

• Uva: Potentiometers
• LightOJ: Curious Robin Hood
• LightOJ: Points in Rectangle
• Spoj: MATSUM
• Spoj: SUMSUM
• Spoj: INVCNT
• Hacker Earth: Counting in Byteland
• Hacker Earth: Akash and GCD1
• Codeforces: Little Artem and Time Machine
• Codeforces: Hanoi Factory
• Codeforces: Goodbye Souvenir
• Codeforces: Subsequences

লংগেস্ট কমন সাব-সিকুয়েন্স (Longest Common Subsequence)

২ টি স্ট্রিং দেয়া থাকবে। এদের মাঝে ম্যাক্সিমাম কত দৈর্ঘ্যের সাব-সিকুয়েন্স আছে, এবং সিকুয়েন্সটি কি, এটা আমাদের বের করতে হবে।
সাব-সিকুয়েন্স হল এমন একটি সিকুয়েন্স, যা কিনা ২ টি স্ট্রিং এর মাঝে কমন ক্যারেক্টার নিয়ে তৈরী এবং, একটি ক্যারেক্টার এর ইনডেক্স এর চেয়ে পরের ক্যারেক্টার এর ইনডেক্স (একটি নির্দিষ্ট স্ট্রিং) অবশ্যই বড় হবে।
যেমনঃ
String X = "AAABCD"
String Y = "ABCDDA"
তাহলে, এদের মাঝে LCS হবেঃ "ABCD"
ধরি Z = "ABCD"
এখানে দেখা যাচ্ছে যে, A,B,C,D এর প্রত্যেকটি ক্যারেক্টার এর ইনডেক্স তার আগের ক্যারেক্টার থেকে বড় (X এবং Y উভয় স্ট্রিং এ)। আমরা মেইনলি ক্যারেক্টার এর অর্ডার মেইনটেইন করবো।

এপ্রোচঃ প্রথমে আমরা X এর i-তম prefix (ক্যারেক্টার, যা অন্য ক্যারেক্টার এর আগে বসাই) কে Xi দিয়ে প্রকাশ করি। তাহলে,
X1 = "A"
X3 = "AAA" etc..
এখন আমরা খেয়াল করি,

• যদি, Xi == Yj হয়, (অর্থাৎ ২ টি স্ট্রিং এর ক্যারেক্টার মিলে গেছে), তাহলে, Zs = Xi = Yj হবে, এবং Zs-1, Xi-1 এবং Yj-1 এর একটি LCS হবে
• যদি, Xi != Yj হয়, তাহলে Zs != Xi বলতে আমরা বুঝাবো, ্Z , Xi-1 এবং Yj এর একটি LCS
• যদি, Xi != Yj হয়, তাহলে Zs != Yj বলতে আমরা বুঝাবো, ্Z , Xi এবং Yj-1 এর একটি LCS

তাহলে, যখন ক্যারেক্টার সমান হবে না, তখন আমরা ২ স্ট্রিং এর মাঝে ক্যালকুলেট করে ম্যাক্সিমাম মানকে নিবো।তাহলে আমাদের অ্যালগরিদম অনেকটা এরকমঃ

c[ i,j ] = 0; if i == 0 OR j == 0
              c[ i-1,j-1 ] + 1; if i,j > 0 AND Xi == Yj
              max ( c[ i,j-1 ], c[ i-1,j ] ); if i,j > 0 AND Xi != Yj

LCS ক্যালকুলেশন

ধরি, X = "ABCBDAB", Y = "BDCABA"
এখন আমরা একটি 8x7 সাইজ এর ২-ডি অ্যারে নিবো। 8 = X.size()+1, 7 = Y.size()+1

আমাদের অ্যারের [0,0] ইনডেক্স 0 ইনিশিয়ালাইজ করবো। এরপরে আমরা প্রতি সারি-কলামে ২ টি স্ট্রিং থেকে ভ্যালু মিলানোর চেষ্টা করবো। এবং আমাদের অ্যালগরিদম অনুযায়ী মান বসাবো। এখন খেয়াল করে দেখবো যে, ইনডেক্স ১ এর A(String X) এর সাথে ইনডেক্স ১ এর B (String Y) মিলেনি, কাজেই আমরা [1,1] ইনডেক্স এ 0 বসিয়ে দিলাম। এই 0 এসেছে, [1,0] এবং [0,1] ইনডেক্স এর ভ্যালুর মাঝের ম্যাক্সিমাম ভ্যালু। অর্থাৎ max ([1,0] এবং [0,1]) = 0।

এর মানে হল, X1 এবং Y1 এর মাঝে LCS এর দৈর্ঘ্য = 0. এভাবে আমরা টেবিল ফিল আপ করতে থাকি।

এখানে, 1(A) এর সাথে 4(A) মিলে গেছে, তাই আমরা [0,3] ঘরের ভ্যালু + ১ বসাবো। এভাবে আমরা বাকি ভ্যালুর জন্য ঘর ফিল আপ করলে এরকম একটি ফাইনাল টেবিল পাবো।

কাজেই, আমাদের LCS স্ট্রিং এর দৈর্ঘ্য হচ্ছে 4.
কোডঃ

এখন আমাদের কাজ হবে, এই যে LCS স্ট্রিং টির দৈর্ঘ্য পেলাম, একে প্রিন্ট করা। এর জন্য আমাদের পাথ বের করতে হবে। আমরা আমাদের ফাইনাল রেজাল্ট থেকে উপরে এবং বামে মুভ করতে থাকবো, যখন আমরা দেখবো যে Xi == Yj, তখন আমরা সেই ঘরের ভ্যালু প্রিন্ট করে দিবো। আমরা যদি পাথ ফাইন্ডিং এর জন্য টেবিল জেনারেট করি, দেখতে এরকম হবে ফাইনালিঃ

এই হচ্ছে আমাদের ফাইনাল পাথ টেবিল। আমরা নিচ থেকে উপরে সিকুয়েন্স অনুযায়ী উঠতে থাকবো। আমরা LCS বের করার সময়, যখন অ্যারেতে ভ্যালু আপডেট করতাম, ঐ সময়, আমরা আমাদের পাথ টেবিল ও আপডেট করে দিবো। Xi == Yj হলে আমরা টেবিলে স্টোর করবো m, তানাহলে, আমাদের চেক করতে হবে যে c[i-1,j] কি c[i,j-1] থেকে বড় অথবা সমান কিনা। এক্সদি বড় অথবা সমান হয়, তাহলে আমরা স্টোর করবো u (up), তানাহলে, আমরা l(left) স্টোর করবো। তাহলে আমাদের LCS স্ট্রিং: "BCBA" এরপরে আমরা নিচের কোড অনুযায়ী পাথ ক্যালকুলেট করবোঃ

এখানে char x[] হল X স্ট্রিং, আমরা এখানে ইচ্ছা করলে Y ও পাঠাতে পারতাম। যেহেতু, ২ স্ট্রিং এর মাঝের কমন স্ট্রিং বের করতে চাচ্ছি, কাজেই, আমাদের ২ টি স্ট্রিং চেক না করে একটির ইনডেক্স চেক করলেই কাজ হয়ে যাচ্ছে

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Uva: 10192 - Vacation
• Uva: 10405 - Longest Common Subsequence
• Uva: 10635 - Prince and Princess
• Hacker Earth: Longest Common Subsequence
• Hackerrank: LCS Returns
• Light Oj: An Easy LCS
• Spoj: Cross country
• Codechef: Chef and LCS

ম্যাট্রিক্স চেইন মালটিপ্লিকেশন (Matrix Chain Multiplication)

আমাদের কিছু ম্যাট্রিক্স দেয়া থাকবে।আমাদেরকে বের করতে হবে, এমন কোন অর্ডার এ ম্যাট্রিক্সগুলিকে গুন করলে তাদের cost মিনিমাম হবে।
ধরি আমাদের ২ টি ম্যাট্রিক্স দেয়া আছে A এবং B.
এখন A = [ P x Q ] ; এখানে P হল সারি (row), Q হল কলাম (column)
B = [ Q x R ]
এখন A*B করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, তার ডাইমেনশন হবে = P x R
এখন আমাদের সবসময় লক্ষ্য রাখতে হবে যে ২ টি ম্যাট্রিক্স এর গুনের জন্য অবশ্যই প্রথম ম্যাট্রিক্স এর কলাম এবং দ্বিতীয় ম্যাট্রিক্স এর সারি সমান হতে হবে। এবং এক্ষেত্রে তাদের মাঝে গুনের জন্য টোটাল মালটিপ্লিকেশন লাগবে ঃ P*Q*R; [ ১ম ম্যাট্রিক্স এর সারি * ১ম ম্যাট্রিক্স এর কলাম * ২য় ম্যাট্রিক্স এর কলাম ]।
অর্থাৎ, cost = P*Q*R.

এবং আমাদের কাজ হচ্ছে একাধিক ম্যাট্রিক্স এভাবে লিনিয়ারলি গুন করা যাতে তাদের cost মিনিমাম হয়।
এখানে মূল ব্যাপার হল, আমরা যেভাবেই মালটিপ্লাই করিনা কেন, ফাইনাল রেজাল্ট সবসময় একই আসবে। অর্থাৎ গুন করার ক্ষেত্রে অর্ডার কোন প্রভাব ফেলেনা। তবে একেক অর্ডার এর জন্য একেকরকম cost আসবে। আমাদের কাজ হবে এমন অর্ডার বের করা যাতে cost মিনিমাম হয়।

ধরি, A [10 x 100 ] , B [ 100 x 5 ] , C [ 5 x 50 ], এই তিনটি ম্যাট্রিক্স। এখন আমরা ২ ভাবে এদের গুন করতে পারি।

• ( A * B ) * C
• A * ( B * C )

এখন ( A * B ) * C এর ক্ষেত্রে, প্রথমে,
( A * B ) এর জন্য cost, c1 = 10 * 100 * 5 = 5000; [ cost = P*Q*R ]
এখন ( A * B ) করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, ধরি নতুন ম্যাট্রিক্সটি A' .
তাহলে A' এর ডাইমেনশন হবেঃ A' [ 10 x 5 ]; [ P x R ]
এখন, ( A' * C ) এর জন্য cost, c2 = 10 * 5 * 50 = 2500
সুতরাং, টোটাল cost, c = 5000 + 2500 = 7500

একইভাবে A * ( B * C ) এর জন্য টোটাল cost হবে 75000
কাজেই আমাদের জন্য প্রথম অর্ডার এ মালটিপ্লাই করলে cost মিনিমাম হবে।

অ্যালগরিদম (Algorithm)

আমরা আমাদের MCM (Matrix Chain Multiplication) বের করার জন্য যে ম্যাট্রিক্সগুলি দেয়া থাকবে, সেগুলি থেকে আমরা তাদের ডাইমেনশনকে একটু মডিফাই করে একটি অ্যারেতে সেভ রাখবো এমন ভাবে যাতে, প্রতিটির ইনডেক্স এ তাদের সারির (row) মানগুলি থাকবে। উদাহরন দিলে ব্যাপারটি পরিষ্কার হবে।
ধরি, আমাদের ৬ টি ম্যাট্রিক্স দেয়া আছে এভাবেঃ

A1 [ 30 x 35 ]

A2 [ 35 x 15 ]

A3 [ 15 x 5 ]

A4 [ 5 x 10 ]

A5 [ 10 x 20 ]

A6 [ 20 x 25 ]

এখন আমরা এদের সারি-কলামের মানগুলোকে একটি অ্যারে p তে এভাবে সাজায়ে রাখবোঃ

কাজেই আমরা যদি, A1 * A2 করতে চাই, তাহলে p অ্যারে থেকে আমরা p[0]*p[1]*p[2] করলেই মান পেয়ে যাবো।
তাহলে আমরা এখন একটি ফর্মুলা দাঁড়া করাতে পারি এভাবেঃ

m[i,j] = i হতে j পর্যন্ত ম্যাট্রিক্স গুন করতে মিনিমাম মালটিপ্লিকেশন।
তাহলে আমরা লিখতে পারিঃ

m[ i,j ] = { 0 if , i == j, else
                min { m[ i,k ] + m[ k+1,j ] + p[ k-1 ] * p[ k ] * p[ j ]  }; [k = 1 to j-1]

আমরা এই ফর্মুলা অনুযায়ী আমাদের MCM table জেনারেট করবো।

টেবিল জেনারেট (MCM table generate)

যেহেতু আমাদের ৬ টি ম্যাট্রিক্স, তাই আমরা 6 x 6 সাইজ এর একটি ২-ডি অ্যারে নিবো। এখন আমরা প্রতিবার, length 1 to 6 পর্যন্ত ম্যাট্রিক্স মালটিপ্লিকেশন এর অর্ডার বের করবো।
length = 1 হলে, m[i,j] = m[i,i] = m[j,j] = 0; m[i,j] হল, m ২-ডি অ্যারের i,j ইনডেক্স।

তাহলে, আমাদের টেবিল দেখতে এরকম হবে। এখানে আমরা cost গুলিকে হিসাব করবো।

length = 2 হলে,
m[1,2] = m[1,1] + m[2,2] + p[0]*p[1]*p[2] = 0+0+30*35*15 = 15750
m[2,3] = m[2,2] + m[3,3] + p[1]*p[2]*p[3] = 0+0+35*15*5 = 2625
m[3,4] = m[3,3] + m[4,4] + p[2]*p[3]*p[4] = 0+0+15*5*10 = 750

m[4.5] = m[4,4] + m[5,5] + p[3]*p[4]*p[5] = 0+0+5*10*20 = 1000

m[5,6] = m[5,5] + m[6,6] + p[4]*p[5]*p[6] = 0+0+10*20*25 = 5000

length = 3;
m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2
এখানে, ৩ দৈর্ঘ্যের জন্য, একবার (A1*A2)*A3, আরেকবার A1*(A2*A3) হিসাবে করে এদের মাঝে মিনিমামটি নিতে হবে। কাজেই m[1,3] = min (7875,18000) = 7875.
lenght = 3 এর জন্য আমরা k এর মান 1,2 ধরবো। এখন এভাবে length = 3 এর জন্য সকল ভ্যালু বসালে আমরা পাবোঃ

এখন length = 4 এর জন্য, k = 1,2,3 ধরে হবেঃ
m[1,4] = m[1,1] + m[2,4] + p[0]*p[1]*p[4] = 14875; k = 1
               m[1,2] + m[3,4] + p[0]*p[2]*p[4] = 21000; k = 2
               m[1,3] + m[4,4] + p[0]*p[3]*p[4] = 9375; k = 3
m[1,4] = min (14875,21000,9375) = 9375

এভাবে বাকি মান বসালে আমরা পাইঃ

length = 5;
m[1,5] = m[1,1] + m[2,5] + p[0]*p[1]*p[5] = 28125

               m[1,2] + m[3,5] + p[0]*p[2]*p[5] = 27250 

               m[1,3] + m[4,5] + p[0]*p[3]*p[5] = 11875; k = 3

               m[1,4] + m[5,5] + p[0]*p[4]*p[5] = 15375
m[1,5] = 11875, so-->

lenght = 6 -->

অর্থাৎ আমাদের ম্যাট্রিক্স মালটিপ্লিকেশন এর জন্য মিনিমাম cost = 15125. এখন আমরা যদি অর্ডার বের করতে চাই, যে কিভাবে আসলে আমরা মাল্টিপ্লিকেশনটি করলাম, এজন্য আমাদের আরো একটি 6x6 সাইজ এর অ্যারে লাগবে। এখানে আমরা প্রতিবার k এর কোন মানের জন্য মিনিমাম ভ্যালুটি নিচ্ছি, সেই k এর মান সেভ করে রাখবো।
যেমন আমরা length = 2 এর সময়, k = 1,2,3,4,5 পর্যন্ত নিয়েছিলাম। সেই অনুযায়ী মিনিমাম সাজালেঃ

আমরা এই অ্যারের নাম দিলাম s, এখানে আমরা k - partition এর নাম্বারগুলি সেভ রাখবো।
length = 3 এর জন্য, আমরা m[1,3] তে যেই মিনিমাম ভ্যালু রেখেছিলাম, সেটি ছিল k = 1 এর ভ্যালু। আমরা এরকম কিছু একটি পেয়েছিলাম-->

m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2

এখানে মিনিমাম ভ্যালু এর জন্য k = 1, কাজেই আমরা s[1,3] = 1 রাখবো। এভাবে length = 3,4,5,6 এর জন্য সাজালে আমাদের বাকি ঘরগুলি সাজায়ে আমরা ফাইনালি এরকম একটি ম্যাট্রিক্স পাবোঃ

অর্ডার প্রিন্ট (Order print)

আমরা এখন আমাদের ম্যাট্রিক্স এর মাল্টিপ্লিকেশন এর অর্ডারটি প্রিন্ট করবো। আমাদের অর্ডার ফাইন্ডিং এর অ্যালগরিদম ঃ

এভাবে আমরা পাবোঃ ( (A1) (A2 A3) ) ( (A4 A5) (A6) )
অর্থাৎ, এই অর্ডারে মাল্টিপ্লিকেশন চালালে আমরা মিনিমাম cost, এক্ষেত্রে 15215 পাবো।
MCM code:

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Uva 348: Optimal Array Multiplication Sequence
• Poj 2246: Matrix Chain Multiplication

২ - পয়েন্টার টেকনিক (Two Pointer Technique)

কোন অ্যারেতে (সর্টেড) সাধারনত জোড়ায় জোড়ায় ভ্যালু খুঁজে বের করার একটি এফিশিয়েন্ট টেকনিক হল ২-পয়েন্টার। আমরা মূলত, কোন সর্টেড অ্যারেতে ২ বা তার বেশি জোড় বের করবো এমনভাবে, যেন তারা কোন কন্ডিশন মেনে চলে। যেমনঃ এমন ১ জোড়া ভ্যালু বের কর যাদের যোগফল X এর সমান হয়, অথবা বিয়োগফল, বা গুনফল ইত্যাদি।
প্রথমে একটি প্রবলেম নিয়ে আলোচনা করা যাক। আমাদের একটি সর্টেড (ছোট থেকে বড়) অ্যারে দেয়া আছে। এখান থেকে এমন একটি জোড়া বের করতে হবে, যাতে তাদের যোগফল X এর সমান হয়। এবং জোড়ার ২ টির ইন্ডেক্স একই হওয়া যাবেনা। আমরা কোড করলে অনেকটা এভাবে ২ টি লুপ চালায়ে করে ফেলবোঃ

এর কপ্লেক্সিটি O(n*(n-1)) যা অনেক বেশি। আমাদের আরও ভালো এপ্রোচ লাগবে। এখন দেখা যাক এই প্রব্লেমটার জন্য ২-পয়েন্টার কিভাবে কাজ করবেঃ

আমরা প্রথমে ২ টি পয়েন্টার সেট করবো। একটি হবে প্রথম ভ্যালুর জন্য, অপরটি হবে দ্বিতীয় ভ্যালুর জন্য। আমরা প্রত্যেকবার চেক করবো X এর সাথে ভ্যালু ২ টির যোগফল মিলে যাচ্ছে কিনা। যদি যোগফল X এর চেয়ে কম হয়, তাহলে আমরা প্রথম পয়েন্টারকে ডানদিকে বাড়াবো। যদি যোগফল X এর চেয়ে বেশি হয়, তাহলে আমরা দ্বিতীয় পয়েন্টারকে বামদিকে কমাবো। অনেকটা বাইনারি সার্চ এর মত কাজ করবে এই ২- পয়েন্টার। এবং আমাদের কন্ডিশন অনুযায়ী প্রথম এবং দ্বিতীয় ভ্যালুর ইনডেক্স সেইম হওয়া যাবেনা। ২ পয়েন্টার এর প্রথমটিকে আমরা 0 (এখানে অ্যারের প্রথম ইনডেক্স 0 ধরে ) এবং পরের পয়েন্টারকে আমরা অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ

এর কমপ্লেক্সিটি হবে O(n)। এখন কিছু ভ্যারিয়েশন দেখা যাকঃ

১ম প্রব্লেম

২ টি সর্টেড অ্যারে(ভিন্ন ভিন্ন সাইজ) থেকে আমাদের এমন ২ টি এলেমেন্ট নিতে হবে (প্রত্যেক অ্যারে থেকে ১ টি), যাতে তাদের যোগফল X এর সমান বা ছোট (ম্যাক্সিমাম যোগফল, অর্থাৎ X এর কাছাকাছি হয়)।

আমরা প্রথম অ্যারেতে একটি পয়েন্টার এবং দ্বিতীয় অ্যারেতে আরেকটি পয়েন্টার সেট করবো। এখন প্রতিবার আমরা চেক করবো X এর সমান অথবা আমাদের ম্যাক্সিমাম সাম X এর কাছাকাছি কিনা, যদি না হয়, আমরা ইনডেক্স আপডেট করবো। এখন যদি সাম X এর চেয়ে কম হয়, তাহলে আমরা প্রথম অ্যারের ইনডেক্স বাড়াবো, নাহলে দ্বিতীয় অ্যারের ইনডেক্স বাড়াবো। এখানে প্রথম পয়েন্টারকে অ্যারের প্রথম ইনডেক্স এবং পরের পয়েন্টারকে অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ

২য় প্রব্লেম

একটি ভিন্ন ভিন্ন (distinct) এলেমেন্ট এর অ্যারে থেকে এমন একটি ট্রিপলেট (তিন টি এলেমেনট এর জোড়া) বের করতে হবে, যাদের যোগফল শুন্য হবে।

২ জোড়ার জন্য আমরা যেভাবে করতাম, এটাও একইভাবে হবে, খালি এক্সট্রা একটি ভ্যালুর জন্য আমরা আগেই একটি ভ্যালু নিয়ে নিব। প্রথমে অ্যারেকে সর্ট করে ফেলবো। এরপরে আমরা আগের মতন যেভাবে জোড়া বের করতাম, একইভাবে এখানেও সেই কাজ করবো। এখানে আমরা একটি ইনডেক্স কে ফিক্সড করে, বাকি ইনডেক্স এর মাঝে ২ টি পয়েন্টার ঠিক আগের মতন করে সেট করবো। কোড দেখা যাকঃ

এখন এভাবে আমরা যেকোন একটি ট্রিপলেট পেলেই প্রোগ্রাম স্টপ করপে দিচ্ছি। যদি আমাদের বলা হয় যে এরকম যত ট্রিপলেট আছে তাদের দেখাও, তাহলে উপরের কোড এ সামান্য একটু পরিবর্তন করলেই আমরা সব ট্রিপলেট পেয়ে যাবো। আমরা লাইন ২১ এ রিটার্ন না করে, l++ এবং r-- করে দিবো। তাহলেই কাজ হয়ে যাচ্ছে।

৩য় প্রব্লেম

আমাদের যদি কোন ট্রিপলেট বের করতে বলে, যাদের যোগফল X এর সমান হবে, আমরা সেইম উপরের টেকনিক অনুযায়ী বের করে ফেলতে পারবো।

৪র্থ প্রব্লেম

এমন ট্রিপলেট বের কর, যাতে যেকোন ২ টির যোগফল, তৃতীয় টির সমান হবে।
এই সমস্যাটিও হুবহু আগের মতই কাজ করবে। আমরা প্রথমে একটি এলেমেন্টকে সেট করবো, এরপরে বাকি ২ টি এলেমেন্ট বের করবো যাতে তাদের সাম, সেট করা এলেমেন্ট এর সমান হয়। কোডঃ

২ - পয়েন্টারের প্রব্লেমগুলিতে আমরা ইনডেক্স কে একেকভাবে সেট করতে পারি, এটা আসলে যে কোড লিখছে তার উপর নির্ভর করে। তবে মূল আইডিয়া ঠিক থাকলে প্রব্লেম এর ফাইনাল আউটপুট সবসময় একই আসবে।

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Leetcode: valid-palindrome
• Leetcode: rotate-array
• Leetcode: two-sum-ii-input-array-is-sorted
• Codeforces: wrath
• Codeforces: strange game on matrix
• Codeforces: bersu ball
• Codeforces: guess a number
• Spoj: roommate agreement
• Spoj: audition

N Puzzle Problem – part 3

আগের পর্ব এখানে ঃ part - 1 , part - 2

মেমরি স্পেস ( Memory Space )

আমরা আমাদের মেমরি স্পেস কমানোর জন্য স্ট্রাকচারকে একটু মডিফাই করতে পারি। আমরা একটি স্ট্রিং এর মধ্যে আমাদের প্রতি স্টেট এর প্রয়োজনীয় সব জিনিস সেইভ রাখতে পারি।

যেমন চিত্রের পাযলটির জন্য আমরা ২ডি অ্যাারে তে ভ্যালুগুলি না রেখে একটি স্ট্রিং এ এভাবে রাখতে পারি ঃ string a = "123046758" । এর মাধ্যমে আমরা পরে এটিকে ইচ্ছা করলে ২ডি গ্রিড এ কনভার্ট করে আমাদের কাজ করতে পারি। এখন আমরা আমাদের প্যারেন্ট ও এভাবে স্ট্রিং এর শেষে অ্যাড করে দিতে পারি। যেমন ঃ a = "123046758L" , এর মানে হচ্ছে এই স্টেট টি Left মুভ দেয়ার পরে আমরা পেয়েছি। আর আমাদের বাকি হিউরিস্টিক ভ্যালু সেইভ। এটাও আমরা একই ভাবে করতে পারি। ব্যাপারটা তোমাদের উপর ছেড়ে দিলাম। এখন আমরা একটি ম্যাপ রাখবো এরকম ঃ map < string, bool > visited;
এই ম্যাপ এর কাজ হচ্ছে আমাদের স্টেট গুলি চেক এ রাখা। মানে একই স্টেট এ যেনো আমরা আবার ফিরে না আশি। এর একটি সুবিধা হল আমাদের অপ্রয়োজনীয় বারতি স্টেট সেইভ রাখা লাগবেনা। আমরা একবার ভিজিটেড কোন স্টেট আবার পেয়েছি কিনা, এটা ম্যাপ এর মাধ্যমে এভাবে চেক করতে পারবো। আরো একটি কাজ আমরা করবো যে, যদি unsolvable state কখনো চলে আসে, তাহলে আমরা তাকে মার্ক করে রাখবো যে এটি বাজে স্টেট, এখানে আসলে সামনে আর একে এক্সপান্ড এর কোন প্রয়োজন নেই। আর আমরা কিউ তে একের বেশি স্টেট কখনো রাখছি না, কাজেই আমাদের মেমরি বেড়ে গিয়ে রান টাইম এরর খাওয়ার সম্ভাবনা কম।

টাইম কমপ্লেক্সিটি ( Time Complexity )

বি এফ এস, ডি এফ এস এর জন্য আমাদের টাইম কমপ্লেক্সিটি হবে O ( b^d ) । এখানে,
b = branching factor ( একটি নোড থেকে সর্বোচ্চ যে কয়টি চাইল্ড নোড জেনারেট হতে পারে, আমাদের পাযল এর ক্ষেত্রে সর্বোচ্চ ৪ টি হতে পারে {উপরে, নিচে, ডানে, বামে} )।
d = depth ( আমাদের নোড জেনারেটের সর্বোচ্চ লেভেল, )

ইটারেটিভ ডিপেনিং সার্চ এর জন্য হবে O ( bd ), O ( b^d ) এর পরিবর্তে। অর্থাৎ আমরা ডি এফ এস মত এগিয়ে যাবো এবং যখন দরকার হবে তখন আমরা নতুন চাইল্ড তৈরী করবো।

A* সার্চ সম্পর্কে জানার জন্য এখানে দেখতে পারো ঃ A* search

N Puzzle Problem – part 2

আগের পর্ব এখানে ঃ part - 1

আগের পর্বে আমরা পাযল এর solvable state নিয়ে কথা বলেছি। এখন আমরা দেখবো কিভাবে আগালে আমরা সহজে পাযল প্রব্লেম সল্ভ করতে পারি।

ছবিটি হল একটি ৮-পাযল এর স্টেট কিভাবে জেনারেট হবে তার একটি স্যাম্পল।

ডি এফ এস ( Depth First Search )

আমরা এটি সল্ভ এর জন্য প্রথমেই ভাবতে পারি ডি এফ এস (Depth_First_Search) এর কথা। এরজন্য আমরা একেকটি স্টেট থেকে সবচেয়ে ডীপ এ যাওয়ার চেষ্টা করবো। যদি আর কোন স্টেট এ না যেতে পারি, তাহলে আবার রিকার্সিভলি ব্যাক করে ফিরে আসবো। কিন্তু এর একটি বড় সমস্যা হল, আমাদের এই নোড জেনারেট এর ব্যাপারটি আমাদের ফাইনাল স্টেট থেকে অনেক অনেক দূরে নিয়ে যেতে পারে, যার কারনে আমরা এক্সপেক্টেড সলুশন পাবোতো নাই, উলটো আমাদের প্রোগ্রাম মেমরি ধারন করতে না পারার কারনে ক্র্যাশ করার সল্ভাবনা অনেক বেশি। কাজেই ডি এফ এস নরমালি করতে গেলে আমাদের জন্য তা সুবিধার হবেনা।

বি এফ এস ( Breadth First Search )

আমরা বি এফ এস এর মাধ্যমেও কাজ করতে গেলে সেইম আগের মতন প্রবলেম এ পরবো। অর্থাৎ BFS & DFS সেইম টাইপ নোড জেনারেট করবে। আমাদের তাই কিছু ট্রিক কাজে লাগাতে হবে যাতে অপটিমাল সলুশন পাওয়া যায়।
যাদের বি এফ এস, ডি এফ এস সম্পর্কে জানা নেই, তারা শাফায়েত ভাই এর ব্লগ থেকে দেখে নিতে পারো।

বি এফ এস
ডি এফ এস

একটি ছোট উদাহরন দেই। ধরি আমি পিযা ডেলিভারি দিবো একটি ১০ তলা বিল্ডিং এ। বিল্ডিং এর প্রতি তলায় আবার ১০ টি করে রুম আছে। একদিন কোন এক কারনে এলাকার মেয়র ঘোষনা দিল যে আজকে এই বিল্ডিং এর সবাইকে পিযা খাওয়ানো হবে । পুরো বিল্ডিং এ পিযা সার্ভের দায়িত্ব পরলো আমার ঘাড়ে -_- । এখন আমার কাছে ২ টি অপশন আছে। আমি প্রথেম ১ তলার সব রুম এ পিযা ডেলিভারি দিলাম, এরপরে ২ তলার সব রুম, এরপরে ৩ তলা... এভাবে ১০ তলা পর্যন্ত ডেলিভারি শেষ করলাম। আরেক কাজ করতে পারি যে, আমি প্রথমে ১ তলার একটি রুম এ পিযা দিয়ে ২ তলায় চলে গেলাম, সেখানের হাতের সবচেয়ে কাছের রুম এ পিযা দিয়ে আবার ৩ তলায়... এভাবে ১০ তলায় দেয়ার পরে আবার ১ তলায় নেমে পরর রুম থেকে একই ভাবে ডেলিভারি শুরু করলাম। এই ২ কাজের মধ্যে প্রথমটি হচ্ছে বি এফ এস, এবং পরেরটি হল ডি এফ এস। আশা করি কোনরকম আইডিয়া তোমরা পেয়েছো।
এখন আমরা কাজের কথায় আসি। আমরা ৮-পাযল সল্ভের ক্ষেত্রে আমাদের জন্য reachable state হল 9! / 2 = 1,81,440। এই ব্যাপারটি কিভাবে আসলো তা এখানে আলোচনা করছিনা। ১৫-পাযল এর জন্য এই মান 16! / 2 = 10,461,394,944,000 । বুঝতেই পারছো, ৮-পাযল শুধুমাত্র ব্রুটফোর্স দিয়ে করা গেলেও, ১৫ এর ক্ষেত্রে এটি সম্ভব না। এজন্য আমাদের লাগবে A* ( এ স্টার ) সার্চ বা ইটারেটিভ ডিপেনিং সার্চ ( Iterative Deepening A* Search or IDA* search )।
আমরা এখানে ডি এফ এস, বি এফ এস স্টাইল এর কাজ করবো, কিন্তু একটু আলাদাভাবে। আমরা একটি ফাংশন নিবো

f  ( n ) = g ( n ) + h ( n ), যেখানে,
f  ( n ) = n তম স্টেট এর ভ্যালু ( cost ) ।
g ( n ) = ইনিশিয়াল স্টেট থেকে  n তম স্টেট পর্যন্ত দূরত্ব।
h ( n ) = হিউরিস্টিক জেনারেশন এর জন্য একটি ফাংশন।

হিউরিস্টিক হল এমন একটি টেকনিক, যা আমাদের অপটিমাল সলুশন খুঁজে বের করতে সাহায্য করে। আমাদের পাযল সল্ভিং এর ক্ষেত্রে A* সার্চে আমরা এই হিউরিস্টিক ব্যবহার করবো। সহজ কথায়, এটি সিম্পল একটি ভ্যালু যা প্রতিটি স্টেট এর জন্য বের করে আমরা আমাদের সুবিধামত সামনে এগিয়ে যাবো।
ছবিটিতে আমরা দেখতে পাচ্ছি যে, ইনিশিয়াল স্টেট থেকে ৪ টি নতুন স্টেট জেনারেট হয়েছে। আমরা A* সার্রচের জন্য এই প্রতিটি চাইল্ড স্টেট এর হিউরিস্টিক ভ্যালু বের করবো। এরমধ্যে যেই ভ্যালু সবার চেয়ে কম, আমরা সেই চাইল্ড কে পরবর্তী স্টেট এর জন্য এক্সপান্ড ( Expand or Branching; creating next child for further calculation ) করবো।

হিউরিস্টিক ব্যবহারের সুবিধা ঃ

অপটিমাল সলুশন সহজে স্বল্প সময়ের মধ্যে বের করে নিয়ে আসা যায়,  এবং অপ্রয়োজনীয় নোড মেরে ফেলে ( removal of unnecessary nodes )।

Coding:

এখন আমরা আলোচনা করবো কোডিং নিয়ে। প্রথমেই আমরা ইনিশিয়াল স্টেট থেকে নোড এক্সপান্ড করবো। এখন যেকোন একটি হিউরিস্টিক ফাংশন আমরা ব্যবহার করবো। ইনিশিয়াল স্টেট এ g ( n ) = 0। এই স্টেট এর জন্য আমরা h ( n ) , f ( n ) বের করবো। আমরা এই প্যারেন্ট কে এক্সপান্ড করে কতগুলি চাইল্ড নোড পাবো। এবার কাজ হচ্ছে প্রতিটি চাইল্ড নোড এর জন্য আমরা f ( n ) বের করবো। এবং এর মধ্যে সবচেয়ে কম যার মান, আমরা সেটি নিয়ে সামনে এগিয়ে যাবো। এই সামনে এগিয়ে যাওয়ার মানে হচ্ছে একটি কিউ তে আমরা স্টেট গুলি জমা রাখবো। এখন আমরা এভাবে একটি স্ট্রাকচার ডিক্লার করতে পারি-->

struct node
{
int grid [ N ] [ N ] ;            // 2D grid to save the state
int h_val;                            // heuristic value of the state
char parent ;                     // parent =  { 'U', 'D', 'L', 'R' }
};

এখানে grid ২ডি অ্যাারেতে আমরা আমাদের পাযল এর স্টেট এর ভ্যালুগুলি রাখবো। h_val এর মাঝে থাকবে এই গ্রিড এর জন্য জেনারেট করা হিউরিস্টিক ভ্যালু। parent ভ্যারিয়েবল এর মাঝে আমরা প্যারেন্ট স্টেট থেকে কোন মুভ এ এই স্টেট এ এসেছি সেটি সেভ রাখবো। (এ ব্যাপারটি আমাদের জানা থাকলে ব্যাকট্র্যাক এর ক্ষেত্রে সুবিধা হবে)
এখন আমাদের একটি কিউ লাগবে যেখানে এই নোডগুলি রাখবো আমরা। শুরুতে আমরা কিউ তে আমাদের ইনিশিয়াল স্টেট এর যে পাযল দেয়া আছে তা রাখবো। এরপরে আমরা কিউ থেকে এই নোড পপ করে এর চাইল্ড জেনারেট করবো। এখন চাইল্ড জেনারেট এর সাথে সাথে আমরা প্রত্যেক চাইল্ডের হিউরিস্টিক ও জেনারেট করবো। এরপরে আমরা এই হিউরিস্টিক এর মধ্যে যার মান কম, সেই চাইল্ডকে কিউ তে পুশ করবো। এখন নরমাল বি এফ এস এ আমরা কিন্তু সব চাইল্ড ই পুশ করতাম। এখানেও তা করা যাবে, কিন্তু ১৫-পাযল এর ক্ষেত্রে খুব কষ্টকর হবে ব্যাপারগুলি ঠিকমত হিসাব নিকাশ করা। কারন, মেমরি, টাইম কমপ্লেক্সিটি এর ব্যাপারগুলি আমাদের মাথায় রাখা লাগবে। আর যেহেতু আমরা A* সার্চ ব্যবহার করছি, আমাদের অপ্রয়োজনীয় চাইল্ড নোড জেনারেট না করাই উত্তম। যখন দরকার হবে আমরা তখন জেনারেট করবো। নিচের ছবিটি খেয়াল করি ঃ

ইনিশিয়াল স্টেট টি থেকে আমরা ৩ টি চাইল্ড নোড পেলাম। এদের f ( n ) বের করলাম। এবং এরমধ্যে সবচেয়ে কম যার মান, তাকে আমরা পরবর্তীতে কিউ তে পুশ করবো। এখন যেহেতু আমরা কিউ তে বাকি ২ টি নোড পুশ করছিনা, কাজেই আমাদের মেমরি স্পেস এক্ষেত্রে অনেক বেঁচে যাবে। কিউ তে চাইল্ড নোডটি পুশ এর সময় আমরা parent ভ্যারিয়েবল এর মধ্যে 'L' ক্যারেক্টারটি রাখবো, কারন 4 কে Left এ নেয়ার মাধ্যমে আমরা এই চাইল্ড নোডটি পেয়েছি। আমরা বলেছিলাম যে আমাদের এই ভ্যারিয়েবল এর মান ব্যাকট্র্যাকিং এর কাজে লাগবে। আমরা সেটি এখন আলোচনা করবো। আশা করি, এ পর্যন্ত সবকিছু বুঝে গেছো। এখন ধরি আমাদের প্যারেন্ট নোডের f এর মান এর চেয়ে প্রতিটি চাইল্ড নোডের f এর মান বেশি আসলো। এখন আমরা যেই চাইল্ড ই নেই না কেনো, ব্যাপারটি কিন্তু আসলে খারাপ হবে, কারন কম f এর মান থেকে আমরা আবার বেশি মানের দিকে আগাচ্ছি। আমাদের মেইন টার্গেট হচ্ছে যত কম মুভ এ পাযল সল্ভ করা যাএ, অর্থাৎ আমাদের f এর মান কমাতে হবে। এখন যদি এরকম অবস্থা হয়, তখন আমাদের সেই চাইল্ড নোড থেকে আবার প্যারেন্ট এ ব্যাক করতে হবে।

এখন আমাদের কাছে তো বর্তমান নোড ছাড়া আর কোন নোড নেই, তাহলে কিভাবে প্যারেন্ট এ ব্যাক করবো? এরজন্য আমাদের তখন দেখতে হবে parent ভ্যারিয়েবল এর মধ্যে কি আছে।যা থাকবে তার বিপরীত স্টেট দিয়ে ব্যাক মুভ করলে আমরা আমাদের প্যারেন্টকে আবার পাবো। মানে যদি ভ্যারিয়েবল এ থাকে 'L', তাহলে আমাদের 'Right' মুভ করতে হবে আগের স্টেট পাওয়ার জন্য। এখন আগের স্টেট পাবার পরে আবার আমরা সব চাইল্ড জেনারেট করবো। এখন যেই চাইল্ড আগে নিয়েছিলাম, সেটি না নিয়ে, তার ঠিক পরের হিউরিস্টিক মান অনুযায়ী আমরা চাইল্ড নিবো।

ধরি আমাদের ইনিশিয়াল স্টেট এ f = 45। এর ৩ টি চাইল্ড জেনারেট করি।

৩ টি চাইল্ডের মধ্যে f = 42 আমরা সিলেক্ট করবো এবং একে কিউ তে পুশ করে এক্সপান্ড করবো।

এখন খেয়াল করে দেখি যে, আমরা নতুন যে ৩ টি চাইল্ড পেলাম, তাদের প্রত্যেকের  f এর মান প্যারেন্ট এর f এর মান থেকে বেশি। কাজেই আমাদের এই নোড এক্সপান্ড করা আসলে ঠিক হয়নি। তাই আমাদের ব্যাকট্র্যাক করতে হবে।

ব্যাকট্র্যাক করে আগের অবস্থায় ফিরে আসলাম। এখন আমরা নিবো f = 43  কারন, আগের f এর মানের ঠিক পরবর্তী মান এটি।

এবার আমরা এই নোডকে এক্সপান্ড করে নতুন চাইল্ড পেলাম, যার মধ্যে একটির f এর মান 41, যা আগের তুলনায় ভালো মান আমাদের প্রব্লেম সল্ভিং এর জন্য। তাই আমরা এখন এটি নিয়ে কাজ করবো।
এই ছিল আসলে ব্যাসিক কোডিং এর হিন্টস। একেকজনের কোডিং স্টাইল অনুযায়ী কোডের আইডিয়া চেঞ্জ হবে, আরো বেটার আইডিয়া আসবে। পরবর্তী পর্বে আমরা দেখবো এই সার্চিং এর মধ্যে কিছু অপটিমাইজেশন আনা যায় কিনা।

পরবর্তী পর্ব : part - 3

N Puzzle Problem - part 1

ছবিটি একটি ৮-পাযল ( 8 - Puzzle ) এর ছবি। এখানে ১ থেকে ৮ পর্যন্ত ইউনিক ৮ টি নম্বর আছে। এবং একটি ফাঁকা ঘর আছে। আমাদের কাজ হচ্ছে পাযলটি কে ফাইনাল স্টেট এ নিয়ে আসা। এক্ষেত্রে আমরা ফাঁকা ঘরটির উপর ভিত্তি করে উপরে, নিচে, ডানে এবং বামে মুভ দিতে পারবো। আমাদের কাজ হচ্ছে নিচের ছবির মতন স্টেট এ আসা।

আমরা হিসাবের সুবিধার্থে ফাঁকা ঘরটিতে 0 (শুন্য) বসিয়ে হিসাব করবো। একটি ডেমোন্সট্রেশন দেখা যাক -->

আমরা প্রথমে বামে( 4 কে 0 এর ঘরে নিয়েছি, কাজেই আমাদের বামদিকে মুভ হয়েছে ), এরপরে উপরে এবং আবার বামে গিয়ে স্টেট মিলাতে পেরেছি। আমাদের ইনিশিয়াল থেকে মোট ৩ টি মুভ দেয়া লাগার কারনে আমাদের টোটাল মুভ লেগেছে ৩ টি। আমাদের কাজ হচ্ছে, এরকম পাযল দেয়া থাকলে ইনিশিয়াল থেকে ফাইনাল স্টেট এ সবচেয়ে কম কত মুভ এ যাওয়া যায় এবং মুভগুলি কিকি তা হিসাব করা।
এটা একটি ৮-পাযল প্রব্লেম। এখানে n এর মান ৩। কাজেই একটি n*n ২ডি গ্রিড এর মধ্যে 0 থেকে n²-1 পর্যন্ত সংখ্যা থাকবে। n এর মান ৪ হলে আমরা তাকে ১৫-পাযল বলবো।

Unsolvable State for N Puzzle Problem

আমরা এখানে ৮-পাযল নিয়ে আলোচনা করবো। সব ৮-পাযল স্টেট কিন্তু সল্ভ করা নাও যেতে পারে। unsolvable এরকম স্টেট আসতে পারে আমাদের কোন এক মুভ এ। আমরা হাতে কলমে কিছুদূর আগালে হয়তোবা বুঝতে পারবো যে এটা সল্ভ করা সম্ভব না। কিন্তু কম্পিউটার কে এটা কিভাবে বুঝাবো? এরজন্য আমাদের কিছু প্যাটার্ন অ্যাানালাইসিস করা লাগবে যে কিকি কারনে একটি পাযল unsolvabel state আছে তা আমরা সহজে বুঝতে পারি।
আমাদের একটি n*n গ্রিড দেয়া আছে। কিছু নিয়ম খেয়াল করলে আমরা বলতে পারবো যে n*n-1 পাযলটি সল্ভ করা যাবে কিনা। নিয়মগুলি খেয়াল করি --- >

১। যদি n এর মান বেজোড় হয়, তাহলে পাযলের স্টেটটি সল্ভ করা যাবে শুধুমাত্র তখনি যখন ঐ স্টেট এর ইনভার্শন (inversion) সংখ্যা জোড় হবে।

২। যদি n এর মান জোড় হয় (১৫-পাযল এর ক্ষেত্রে n এর মান ৪, যা জোড়) তাহলে পাযলের স্টেটটি সল্ভ করা যাবে যদি-->

• যদি গ্রিড এর নিচ থেকে শুরু করে জোড় পজিশন (second_last, fourth_last,... ) এ ফাঁকা ঘরটি থাকে এবং ইনভার্শন সংখ্যা বেজোড় হয় অথবা,
• যদি গ্রিড এর নিচ থেকে শুরু করে বেজোড় পজিশন (last, third_last,fifth_last,... ) এ ফাঁকা ঘরটি থাকে এবং ইনভার্শন সংখ্যা জোড় হয়।
  

** এখানে পজিশন হল, নিচের সারি ( একদম শেষ সারিকে ১ ধরে ) থেকে শুরু করে উপরে উঠতে থাকলে যেই সারি তে আমরা ফাঁকা ঘরটি পাবো সেই সারি নম্বর।

৩। বাকি সকল ক্ষেত্রে পাযলটি সল্ভ করা সম্ভব হবেনা।

Inversion Count for a N Puzzle State

আমরা গ্রিডটি কে ২ডি থেকে ১ডি তে কনভার্ট করি। তাহলে উপরের উদাহরন অনুসারে আমরা এভাবে মানগুলিকে সাজাই --> 1  2  3  0  4  6  7  5  8
এখানে পজিশন হল ২, কারন নিচ থেকে শুরু করে ২ নং সারিতে আমাদের ফাঁকা ঘরটি আছে।
এখন এটি একটি ১ডি অ্যাারের মতন হয়ে গেল। এখন আমরা এখানে সকল পেয়ার (pair) সংখ্যা এর জন্য দেখবো যে ,
একটি সংখ্যা তার পরের সংখ্যা থেকে বড় কিনা। যদি বড় হয়, তাহলে আমরা ইনভার্শন এর মান বাড়াবো। তাহলে এই অ্যাারে থেকে খেয়াল করলে আমরা সকল পেয়ার এর মধ্যে হিসাব করলে দেখবো যে ২ টি সংখ্যা এর মধ্য নিচের পেয়ারগুলি আমাদের ইনভার্শন হবার শর্ত পূরণ করে-->

• ( 6, 5 ) as 6 > 5
• ( 7, 5 ) as 7 > 5

তাহলে আমাদের ইনভার্শন সংখ্যা হচ্ছে ২ যা জোড়। এবং এই পাযল এর জন্য n এর মান ৩, যা বেজোড়। এবং এটি আমাদের unsolvable puzzle state এর ১ নং শর্তটি পূরণ করেছে। কাজেই, পাযলের এই স্টেটটি সল্ভেবল একটি স্টেট। আরেকটি পাযল দেখা যাক-->

এখানে  2  1  3  4  5  6  7  8  9  10  11  12  13  14  15  0
সুতরাং আমাদের ইনভার্শন সংখ্যা হবে ১। ( যেহেতু পেয়ার < 2, 1 > ই কেবলমাত্র শর্ত মানে )।
আর যেহেতু ইনভার্শন সংখ্যা বেজোড় এবং n  এর মান এখানে জোড় ( 4 ) কাজেই এটি unsolvable puzzle state এর ২নং শর্ত অনুযায়ী , 0 নিচ থেকে শুরু করে বেজোড় পজিশন এ আছে। এবং ইনভার্শন সংখ্যা এর মান ও বেজোড়। কাজেই এটি একটি unsolvable state । এই স্টেট থেকে কখনো আমরা ফাইনাল স্টেট এ যেতে পারবোনা।

** আমরা কিন্তু ইনভার্শন কাউন্ট এর সময় 0 কে কখনো ধরবো না। হিসাবের সুবিধার্থে আমরা 0 নিয়েছি, যাতে প্রোগ্রাম লিখার ক্ষেত্রে আমাদের সুবিধা হয়। এখানে 0  আসলে ফাঁকা ঘর, যা আমরা আগেই বলে এসেছি।

আরো কিছু উদাহরন দেখা যাক--->

এখানে একটি n-puzzle এর সল্ভ চেকিং এর কোড দেয়া হল। ইচ্ছামতন গ্রিড সাইজ দিয়ে কোড রান করলে আমরা বলতে পারবো স্টেট টি সল্ভ করা সম্ভব কিনা।


Sources:
https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
পরবর্তী পর্ব পাওয়া যাবে এখানে ঃ part - 2 

A* Search Algorithm for N-Puzzle

আমরা A* সার্চ দিয়ে ৮-পাযল প্রব্লেমটি সল্ভ করার চেষ্টা করবো। শুরুতে একটি স্ট্রাকচার এ আমরা আমাদের স্টেট সেইভ রাখার জন্য স্ট্রিং, পাথ সেইভ রাখার জন্য আরেকটি স্ট্রিং, হিউরিস্টিক, ডেপথ এসব সেইভের জন্য ইন্টিজার। তাহলে স্ট্রাকচার এমন দাঁড়ায় ঃ

struct puzzle {
string state, path;
int heuristic, depth, f;
}

আমরা f এর মাঝে depth + heuristic সেইভ রাখবো প্রতিটি স্টেট এর জন্য। এখন আমাদের কাজ হচ্ছে একটি প্রায়োরিটি কিউ নেয়া। প্রায়োরিটি কিউ তে আমরা f এর মান অনুসারে নোড ইনসার্ট করবো। তাহলে যার f এর মান কম, সেটি আমরা আগে প্রসেস করবো।

আমরা ইনিশয়াল এ আমাদের স্টেট এর পাথ এর জন্য "0" পুশ করতে পারি path স্ট্রিং এ, depth হবে 0 এবং f এর মান হবে, depth + heuristic = ( হিউরিস্টিক হিসাব করে যত হয়, আমরা তা বসাবো )।
চাইল্ড নোড জেনারেট এর পরে, চাইল্ড এর ক্ষেত্রে depth = parent.depth + 1 এবং path এর ক্ষেত্রে আমরা যদি UP ,মুভ দেয়ার ফলে চাইল্ডটি পেয়ে থাকি, তাহলে path = parent.path + "U" এভাবে পুশ করে দিবো।
আমরা যদি আমাদের ফাইনাল স্টেট পেয়ে যাই, তাহলে আমরা path স্ট্রিংটি রিটার্ন করে দিবো, এবং এই path থেকে পরবর্তীতে আমরা ইনিশিয়াল থেকে ফাইনাল স্টেট এর গ্রিড ও প্রিন্ট করতে পারবো।

২ টি ভেক্টর নিবো open এবং close নামের। open এর কাজ হচ্ছে, আমরা যেসব নোড এখনও এক্সপান্ড করিনি, সেগুলি রাখবো। আর close এর মাঝে আমরা, যেসব নোড এর এক্সপান্ড হয়ে গেছে,সেগুলো রাখবো।open, close এর কাজ হল, অপ্রয়োজনীয় নোড নিয়ে আমাদের মাথা ব্যথা আর করা লাগবেনা। আমরা প্যারেন্ট নোড থেকে চাইল্ড বানানোর পর দেখবো যে, এই চাইল্ড আগে থেকেই open এর মাঝে আছে কিনা, যদি থাকে, এবং ঐ open এর চাইল্ড যদি আমাদের এখন পাওয়া চাইল্ড এর চেয়ে ভালো অথবা সমান হয়, তাহলে আমরা এখনকার চাইল্ড আর নোড এ পুশ করবোনা। একই কাজ আমরা close এর খেত্রেও করবো।
আর এরকম কিছু না হলে আমরা সেটি কিউ তে পুশ করবো। এভাবে কাজ চলতে থাকবে, এবং আমরা আমাদের ফাইনাল স্টেট পেলে ব্রেক করে দিবো আর পাথ এর স্ট্রিংটি থেকে আমরা ইনিশিয়াল থেকে সহজেই পাথ ও প্রিন্ট করতে পারবো।

pseudocode:

path_finding:

সার্চিং অ্যালগরিদম (Searching Algorithm)

লিনিয়ার সার্চ(Linear Search)

লিনিয়ার সার্চ সবচেয়ে ব্যাসিক সার্চ টেকনিক। ধরি আমাদের n টি নম্বর এর একটি অ্যাারে দেয়া আছে। এখন আরেকটি নম্বর a দিয়ে আমাকে জিজ্ঞাসা করা হল, এই a , আগের n টি নম্বর এর মাঝে আছে কিনা। স্বাভাবিকভাবে আমরা 0 থেকে n (অ্যাারে এর ঘর বিবেচনা করলে) পর্যন্ত একটি লুপ চালায়ে নম্বরটিকে বের করার চেষ্টা করবো।
int arr [ ] = { 1, 2, 4, 12, 14, 78, 21, -90, 111, 1467};
int a = 111;
for ( int i = 0; i < 10; i++ ){
          if ( arr [ i ] == a ){
                cout << " Found the number :D " << endl;
                break;
          }
}

সার্চিং এর ক্ষেত্রে লিনিয়ার সার্চ ছোট রেঞ্জ এর মধ্যে কাজ করবে কিন্তু রেঞ্জ বড় হয়ে গেলে TLE দিবে। আমরা লিনিয়ারি একটি পজিশন থেকে আরেকটি পজিশন এ যাচ্ছি ( n তম এলেমেন্ট পাওয়ার জন্য আমাদের শুরু থেকে n পর্যন্ত যেতে হবে), কাজেই লিনিয়ার সার্চের কমপ্লেক্সিটি O ( n )  [ Order of n ] যেখানে n হল কতটি এলেমেন্ট এর মাঝে সার্চিংটি চলছে।

বাইনারি সার্চ(Binary Search)

বাইনারি সার্চ সবচেয়ে জনপ্রিয় সার্চ টেকনিক এবং এর ব্যবহার ও খুব মজার। বাইনারি সার্চের জন্য প্রথমেই আমাদের নম্বরগুলিকে কোন একটি অর্ডার এ সাজাতে হবে ( Ascending or Descending )। এরপরে আমরা ২টি পজিশন সেট করবো low এবং high নামে। low  হবে আমাদের অ্যাারে এর 0th ইনডেক্স এবং high হবে (n-1)th ইনডেক্স। এখন আমরা এই high এবং low এর মাঝে থেকে middle ইনডেক্স বের করার চেষ্টা করবো এবং চেক করবো ঐ middle ইনডেক্স এর ভ্যালুটা আমাদের কাঙ্ক্ষিত ভ্যালুর সাথে মিলে গেছে কিনা। যদি মিলে যায়, তাহলে আমরা আমাদের ভ্যালু পেয়ে গেছি। যদি না মিলে, তবে ২টি কন্ডিশন হতে পারে।
১ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে বড়।
২ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে ছোট।
ধরি আমাদের অ্যাারেটি ছোট থেকে বড় আকারে সাজানো আছে। এখন ১ এর জন্য মিড ভ্যালুটি বড়, কাজেই আমাদের কাঙ্ক্ষিত ভ্যালুটি মিড ইনডেক্স এর অবশ্যই আগে আছে। কাজেই তখন আমাদের high হয়ে যাবে middle - 1 এবং low এর কোন চেঞ্জ হবেনা। ২ঃ এর খেত্রেও একই ব্যাপার। তখন low হবে middle + 1 এবং high এর কোন চেঞ্জ হবেনা। একটি উদাহরন দেখিঃ আমাদের ২০ কে খুঁজে বের করতে হবে।

টাইম কমপ্লেক্সিটি ঃ আমরা প্রতিবার সার্চিং এর জন্য একটি অংশ নিচ্ছি এবং অন্যটি বাদ দিয়ে দিচ্ছি। কাজেই worst case এর জন্য আমাদের কমপ্লেক্সিটি হবে O ( N * logN )।

স্যাম্পল কোড ঃ


আমরা ভ্যালু পেয়ে গেলে ভ্যালুটির ইনডেক্স রিটার্ন করবো, আর না পেলে -1 রিটার্ন করবো। লক্ষ্য করলে দেখবে যে বাইনারি সার্চ এর টারমিনেট কন্ডিশন যখন high এর চেয়ে low এর ইনডেক্স বড় হয়ে যাবে। এই ব্যাপারগুলি ভালোভাবে খেয়াল না রাখলে ইনফিনিট লুপ এ পরবে প্রোগ্রাম। কোড করার সময় তাই আমাদের মাথায় রাখতে হবে আসলে কখন কোথায় কি হচ্ছে এবং কখন কোন কন্ডিশন দিলে ঠিকমতন প্রোগ্রাম রান করবে।

স্লাইডিং উইন্ডো (Sliding Window Technique)

প্রোগ্রামিং কন্টেস্টে আমাদের অনেক সময় ৩ বা ৪ বা এরচেয়েও বেশি লুপ এর কোড লিখতে হয়। ব্যাসিকালি ব্রুটফোর্স যাকে বলে। এখন আমরা যেই টেকনিক দেখবো, এটি এরকম একাধিক লুপ এর প্রব্লেমকে কম সময়ে সল্ভ করে দিতে পারবে।

স্লাইডিং উইন্ডো সমস্যার বিভিন্ন রূপ আছে। কিন্তু তাদের সবারই একটি কমন বৈশিষ্ট আছে : একটি সাব-অ্যারেকে (আমরা একে 'উইন্ডো' বলে থাকি, যা স্ট্যাটিক বা ডাইনামিক দৈর্ঘ্য থাকতে পারে) আমরা  n সংখ্যক উপাদানগুলির অ্যারে এর বাম থেকে ডান দিকে লিনিয়ারভাবে সরায়ে কিছু কম্পিউট করার চেষ্টা করবো। এভাবে উইন্ডো স্লাইড করার টেকনিক কেই স্লাইডিং উইন্ডো বলে। স্লাইডিং উইন্ডোর অনেক রকম ভ্যারিয়েশন আছে। যেমন ঃ 

1. একটি অ্যারের মাঝে ফিক্সড সাইজের কোন সাব-অ্যারের ম্যাক্সিমাম সামেশন বের করা। যেমন ঃ অ্যারে  A = {10, 40, 10, 30, 20} এবং উইন্ডো সাইজ w = 3 হলে, মাক্সিমাম সামেশন = 40+10+30 = 80.
   
2. একটি অ্যারের মাঝে ফিক্সড সাইজের সকল সাব-অ্যারের ম্যাক্সিমাম অথবা মিনিমাম সংখ্যা বের করা। যেমন ঃ
   অ্যারে A = {0, 5, 5, 3, 10, 0, 4} , n = 7 এবং উইন্ডো সাইজ w = 3, হলে এখানে n-w+1 = 5 টি ভিন্ন ভিন্ন সাব-অ্যারে আছে যাদের সাইজ = 3; {0, 5, 5}, {5, 5, 3}, {5, 3, 10}, {3, 10, 0}, {10, 0, 4}. এবং আমরা এদের ম্যাক্সিমাম সংখ্যা বের করতে চাইলে এগুলি হবে ঃ 5, 5, 10, 10, 10 প্রতি সাব-অ্যারের জন্যে।
   
3. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর, যার এলেমেন্ট এর সাম, নির্দিষ্ট কোন সাম S থেকে বড়/ সমান/ ছোট হয়। যেমন ঃ অ্যারে A = {5, 1, 2, 3, 4, 2} এবং S = 7 হলে,
   মিনিমাম দৈর্ঘ্য == 7 : 2,  {5, 1, 2, 3, 4, 2}
   মিনিমাম দৈর্ঘ্য > 7 : 3,  {5, 1, 2, 3, 4, 2} , {5, 1, 2, 3, 4, 2}, {5, 1, 2, 3, 4, 2}
   মিনিমাম দৈর্ঘ্য < 7 : 1,  {5, 1, 2, 3, 4, 2} ; যেকোনটাই হতে পারে।
   
4. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর যাতে  [ 1 to w ] পর্যন্ত সকল সংখ্যা কমপক্ষে একবার করে হলেও থাকবে। যেমনঃ A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} এবং w = 4, আমরা 13 length এর একটি সাব-অ্যারে পাবো, যাতে 1, 2, 3, 4 আছে। এই সেইম অ্যারের জন্যে যদি w = 3 হয়, তাহলে A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} আমরা 3 length এর একটি সাব-অ্যারে পাবো। 

সলুশন (Solution)
উপরের প্রবেল্মগুলি আমরা নরমালি বারে বারে লুপ চালায়ে সল্ভ করতে পারবো তখনি, যখন রেঞ্জ কম হবে, যা আমাদের given time এর মাঝে সল্ভ করা সম্ভব হয়। আমরা ব্রুটফোর্স এর ব্যাপারগুলি বাদ দিয়ে সরাসরি আমাদের স্লাইডিং উইন্ডো টেকনিক এ চলে আসি, যা কিনা O (n) সময়ে সল্ভ করতে সক্ষম।

১ম টেকনিক (First Technique):

আমরা প্রথমে উইন্ডো তে আমাদের প্রথম w টি ইন্টিজার ইন্সার্ট করে দিলাম এবং এদের সাম বের করে তাকে curr_sum ভ্যারিয়েবল এ রাখলাম। এরপরে আমরা স্লাইড করে করে আগাবো। আমরা ডান পাশে একটি একটি করে এলেমেন্ট উইন্ডো তে ইন্সার্ট করবো এবং বাম দিক থেকে একটি করে সরায়ে দিব, ফলে আমাদের উইন্ডোর সাইজ সেইম থাকবে।এলেমেন্ট ইন্সার্ট এর সময় আমরা চেক রাখবো যে এখন আমরা ম্যাক্সিমাম সাম পেলাম কিনা। প্রতিবার ইন্সার্ট করার সময় আমাদের নতুন সাম হবে curr_sum + inserted_element - removed_element. এভাবে আমরা পুরো অ্যারেকে স্লাইড করে রেসাল্ট পাবো।

২য় টেকনিক (Second Technique):

যদি n এর মান অনেক বড় হয়, সকল সাব-অ্যারের মাক্স/মিন বের করা একটু কঠিন হবে। এজন্য আমরা deque (double ended queue) ব্যবহার করবো। এখন আমাদের উইন্ডো হবে আমাদের deque টি। আমরা deque কে ascending order ( ছোট থেকে বড় ) এ সাজাবো ( যদি মিন বের করতে চাই)। deque এর প্রথম দিকে আমাদের মিনিমাম এলেমেন্ট গুলি থাকবে। কিন্তু এভাবে কাজ করতে গেলে একটি বড় প্রব্লেম হল, আমাদের মূল অ্যারের ইন্ডেক্সগুলি উল্টাপাল্টা হয়ে যাবে, এজন্য আমাদের ইন্ডেক্স এর ট্র্যাক রাখতে হবে যাতে আমরা বুঝতে পারি যে, এলেমেন্ট উইন্ডো তে আছে কি নাই। নিচের একটি স্যাম্পল কোড দেয়া হল ঃ

৩য় টেকনিক (Third Technique):

আমরা একটি ডাইনামিক সাইজ উইন্ডো মেইন্টেইন করবো, যেখানে ভ্যালু যোগ করতে থাকবো। মিন/ ম্যাক্স/ ইকুয়াল, কোন এক কন্ডিশন পেলে আমরা আমাদের মিনিমাম উইন্ডো সাইজ পেয়ে যাবো। প্রোগ্রাম এ কি চাওয়া হয়েছে তার উপরে ভিত্তি করে আমাদের কোড এ কন্ডিশন এর পরিবর্তন হবে। এখানে আমরা ১ম টেকনিক এর মত করে ইন্সার্ট করতে থাকবো এবং কন্ডিশন চেক করবো। আর এলেমেন্ট উইন্ডোতে আছে কিনা, উইন্ডো সাইজ কি আমাদের মূল অ্যারে থেকে বড় হয়ে গেলো কিনা - এসব আমরা ২য় টেকনিক এর মত একটি deque নিয়ে চেক করতে পারি।

৪র্থ টেকনিক (Fourth Technique):

আমরা এমন একটি উইন্ডো মেইন্টেইন করবো যা কিনা 1 to w সকল সংখ্যা যদি না পাই, উইন্ডো সাইজ বারাতে থাকবে, নাহলে সাইজ কমাতে থাকবে। আমরা মিনিমাম উইন্ডো সাইজের ট্র্যাক রাখবো। 1 to w সকল এলেমেন্ট পেয়ে গেলাম কিনা এটি আমরা নরমাল একটি ফ্রিকুয়েন্সি কাউন্টের মাধ্যমে করতে পারি। যখন সকল এলেমেন্ট এর কাউন্ট >0 হবে, তখন আমরা আমাদের মিনিমাম উইন্ডো সাইজ রিটার্ন করে দিবো।

প্র্যাক্টিস প্রব্লেম (Practice Problems): 

• Uva 1121 (Subsequence)
• Uva 11536 (Smallest-Sub-Array)
• LeetCode 239 (Sliding Window Maximum)
• HackerRank (The Maximum Subarray)
• Spoj (KOIREP - Representatives)
• Codeforces (Bear and Square Grid)

Lexicographic rank of a string(without duplicate character)

লেক্সিকোগ্রাফিক বলতে বুঝায় অ্যালফাবেটিকাল অর্ডার। যেমনঃ কোন স্ট্রিং "xyz" হলে, আমরা বলতে পারি এই স্ট্রিং এর লেক্সিকোগ্রাফিক অর্ডারের প্রথমে আছে "xyz", এরপরে "xzy" .. অর্থাৎ স্ট্রিং এর সকল পারমুটেশন এর সিরিয়াল, যারা কিনা ছোট থেকে বড় আকারে সর্টেড অবস্থায় আছে। এখন এরকম একটি স্ট্রিং দেখে আমাদের বলতে হবে এর র‍্যাঙ্ক কত। যেমনঃ "abc" এর ক্ষেত্রে, rank of "abc" = 1, rank of "acb" = 2 .... এভাবে।
একদম ব্যাসিকভাবে চিন্তা করলে আমরা সকল পারমুটেশন জেনারেট করে দেখতে পারি যে স্ট্রিং টি কততম পারমুটেশন এর সাথে মিলে গেছে। তাহলে সেটিই আমাদের স্ট্রিং এর র‍্যাঙ্ক।



এভাবে আমাদের টাইম কমপ্লেক্সিটি অনেক বেড়ে যাবে, প্রায় এক্সপোনেন্ট হারে!! (exponent) এজন্য আমাদের আরো ভালো এপ্রোচ দরকার।
আমরা একটি স্ট্রিং ধরি, "FRIEND" এর র‍্যাঙ্ক বের করতে হবে। এখানে প্রথম ক্যারেক্টার  "F" এবং "F" এর চেয়ে ছোট ২ টি ক্যারেক্টার আছে ("D", "E") এবং "F" কে তার জায়গায় ফিক্সড করলে আমাদের বাকি থাকে আরো ৫ টি জায়গা এবং "F" এর আগের ২ টি ক্যারেক্টার ঐ ৫ টি জায়গায় বসতে পারবে ৫ ফ্যাক্টরিয়াল (5!) উপায়ে। তাহলে ২ টির জন্য কম্বিনেশন হবে ২*৫!
এখন আমরা তাহলে "F" এর কাজ শেষ হলে, "F" কে ফিক্সড করে দেই। মানে "F" নিয়ে আমাদের আর মাথা ব্যথা করতে হবে না। এখন দ্বিতীয় ক্যারেক্টার "R" নিয়ে দেখি। "R" এর চেয়ে ছোট ৪ টি ক্যারেক্টার আছে ("D", "E", "I", "N"). ["F" কে আমরা ফিক্সড করে দিয়েছি, কাজেই "F" বাদ] 
তাহলে আমরা "R" এর জন্য পাবোঃ ২*৫! + ৪*৪! (আগের "F" এরগুলোও ধরতে হবে)।
একই ভাবে আমরা বাকি ক্যারেক্টার গুলোর জন্য করে ফেলিঃ

"I" = 2*5! + 4*4! + 2*3!
"E" = 2*5! + 4*4! + 2*3! + 1*2!
"N" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1!
"D" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0!
তাহলে, "FRIEND" এর জন্য র‍্যাঙ্ক হবে ঃ 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0! = 351
যেহেতু, র‍্যাঙ্ক ১ থেকে শুরু হয়, কাজেই আমাদের ফাইনাল রেজাল্ট হবে 1 + 351 = 352.



এর কপ্লেক্সিটি O(n²)। আমরা একটু বুদ্ধি খাটালে এর কমপ্লেক্সিটিকে কমিয়ে আনতে পারবো। এজন্য আমরা কিউমুলেটিভ ভাবে প্রতিটি ক্যারেক্টারের চেয়ে ছোট ক্যারেক্টারকে একটি অ্যারেতে সেভ করে রাখবো।এরপরে প্রতিবার সেখান থেকে কাউন্ট নিয়ে আমরা কাজ করবো O(n) কপ্লেক্সিটিতে

Calculate Summation of GCD(i,n); for i = 1 to n

আমাদের এবারের কাজ হল ১ থেকে n পর্যন্ত সবগুলো সংখ্যার সাথে n এর গ.সা.গু. বের করে তাদের যোগফল বের করা।

শুনতে ব্যাপারটি সহজ মনে হলেও, আসলে ঠিক সহজ না, যদি না আমরা সঠিক এপ্রোচ না জানি। নরমালি আমরা যখন প্রোগ্রামিং এ নতুন, তখন আমরা ১ থেকে n পর্যন্ত লুপ চালায়ে তাদের যোগফল বের করতাম।



এখন কথা হচ্ছে, এভাবে করলে আমরা বড় বড় সংখ্যার জন্য আমরা TLE খাবো। যেমন n = 1000000000 এর জন্য আমাদের প্রচুর সময় লাগবে, ( ইচ্ছে করলে উপরের কোডটি নিজ দায়িত্বে রান করে দেখে নিতে পারো :3 )
এখন তাহলে আমরা কিভাবে এর সমাধান করবো? খেয়াল করলে দেখবো যে, আমরা যখন ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যাগুলোর সাথে n এর গসাগু বের করার চেষ্টা করছি,তখন আসলে আমরা প্রতিবার n এর সবগুলো বিভাজক( all divisor ; there maybe multiple occurance of divisors) নিয়ে তাদের যোগফলটা নিচ্ছি। যেমনঃ  n = 8 হলে, gcd(1,8) + gcd(2,8) + gcd(3,8) + gcd(4,8) + gcd(5,8) + gcd(6,8) + gcd(7,8) + gcd(8,8)  = 1+2+1+4+1+2+1+8 = 20।
এখানে খেয়াল করে দেখি যে, আমরা কিন্তু ১,২,৪,৮ ছাড়া আর কিছু যোগ করছিনা! আর এই সংখ্যাগুলি কিন্তু আসলে ৮ এর বিভাজক (divisor)। আমরা আপাতত গোনায় বাদ রাখলাম কোন সংখ্যা কতবার নিচ্ছি, কিন্তু আসল কথা হচ্ছে আমরা n এর divosr গুলিকেই নিচ্ছি আমাদের ক্যাল্কুলেশন এর জন্য। তাহলে বুঝা যাচ্ছে আমাদের আসলে n এর divisor গুলি বের করতে হবে। আর আমরা O(√n) কমপ্লেক্সিটি তে n এর divisor বের করতে পারি। কাজেই, n = 1000000000 এর জন্য আমরা 31622.77.. কমপ্লেক্সিটিতে divisor গুলি বের করে, এরপরে আমাদের বাকি কাজ করবো।
তাহলে  n = 8 এর জন্য, আমাদের যোগফল অনেকটা এরকম হবে দেখতেঃ

এখানে coef1,coef2... এগুলোই আমাদের বের করতে হবে। divisor গুলি আমরা আগেই পেয়ে গেছি।
১ থেকে n পর্যন্ত সংখ্যাগুলোর সাথে n এর গ.সা.গু. বের করতে গেলে,গ.সা.গু = ১ কতবার আসবে, সেই সংখ্যাটা আসলে n এর অয়লার ফাংশন। অয়লার ফাংশন সম্পর্কে না জানলে এই লিঙ্ক দেখার অনুরোধ রইল আগে।
আচ্ছে এখান থেকে আমরা একটু মনযোগ দেয়ার চেষ্টা করি,

phi (8) = 4.
phi (4) = 2.
phi (2) = 1.
phi (1) = 1.
আমরা এখানে আসলে ৮ এর divisor গুলির phi এর মান দেখলাম।
আচ্ছে এখন দেখা যাক, phi(8) = 4 এর জন্য, কোন কোন জোড়া নিলে আমাদের গসাগু ১ আসছেঃ
(1,8), (3,8), (5,8), (7,8); কাজেই, আমাদের coef1 = 4 হবে।

( coef1*(1); এই 1 এর মানে হচ্ছে, ঐসব জোড়া আমরা নিবো, যাদের মাঝের গ.সা.গু. = 1 হবে, এরকম জোড়া আছে 4 টি, কাজেই আমাদের coef1 = 4 )
এখন আমরা বের করবো coef2 এর মান। কাজেই আমাদের বের করতে হবে এমন কতটি জোড়া আছে, যারা 8 এর সাথে গ.সা.গু.  = 2 হবে। এজন্য আমাদের দরকার phi(8/2) = phi(4) এর মান। আমরা আগেই বের করে রেখেছি, phi(4) = 2. কাজেই আমাদের coef2 = 2. একইভাবে, coef3,coef4 বের করতে পারবো আমরা। ফাইনালি,
coef1 = phi(8/1) = phi(8) = 4. ; divide by first divisor = 1.
coef2 = phi(8/2) = phi(4) = 2. ; divide by second divisor = 2.
coef3 = phi(8/4) = phi(2) = 1. ; divide by third divisor = 4.
coef4 = phi(8/8) = phi(1) = 1. ; divide by forth divisor = 8.


কাজেই, আমাদের ফাইনাল রেজাল্ট ঃ

phi(8/1)*1 + phi(8/2)*2 + phi(8/4)*4 + phi(8/8)*8
= 4*1 + 2*2 + 1*4 + 1*8 = 20 

অ্যালগরিদম (Algorithm)

without pre computing phi values:


এখন আমাদের অনেক কুয়েরি থাকলে আমাদের আগে থেকে phi এর মান বের করে রাখতে হবে। ঐ ব্যাপারটা তোমরা নিজেরা করে দেখো। আবার যদি আমাদের n এর মান অনেক বড় হয়ে যায় যে, আমরা O(√n) এও TLE খাচ্ছি, তাহলে আমাদের number theorem এর অন্যরকম এপ্রোচ নিতে হবে। এগুলো নিয়ে পরে আলোচনা করা যাবে।