বাইনারি ইন্ডেক্সড ট্রি অথবা ফেনউইক ট্রি ( 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

স্লাইডিং উইন্ডো (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)

UVA 11254: Consecutive Integers

Prob link: UVA 11254: Consecutive Integers

Problem টায় বলা হয়েছে আমাকে একটা integer দেয়া হবে, আমাকে ঐ integer টি আরো কতোগুলি consecutive integer এর summation এর মাধ্যমে বানানো যায় তা print করতে হবে।
Suppose 15 কে আমরা লিখতে পারি এভাবে ------>

15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
15 = 15

দেখা যাচ্ছে যে এর মধ্যে প্রথম টির integer সংখ্যা বেশি, তাই আমাকে প্রথম টি ই print করা লাগবে।print করার জন্যে question এ যে format এর কথা বলা হয়েছে, সে অনুযায়ী print করলে আমাদের output হবে এরকম  :::
15 = 1 + ... + 5  ( অর্থাৎ আমাকে consecutive integers এর  first এবং last integer টা print করতে হবে )
যদি এমন integer হয়, যাকে কোন consecutive integer এর summation এ ফেলা যায় না, তখন কেবল ঐ integer টাই print হবে।
Ex : For N = 8  ans   ===   8 = 8 + ... + 8

Solve Technique:

আমরা sum of arithmetic progression সম্পর্কে নিশ্চই জানি।
যদি n তম integer পর্যন্ত summation বের করতে হয়, তাহলে সূত্র ঃ sum, Sn ( n terms ) = n / 2 + [ 2 * a + ( n - 1 ) * d ]
যেখানে , a = first term , n = last term , d = interval between numbers .
আমরা এই সূত্র ব্যবহার করে আমাদের উত্তর বের করবো।
যেহেতু আমাদের বলা আছে , consecutive integers, so আমাদের d এর মান হবে  one  ( 1 ) .
এখন আমাদের n জানা আছে, আমরা চাইলে brute force করে করতে পারি,  কিন্তু আমাদের range টাকে ( 10 ^ 9 ) মাথায় রাখতে হবে।
এতবড় জিনিস বারবার loop চালায়ে করলে TLE  ( Time Limit Exceeded ) খাওয়ার সম্ভাবনা অনেক বেশি, তাই আমরা আমাদের সূত্র ব্যবহার করে একটা ফরমুলা বানানোর চেষ্টা করবো যাতে আমাদের brute force এর time complexity কম হয়।
সূত্র টাকে আরেকভাবে লিখা যাক,  a = ( 2 * Sn + n - n * n ) / ( 2 * n )
হিসাবের সুবিধার জন্য আমরা এভাবে লিখলাম, এখন খেয়াল করে দেখো আমাদের জানা মান হল Sn , যা qs এ দেয়া থাকবে, আমাদের বের করতে হবে a এবং n । আমরা ২ টা কাজ করতে পারি, প্রতি a  এর জন্য লুপ চালায়ে n বের করতে পারি, অথবা উলটা কাজটাও করতে পারি।

এখন কথা হল লুপ চালাবো কতক্ষন ?
equation খেয়াল করলে দেখা যায় আমাদের R.H.S এ আছে 2 * Sn , আমরা square root of 2 * Sn থেকে 1 পর্যন্ত integer এর উপর লুপ চালায়ে n  এর মান বের করতে পারি এবং n  এর মান আমরা equation এ বসায়ে  a এর মান এর validity check করতে পারি।যখন ই আমরা valid একটা মান পাবো তখন আমাদের result এর a হবে
equation থেকে প্রাপ্ত মান এবং n হবে   a + ( যেই মান এর জন্য আমরা valid a পেলাম সেই মান) - 1 ।

Qs 1 : Why sqrt ( 2 * Sn )  ?

Ans : equation থেকে এটা easily observe করা যায়, n * n এই value টার আগে minus sign আছে, কাজেই, আমার  n এর মান sqrt ( 2 * Sn ) এর বেশি হলে negative integer আসবে , যা আসলে ভুল result দিবে।

Qs 2 : a এর validity check করবো কিভাবে ?

Ans : আমরা a = ( 2 * Sn + n - n * n ) / ( 2 * n )  এই সূত্র টা কাজে লাগাবো, sqrt ( 2 * Sn ) থেকে 1 পর্যন্ত লুপ চালায়ে আমরা প্রতি n এর জন্য  a এর মান এর validity দেখবো। a valid হবে তখনই যখন আমার equation এ n এবং Sn বসালে তা সত্য হবে।

a = ( 2 * Sn + n - n * n )  এটা থেকে আমরা একটা মান পাবো, এখন কখন এই মানটা সত্য? যখন a কে  ( 2 * n ) দিয়ে মড করলে মান শুন্য আসবে, কেবলমাত্র তখনই আমরা a এর একটা integer value পাবো এবং value টা হবে ( 2 * Sn + n - n * n ) / ( 2 * n ).