Toph Hints

• Toph: XORs
• Toph: Arya and OR
• Toph: Horrible Queries
• Toph: XOR Master
• Toph: Range Product

Toph: XORs

Problem link: XORs

Solution:

We will be given some integers. We are asked to output the cumulative xor sum of all possible pair from those integers; where pair (a[i] ^ a[j]) and 1 <= i, j <= n [i, j = index]

Given the array 1 2 2 4 5, we have to perform our operation like below->

For 1, take all possible pairs:

• (1, 2) = 1 ^ 2 = 3
• (1, 2) = 1 ^ 2 = 3
• (1, 4) = 1 ^ 4 = 5
• (1, 5) = 1 ^ 5 = 4

For 2, take all possible pairs:

• (2, 2) = 2 ^ 2 = 0
• (2, 4) = 2 ^ 4 = 6
• (2, 5) = 2 ^ 5 = 7

For 2, take all possible pairs:

• (2, 4) = 2 ^ 4 = 6
• (2, 5) = 2 ^ 5 = 7

For 4, take all possible pairs

• (4, 5) = 4 ^ 5 = 1

So, we get values: 3, 3, 5, 4, 0, 6, 7, 6, 7, 1 and out output would be
3 ^ 3 ^ 5 ^ 4 ^ 0 ^ 6 ^ 7 ^ 6 ^ 7 ^ 1 = 0

So, how can we solve this? If we try to use bruteforce approach, complexity would be so much and we will surely get TLE in the process.

Let's consider the previous array 1 2 2 4 5, here for 1 we have exactly 4 pairs, for 2(first) we have 3 pairs, for 2(second) we have 2 pairs... for 5 we have no pair. Can you see the pattern here? Well let's talk about it, why the number of pair is important for us.

We know, if we xor an integer odd number of times, it becomes 0 (zero) and for even number of times, it becomes the integer itself. For the 4 pairs of 1, we get the following result by xoring all of the pair for 1 like this: (1^2)^(1^2)^(1^4)^(1^5). We can see, as we have xored odd number of one (1), [1 ^ 1 ^ 1 ^ 1]. We can conclude that it will finally be zero (0). So we don't need this in our calculation. What we need is that the xor of (2^2^4^5). Similarly for 2(first) we get 3 pairs, as we are xoring two 2's, and two is even, so we have to xor 2 with the result. So it will look something like this: 2^(2^4^5).
For second 2, we get (4^5).
For 4, we have one pair (zero xor, as zero is even, we need to xor with 4), Finally we get: (4^5).
For 5, we have no pair, so we don't need to do anything.

I hope now you understand why we need the number of pair. We can get the number of pair simply by (n - index_of_the_element). And for each element, we need the cumulative xor of all the element from index+1 to n of that particular index. We can pre calculate the cumulative xor of all the elements in an array. Remember, we need to pre calculate in reverse order for our purpose.

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:

Dev Skill: Game of MODs

Problem link: Game of MODs

In this problem, we are given an integer n with q queries. Each query we have k integer. We need to calculate the maximum and minimum number can be formed after removing k digits from n. Here the digits won't change their position.

Solution: Some things to observer first.

• If k == size of n (digits), then the answer would be 0 0
• If there are leading zeros, we need to remove them, say we got a number like 000000009. this should be changed to 9.
• If we have only 0 digit, then the answer would be zero

We will use recursion technique for building up our desired result. The idea is that a character among first (k+1) characters must be present in the resultant number. So we pick the first (k+1) smallest or largest depending on the situation. Put it on the result, then recur for remaining characters.
This is done in the legend function below. I used a counter variable for checking whether we are creating maximum or minimum number. Look at line 18 for understanding. Only the change in the index can produce two defferent result. Complexity is O(n), the number of digits. Considering all the cases, queries, complexity would be 100*200*11 = 220000

কম্বিনেশন ( 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) ব্যবহার করে মান বের করবো।

সেট (Set)

সেট (Set)

সেট বলতে আমরা ইউনিক জিনিস বুঝে থাকি। যেমন আমার কাছে অনেকগুলি চকলেট আছে, ২ টি মার্স, ১০ টি স্নিকার্স, ৭ টি কিটক্যাট, ১৮ টি সাফারী। এখন আমি যদি আমার চকলেট এর সেট করতে চাই, তাহলে
s = { Mars, Snikers, Kitkat, Safari };

এখানে কিন্তু কোন চকলেট কতবার আছে তা জানার কোন দরকার নেই। আমার খালি দরকার আমার কাছে ইউনিক কি আছে। সেট এই কাজটা করে। STL এর সেট ভ্যালুগুলিকে ইউনিক আকার এবং একই সাথে সর্টেড আকারেও রাখে।

#include <set>
using namespace std;
int main()
{
        set < int > s;
        s.insert ( 10 );
        s.insert ( 10 );
        s.insert ( 1 );
        s.insert ( 10 );
        s.insert ( 10 );
        s.insert ( 2 );
        s.insert ( 2 );

        // এখানে সেট এ আমরা পাবোঃ 1, 2, 10

        set < int > :: iterator it;                   //সেট এর ভ্যালু পয়েন্ট করার জন্য ইটারেটর ডিক্লার
        for ( it = s.begin(); it != s.end(); it++ )
               cout << *it << endl;                //সেট এর ভ্যালুগুলি প্রিন্ট করলাম

        cout << s.size() << endl;                //সেট এর সাইজ প্রিন্ট করলাম
       
        s.clear();                                         //সেট ক্লিয়ার করে দিলাম
}

ধরি আমাকে অনেকগুলি নম্বর দেয়া হল। আমাকে বলতে হবে এর মধ্যে ইউনিক কতটি নম্বর আছে। এর জন্য আমরা খালি সেট এর মধ্যে ইনসার্ট করতে থাকবো এবং সেট এর সাইজটি প্রিন্ট করে দিবো।

আপার_বাউন্ড এবং লোয়ার_বাউন্ড ( upper_bound & lower_bound )

আপার_বাউন্ড এবং লোয়ার_বাউন্ড(upper_bound & lower_bound)

আপার_বাউন্ড এবং লোয়ার_বাউন্ড খুব গুরুত্বপুর্ণ  একটি টপিক। এখন একটি কাহিনী দেখা যাকঃ
আসিফ এবং আসফি ২ যমজ ভাই। তাদের বয়স ধরি ২১। অর্থাৎ তাদের বিয়ের বয়স হয়েছে। তারা আবার খুব হ্যান্ডসাম এবং একই সাথে ব্রিলিয়ান্ট এবং তাদের আগে কোন ফুল-গার্লফ্রেন্ড, হাফ-গার্লফ্রেন্ড কিছুই ছিলনা। কাজেই তাদের বিয়ে করার কথা শুনে মেয়েরা পাগলপ্রায়। এখন আসিফ এর পছন্দ তার থেকে কম বা তার সমান বয়স্ক মেয়েদের (বউ হিসেবে)। অন্যদিকে আসফি এর পছন্দ তার থেকে বেশি বয়স্ক মেয়েদের। এখন ধরি প্রায় ১০০ জন মেয়ে তাদেরকে বিয়ে করার জন্য আগ্রহী। আমাদের কাজ হবে আসিফ এবং আসফি এর জন্য সঠিক বয়সের পাত্রী খুঁজে বের করা। কিভাবে করবো কাজটা? প্রথমেই আমরা পাত্রীদের কে তাদের বয়সের ক্রমানুসারে কম থেকে বেশি আকারে সাজাই। এই সংখ্যাগুলি ধরে একটি ভেক্টর এর মধ্যে রাখি। ধরি আমাদের ভেক্টরটি দেখতে এরকমঃ

int v [ ] = { 10, 12, 14, 21, 21, 21, 21, 30, 32 };

এখন আমরা এই v ভেক্টর এর উপর লোয়ার_বাউন্ড চালালে পাবো ২১, যা ৩ তম ইনডেক্স। আর আপার_বাউন্ড চালালে পাবো ৩০, যা ২১ থেকে ঠিক বড়।



Output :

lower_bound at position 3
upper_bound at position 6

ভেক্টর এর ইনিশিয়াল এবং এনডিং অ্যাড্রেস এবং কোন ভ্যালুর সাপেক্ষে আমরা বাউন্ড বের করতে চাই এগুলি প্যারামিটার হিসেবে দিতে হবে।

ইটারেটর(Iterator)

ইটারেটর(Iterator)

ইটারেটর আসলে সি এর পয়েন্টার এর মত কাজ করে। পয়েন্টার একটি অ্যাড্রেসকে পয়েন্ট করে থাকে যা থেকে আমরা পরবর্তীতে সেই অ্যাড্রেস এর ডাটা নিয়ে কাজ করতে পারি। সি++ এর ইটারেটর এর কাজ ও ঠিক ওরকম। STL ফাংশনগুলি অনেক ক্ষেত্রে অ্যাড্রেস পাঠায় আমরা যে ডাটাকে খুঁজছি, তা কোথায় আছে তার। ইটারেটর ডিক্লার করে এভাবে-->

vector< int > :: iterator it ;
আমরা ভেক্টর এর একটি ইটারেটর it ডিক্লার করলাম।
এখন ভেক্টর এর সব এলেমেন্ট দেখতে চাইলে আমরা এটা করবো-->

for ( it = v.begin(); it != v.end(); it++ )   // v নামের একটি ইন্টিজার এর ভেক্টর নিলাম।
       cout << *it << endl;                        // *it দিয়ে আমরা it অ্যাড্রেস যাকে পয়েন্ট করে আছে, তার ভ্যালু প্রিন্ট করলাম।

প্রায়োরিটি কিউ (Priority Queue)

প্রায়োরিটি কিউ (Priority Queue)

ঠিক কিউ এর মতই, তবে এর একটি সুন্দর দিক হচ্ছে এটি প্রোগ্রামারের প্রায়োরিটি অনুযায়ী কাজ করে।
ধরি কোন একটি জিনিস নিলামের জন্য ডাকা হল। এখন ক্রেতা অনেক। একেকজন একেক দাম হাঁকছে। ধরলাম ক্রেতা আবির, কালাম, হাসান, মমতাজ যথাক্রমে ১০, ৩০, ১২, ১৪ টাকা দাম ডাকলো। এখন আবির আগে ১০ টাকা ডাকলেও, কালাম কিন্তু ৩০ টাকা ডাকার কারনে তার প্রায়োরিটি বেশি হবে বিক্রেতার কাছে। তাই বিক্রেতা চাবে কালামকে জিনিসটি দিতে। এরপরে কালাম চলে গেলে বেশি প্রায়োরিটি পাবে মমতাজ। প্রায়োরিটি কিউ ঠিক এরকম বিক্রেতার মত আচরন করে। default প্রায়োরিটি কিউ বড় থেকে ছোট ভ্যালু প্রসেস করে। কাজেই এক্ষেত্রে ৩০, ১৪, ১২, ১০ এভাবে ভ্যালুগুলি সাজানো থাকবে কিউতে।
প্রায়োরিটি কিউ এর হেডার ফাইলঃ #include <priority_queue>

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

ম্যাপ ( Map )

ম্যাপ ( Map )

ম্যাপ খুব দরকারি একটি ডাটা স্ট্রাকচার। আমরা অ্যাারে এর কনসেপ্ট থেকে ম্যাপ কে বুঝার চেষ্টা করবো। আমরা অ্যাারে এর ব্যাপার গুলি থেকে যা জানি, অ্যাারে তে 0 থেকে n সংখ্যক কিছু ইনডেক্স থাকে, সেসব ইনডেক্স এ আমরা আমাদের ডাটা টাইপ অনুযায়ী ডাটা রাখি। অতঃপর আমরা অ্যাারে এর ইনডেক্স কে কল করলে, সে ইনডেক্স এ রাখা ডাটা কে খুব সহজে পেয়ে যাই। এটা মোটামুটি অ্যাারে এর ব্যাসিক আইডিয়া। এখন আমরা অ্যাারে এর ইনডেক্স এর জন্য কেবল মাত্র ইন্টিজার নম্বর ব্যবহার করি, অর্থাৎ কোন একটি ইন্টিজার নম্বর এর সাপেক্ষে আমরা ঐ ইনডেক্স এর ভ্যালু পাবো। এক্ষেত্রে এই ইন্টিজার নম্বরগুলি হচ্ছে key or index, আর এরমধ্যে রাখা জিনিসগুলি হচ্ছে value or data.
এখন একটি গল্প দেখা যাক-->

ধরি কোন এক রাজ্যে কোন এক রাজা আছে। রাজার প্রায় ১০০+ বউ আছে, এবং ৩০০+ বাচ্চাকাচ্চাও আছে !! আচ্ছা ব্যাপারটা একটু কেমন দাঁড়ায়। আসলে ইনি রাজা নন, এনাকে আমরা মহারাজা বলবো এখন থেকে :D । তো, মহারাজার নাম হচ্ছে সেন্টিনো। সেন্টিনোর মন্ত্রীর নাম লুসিফার। প্রতি মাসের প্রাইম নম্বর এর দিনগুলিতে মহারাজা সেন্টিনো, লুসিফার এর কাছে তার বউ বাচ্চার খবর জানতে চায়। আসলে খবর বলতে সেন্টিনো খালি জানতে চায় অমুক নামের মানুষটি কি তার বউ? নাকি বাচ্চা? ( অনেক বাচ্চাকাচ্চা, বউ, পাইক - পেয়াদা, সৈন্য সবার নাম, পদবী তার মনে থাকেনা, এজন্য মন্ত্রী মশাইয়ের কাছে উনি একেটটি নাম দিয়ে তার পজিশন জিজ্ঞাসা করেন  :P )। এখন সেন্টিনো খুব বদমেজাজী রাজা। পান থেকে চুন খসলেই গর্দান ফালায়ে দিবে এরকম টাইপ। লুসিফার এর ভয় ,যদি সে উলটাপালটা কোন ইনফরমেশন দেয়, তাহলে তার জীবন ঐদিন ই শেষ :( । তো লুসিফার অন্য এক সাম্রাজ্য থেকে তোমাকে ডেকে নিয়ে আসলো এবং মহারাজার এই ব্যাপারটায় সাহা্য্য করতে বললো। সাহায্য না করলে তোমার গর্দান যাবে বলে হুমকিও দিল। মজার কথা হচ্ছে, তুমি যদি ম্যাপ জানো, তাহলে তোমার জন্য এটা পুরা পান্তা ভাত, আর না জানলে তো গর্দান যাবে বুঝতেই পারছো।

এখন মহারাজা একটি একটি করে নাম বলে, এবং তোমাকে বলতে হবে ঐ নামধারী ব্যাক্তি আসলে মহারাজার কি হয়? বউ? বাচ্চা? নাকি অন্য কিছু। যেমন সেন্টিনো জানতে চাইলো, মর্জিনা আমার কি হয়? উত্তর ঃ বউ। এখন তুমি যদি উত্তর দেও যে মর্জিনা আপনার বাচ্চা হয়, এবং মর্জিনা কে ডেকে আনার পর যখন মহারাজা বুঝবে যে তুমি মিথ্যা বলেছো, তুমি ওইখানেই শেষ। ( ধরি হিসাবের সুবিধার্থে, কোন বাচ্চা, বউ, সৈন্য কারো নামের ডুপ্লিকেট কেউ থাকবে না )।

এখন আসি সমাধানে -->
এখন ম্যাপ জানা থাকলে তুমি একটি নাম কে, আরেকটি নাম দিয়ে রিপ্রেসেন্ট করবে। যেমন এখানে মর্জিনা হচ্ছে key, আর বউ হচ্ছে তার value. এখন মর্জিনা, বউ এগুলা তো স্ট্রিং টাইপ, কাজেই আমরা ম্যাপ এভাবে ডিক্লার করতে পারিঃ
#include <map>
map < string, string > m;
এখানে ম্যাপ আসলে এভাবে থাকে ঃ map < key, value >

তাহলে আমরা m নামের একটি ম্যাপ ডিক্লার করলাম।
এখন আমরা এই ম্যাপ এ ভ্যালু ইনসার্ট করবো।

m [ "Morjina" ] = "Bou";              // এরমানে হচ্ছে, "Morjina" নামের একটি ইনডেক্স এ "Bou" কে ইনসার্ট করলাম।
cout << m [ "Morjina" ] << endl; // এখানে আউটপুট আসবে ঃ "Bou"
আশা করি ব্যাপারটা বুঝে গেছো সবাই। এভাবে আমরা ম্যাপিং এর মাধ্যমে যেকোন ডাটা টাইপ কে যে কোন টাইপ দিয়ে রিপ্রেসেন্ট করতে পারি।

m [ "Sokhina" ] = "Bachcha";
m [ "Anika" ] = "Bou";
m [ "Solayman" ] = "Soldier";
m [ "Lucifer" ] = "Minister";
m [ "Keka Ferdousi" ] = "Radhuni";

এরকম ইনসার্ট করার পরে আমরা মহারাজা সেন্টিনোর কথা অনুযায়ী ম্যাপ থেকে খুব সহজেই ডাটা রিট্রিভ করতে পারবো।
যদি ম্যাপ এর সবকিছু আমরা আগের অবস্থায় আনতে চাই, তাহলে map.clear() লিখলে ম্যাপ একদম empty হয়ে যাবে।

ম্যাপ নিয়ে আপাতত এটুকুই। আরো ডিটেইলস জানতে চাইলে তোমরা গুগল করে শিখে নিলে সেটা ভালো হয়।
মহারাজার আজগুবি কাহিনী পড়ার জন্য ধন্যবাদ :P 

কিউ ( Queue )

কিউ(Queue)

কিউ পুরোপুরি স্ট্যাক এর উলটা। এর কাজ করার সিস্টেম হল ঃ First In First Out ( FIFO ).

আমরা কিউ এর উদাহরন এভাবে দিতে পারি, ধরি আমরা বসুন্ধরায় "ভালোবাসা দিবি কিনা বল" মুভি দেখতে গেলাম। আমরা n সংখ্যক বন্ধু বান্ধব মিলে লাইন এ দাড়ালাম টিকেট কিনার জন্য। এই লাইনটিই কিন্তু একটি কিউ। ধরি আমাদের দাড়ানোর সিরিয়ালটি এরকম ঃ তারেক->আমি->জামি->আহানাফ->ইসলাম।
তাহলে কিউ এর একদম প্রথমে আছে তারেক। যখন ওর টিকেট কিনা হয়ে যাবে, ও সামনে দিয়ে লাইন থেকে বের হয়ে যাবে। প্রোগ্রাম এর ভাষায় একে বলে পপ ( pop() ). তাহলে তারেক পপ হবার পরে কিউ এর সামনে থাকবো এখন আমি। এভাবে যে আগে কিউ তে প্রবেশ করবে, সে আগে বের হবে, এটা হল আসল কথা।

#include<queue>
using namespace std;
int main()
{
        queue <string> q;
        q.push("Tarek");                         // কিউ তে insert এর জন্য push() ফাংশন
        q.push("Shishir");
        q.push("Jami");
        q.push("Ahanaf");
        q.push("Islam");
        while ( !q.empty() )
        {
                 cout << q.front() << endl;  // কিউ এর প্রথম এলেমেন্ট প্রিন্ট করলাম
                 q.pop();                              // কিউ এর প্রথম এলেমেন্ট রিমুভ করলাম
        }
return 0;
}

প্র্যাকটিস এর জন্য কিছু প্রব্লেম ঃ

১। একটি কিউ এ ১ থেকে ১০০ পর্যন্ত নম্বর পুশ কর এবং এর মধ্যে থেকে কেবল মাত্র জোড় সংখ্যাগুলো প্রিন্ট কর।

২। কিউ তে কতগুলি স্ট্রিং পুশ কর এবং তাদেরকে LIFO আকারে প্রিন্ট কর। (using queue, print the values like stack).

স্ট্রিং ( String )

  স্ট্রিং(String)

স্ট্রিং একটি বেশ মজার এবং কাজের ডাটা স্ট্রাকচার। এর কাজ নরমাল ক্যারেক্টার অ্যারে এর মতই, কিন্তু এর ব্যবহার খুব সহজ এবং অনেক কাজ অনেক সহজে করা যায়। স্ট্রিং এর জন্য হেডার ফাইল : #include<string>
একটি কোড দেখা যাক -->

#include<string>
using namespace std;
int main()
{
                string a; // স্ট্রিং টাইপ একটি ভ্যারিয়েবল 'a' ডিক্লার করলাম
                cin >> a; // user থেকে ইনপুট নিলাম
                cout << a << endl; // ইনপুট এর স্ট্রিং প্রিন্ট করলাম
                return 0;
}

স্ট্রিং এর ক্ষেত্রে এভাবে নিয়ে আমরা স্ট্রিং প্রিন্ট করতে পারি। কিন্তু এখানে স্পেস এর পরে কোন ক্যারেক্টার প্রিন্ট হবেনা। তোমরা ইনপুট নিয়ে দেখতে পারো। এরকম ক্ষেত্রে আমরা তাহলে কি করবো? আমাদের দরকার পুরা একটি লাইন ইনপুট নেয়া। এরজন্য ইনপুট নিতে হবে এভাবে-->

getline ( cin, a );

getline() ফাংশন এর কাজ হচ্ছে লাইন শেষ না হওয়া পর্যন্ত ইনপুট নিবে। এখন আমরা স্পেস সহ ইনপুট নিতে পারবো। উপরের কোড এ cin>>a এর বদলে getline (cin,a) লিখে তোমরা ব্যাপারটা দেখতে পারো।

স্ট্রিং এর মজার ব্যাপার হচ্ছে স্ট্রিং কে আরেক স্ট্রিং এ সরাসরি কপি, অ্যাড করা যায়।

string a,b,c;
a = "I eat rice";
b = " and I eat pizza.";
c = a + b;
cout << c << endl;          // এখানে আউটপুট হবে : "I eat rice and I eat pizza"

সুন্দরভাবে concatanation হয়ে গেলো!! সি তে char array নিয়ে করতে গেলে ব্যাপারটা এত সহজ না।

string.size() ফাংশন স্ট্রিং এর সাইজ রিটার্ন করে (integer).
কোন একটি স্ট্রিং কে উলটা করে লিখার জন্য আমরা এভাবে for loop ব্যবহার কতে পারি-->

string a;
cin >> a;
int len = a.size();
string b = "";                 // একটি empty string ডিক্লার করলাম
for ( int i = len-1, pos = 0; i >= 0; i--, pos++ )
b [ pos ] = a [ i ];
cout << b << endl;       // রিভার্স করা স্ট্রিংটি 'b' এর মধ্যে আছে এখন।

সি++ এ আমরা reverse() ফাংশন ব্যবহার করে স্ট্রিং কে কোন লুপ কোড লিখা ছাড়াই রিভার্স করতে পারি এভাবেঃ
reverse ( a.begin(), a.end() );    // a = string variable

স্ট্রিং অনেকগুলি ক্যারেক্টার এর একটি অ্যারে। তাই নরমাল সি এর char array এর মত স্ট্রিং কেও ইনডেক্স অনুযায়ী এক্সেস করা যায়, প্রসেস করা যায়। যেমন, স্ট্রিং a এর 0th ইনডেক্স এর ক্যারেক্টার হবেঃ a [ 0 ]

স্ট্রিং একটি নরমাল ডাটা টাইপ (like int,float,double), কাজেই এটাকে আমরা অন্যান্য ডাটা টাইপ লিখার জন্য যেভাবে লিখি, সেভাবে লিখতে পারবো।
স্ট্রিং এর ভেক্টর: vector < string > string_vec;
স্ট্রিং এর স্ট্যাক: stack < string > string_stack;  এরকম।

স্ট্রিং এর জিনিসগুলি ভালোভাবে রপ্ত করার জন্য তোমরা নিচের সমস্যাগুলি চেষ্টা করতে পারোঃ

১। একটি স্ট্রিং প্যালিন্ড্রম কিনা চেক কর।
example :
hello -> not palindrome
1234321 -> palindrome
wecanacwe ->not palindrome

২। একটি স্ট্রিং দেয়া হবে। যেখানে কেবলমাত্র 0 এবং 1থাকবে। একে ডেসিমাল ভ্যালুতে প্রকাশ কর
example :
00000010 -> the decimal value is 2
111 -> the decimal value is 7

৩। একটি স্ট্রিং এ মোট কতটি ওয়ার্ড আছে এবং কিকি লিখ।
example :
Hello, how are you ?
--> there are 4 words. They are : Hello, how, are, you.

স্ট্যাক ( Stack )

স্ট্যাক (stack)

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

এটি ই স্ট্যাক এর মূল বৈশিষ্ট। একে আমরা বলি “Last In First Out” বা সংক্ষেপে “LIFO”.
এই জিনিসটাকে বলে স্ট্যাক। মানে আমরা সবার পরে যাকে প্রসেসিং করতে ঢুকাচ্ছি তাকে যদি আগে প্রসেসিং করি তাহলে সেটাই স্ট্যাক। STL এ স্ট্যাক ব্যবহার করতে হয় এভাবে,

#include <stack>
using namespace std;
int main()
{
        stack s;  //  একটি ইন্টিজার এর স্ট্যাক
        s.push( 10 );
        s.push( 20 );
        s.push( 30 );
}
/* 10, 20, 30 কে স্ট্যাক এ পুশ করলাম। এখন আমার স্ট্যাক টা দেখতে হবে অনেকটা এরকম
30 // top value of the stack (LIFO)
20
10
*/অর্থাৎ স্ট্যাক এ এখন ৩ টি ভ্যালু আছে।

তাই, স্ট্যাক এর সাইজ হবে ৩।  s.size() এর মাধ্যমে আমরা স্ট্যাক এর সাইজ জানতে পারি।

এখন আমরা স্ট্যাক এর টপ ভ্যালু দেখতে চাইলে যে ফাংশন ব্যবহার করবো তাহলো top() ফাংশন।

int x = s.top();    // x এর মধ্যে স্ট্যাক এর টপ (30) ভ্যালু আছে
cout << x << endl; // x = 30;

এখন যদি আমরা পরের ভ্যালু দেখতে চাই, তাহলে আমাদের আগে টপ এর ভ্যালু কে মুছে ফেলতে হবে। মুছে ফেলার জন্য আমরা ব্যবহার করবো pop() ফাংশন।

s.pop();       // স্ট্যাক এর টপ টাকে ডিলেট করে ফেললাম।
এখন আমার স্ট্যাক এর টপ ভ্যালু হবে 20.

আরেকটা গুরুত্বপুর্ণ ফাংশন হলো empty()
এর কাজ হল স্ট্যাক টা খালি (NULL) আছে কিনা তা চেক করা।

একটি কোড দেখা যাক,

while( !s.empty() )
{
        cout<< s.top() <<endl; // printing the top element;
        s.pop(); // removing the top element;
}
// যতক্ষন স্ট্যাক টা নাল না হবে, ততক্ষন স্ট্যাক এর এলেমেন্ট গুলি প্রিন্ট করলাম

স্ট্যাক দিয়ে আমরা অনেকরকম প্রব্লেম সল্ভ করতে পারি। এর মধ্যে ব্র্যাকেট ম্যাচিং (Bracket Matching or Paranthesis Matching) উল্লেখযোগ্য। তোমরা এগুলো একটু ঘাটাঘাটি করে দেখতে পারো। paranthesis matching নিয়ে পরে কোন এক পোস্ট এ কিছু লিখবো।

ভেক্টর ( Vector )

STL

সি++ এ বিশাল একটি লাইব্রেরী আছে, যার কোডগুলো যেকোন ধরণের ডাটার জন্য কাজ করতে পারে। এই টেম্প্লেট লাইব্রেরীর সবচেয়ে স্ট্যান্ডার্ড ভার্শনটার নামই স্ট্যান্ডার্ড টেম্প্লেট লাইব্রেরী, ওরফে STL।
STL হল একটা বেশ বড়সড় একটা লাইব্রেরী। আমাদের শুধু জানতে হবে সেটা আমরা কিভাবে ব্যবহার করবো। এখন আমরা কিছু STL নিয়ে আলোচনা করবো।

ভেক্টর (vector)

মাঝে মাঝে আমাদের এমন কিছু দরকার হয় যেখানে সাড়ি থাকবে n সংখ্যক, প্রতি সাড়ি তে আবার m সংখ্যক কলাম ও থাকবে। এখানে n,m <= 10000. এবং বলা আছে, কোন কোন সাড়ি তে আবার কলাম নাও থাকতে পারে, মানে ব্যাপারটা এভাবে চিন্তা করলে দেখা যায়, এমন সাড়ি থাকতে পারে যেখানে 10000 এর মতন কলাম আছে, আবার এমন সাড়িও থাকতে পারে যেখানে অনেক কম কলাম আছে। 10000 টা সাড়ি থাকতে পারে যার প্রতিটি মাত্র 5-6 টি কলাম নিয়ে আছে।আর বলা আছে, সাড়ি এবং কলাম মিলে 1000000 এর বেশি কোন ভ্যালু নেই। এখন কথা হল, আমরা যদি এরকম একটা scenario কল্পনা করি তাহলে আমরা 2D (Dimensional ) অ্যারে এর কথা ভাবতে পারি এভাবে,

int a[10000][10000]; // ইনটিজার টাইপ এর একটি অ্যারে, a
এটা কিন্তু বেশ বড়সড় একটা অ্যারে। আমার কম্পিউটার মাথা ঘুরে পড়ে যাবে তাকে এই পরিমান মেমরি অ্যালোকেট করতে বললে, কিন্তু আমার আসলে এত বেশি জায়গা লাগছে না, কারন আমাকে বলেই দেয়া হয়েছে ডাটা সবমিলে সর্বোচ্চ 1000000 টা থাকতে পারে। এধরণের সময়, আমরা ডাইনামিক মেমরি অ্যালোকেট করি - ঠিক যতটুকু মেমরি দরকার ঠিক ততটুকুই নেই। যেটা ম্যানুয়ালি করা বেশ কষ্টকর, আর সেটায় মেমরি পরিষ্কারও করে দিতে হয় কাজ শেষে, নইলে সব ডাটা জমতে জমতে কম্পিউটারের crash করার সম্ভাবনা প্রায় ৮৫% (:P)।
ভেক্টর হলো একটা অ্যারে, যেটায় ডাইনামিকালি জিনিসপাতি ঢুকিয়ে রাখা যায়। মানে, এটাও একটা অ্যারে, কিন্তু সেটা ঠিক ততটুকু মেমরি খায়, যতটুকু খাওয়া লাগে।

ভেক্টর এর হেডার ফাইল ঃ #include<vector>
ভেক্টর ডিক্লেয়ার করে এভাবেঃ  vector< int > a;

যদি অন্য কোন টাইপের ডাটা নিতে চাই তাইলে int এর জায়গায় সেই ডাটার নাম লিখতে হবে। যেমন এটা আরো কিছু অ্যারে।
vector< double > hash;
vector< long long > balti;
vector< char > cow;
vector< float > dalim;

ভেক্টরে কোন ডাটা রাখতে হলে, সেই ভেক্টরের শেষে ডাটাটাকে পুশ করতে হয়।
a.push_back( 100 );       // push_back() function
আর ভেক্টরে কয়টা ডাটা আছে সেটা আমরা জানতে পারি .size() ফাংশনকে কল করে। যেমন আমি একটা ভেক্টরে কিছু ইন্টেজার ঢুকাবো, তারপর সবাইকে প্রিন্ট করবো, সেটার কোড হবে এরকমঃ

int main() {
vector< int > v;
v.push_back( 1 );
v.push_back( 2 );
v.push_back( 3 );
v.push_back( 4 );
for( int i = 0; i < v.size(); i++ )
cout << v[i] << endl;
return 0;
}

বাকি সব কিছুতে ভেক্টরকে সাধারণ অ্যারের মত ব্যবহার করা যায়। যেমন আমি 0th এলিমেন্টটা পাল্টে দিতে পারি v[0] = 10000 লিখে। আরেকটা সুবিধা হচ্ছে আমরা অ্যারেতে সরাসরি কপি করতে পারি না । কিন্তু ভেক্টরে সেটা করা যায়ঃ

int main() {
vector< int > v, cp;
v.push_back( 1 );
v.push_back( 2 );
v.push_back( 3 );
v.push_back( 4 );
cp = v; // copying
for( int i = 0; i < cp.size();  i++ )
cout << cp[i] << endl;
return 0;
}

ভেক্টরে যদি আমি 2D ডাটা রাখতে চাই তাহলে সেটা দুভাবে করা যায়
vector< int > v[100];
vector< vector< int > > v;

প্রথমটি বেশি preferable, তবে এখানে  row  ১০০ টাই থাকবে,আমি ১ টি row ব্যবহার করলেও প্রোগ্রাম ১০০ টার জন্য জায়গা নিয়ে রাখবে।
পরেরটির কলাম ও ডাইনামিকালি চেঞ্জ করা যাবে।
* vector< vector< int >> v; এভাবে লিখলে >> এর জন্য কিছু কম্পাইলর কিন্তু এরর দিবে।
তাই সাবধানতা অবলম্বন করে spacing ব্যবহার করা ভালো।

সমস্যা

১. ১০ থেকে ১০০০০ এর মাঝের সকল বেজোড় সংখ্যা ভেক্টরের মাঝে নিয়ে প্রিন্ট কর।
২. N সংখ্যক ইন্টিজার এবং k একটি সংখ্যা দেয়া হবে। তোমাকে বলতে হবে k সংখ্যাটি N সংখ্যক                 ইন্টিজার এর মাঝে কতবার আছে?
৩. N সংখ্যক ইন্টিজার কে ছোট থেকে বড় আকারে প্রিন্ট কর।
৪. N সংখ্যক ইন্টিজার দেয়া হবে। প্রতিটি ইন্টিজার কতবার করে আছে (ascending order) প্রিন্ট কর।
Input :
6
10 10 2 3 2 8
Output :
2 is 2 times.
3 is 1 times.
8 is 1 times.
10 is 2 times.

CodeChef: February Long Challange 2018

Chef And His Characters: Given a string, we need to find four contiguous characters that can make a string "chef". We need to print how many four contiguous characters ('c','e','f','h') we found. If we found any simply write "lovely (the number of contiguous four characters we found)" else print "normal" without the quotes.

Solution:  The easiest problem of the set. Simply bruteforce through the string from 0 to length-4 and each time see if four contiguous characters are found or not. If found, increase the counter. Finally output the result.

Chef and The Patents: Given N patents we need to complete all of them in M months with K workers. Also each worker can work only one patent at most, that is, if we use a worker for a patent, we can't use him anymore. Every single patent needs exactly one month to finish. And we are also given X, that is at most X workers can work in a month. We are finally given a string of length K denoting the workers. On odd month, workers with character 'O' can work and on even month, worker with character 'E' can work.

Solution: It's a greedy problem. Some key things to notice:

• Worker can work only one month (after working one month, current worker would no longer be available).
• Restriction in odd and even month.
• At most X workers can work on a single month.

We just need to calculate for each month, how many workers can be used to finish how many patents. As a single worker can finish single patent at a time and there is a restriction of even and odd month, we will simply iterate through all the months from 1 to M. Then for each month, we will select minimum(number of workers, X). This is the value of the number of patents we can get in a month. In odd month, the number of worker should be the number of 'O' in the string. Similarly for even month the number of workers would be the number of 'E' in the string. Every time we get minimum workers, we will discard that number from that particular type of worker as a worker can at most work 1 month, so he won't be available after he has done his part. We will store the value every time we count how many workers can work in every month, then simply check if the value is >= N or not. If >= N, then 'yes', else 'no'

Permutation and Palindrome: Given a string, we need to make that string a palindrome re-arranging it's characters and output the indices of those characters that made the palindrome string.

Solution: It's a greedy implementation problem. Some key things to notice:

• If the string length is even and at least one character has odd frequency, we can't make it a palindrome. ex: "aacb"; Here, 'c' and 'b' has frequency = 1, which is odd, and the string length is 4, which is even, so no palindrome can be made.
• If the string length is odd and at least two character has odd frequency, we can't make it a palindrome. ex: "acccb"; Here, 'a', 'b' and 'c' has frequency 1, 1 and 3 respectively, which is odd and the string length is odd. So we can't make a palindrome.

Now how to make the palindrome. We can simply check all the frequency of the characters. If frequency is even, then we will take first half of the position (index) in our first vector, say X.
And second half will go to vector Y. For even length, we won't have any odd frequency, so we will simply reverse Y and then merge it with X to get final output. For odd we need to get the odd element's index first. let's see for even length:

string = "abababab"
We will push the indices accordingly in a vector containing frequency of each character. So,

vector['a'] = 1 3 5 7
vector['b'] = 2 4 6 8

Now, we will iterate through the character's frequency. For 'a'
The first half will go to vector X, and second half will go to vector Y. So.
X = 1 3
Y = 5 7
Now, for 'b', similarly
X = 1 3 2 4
Y = 5 7 6 8

Now, reverse the Y and merge it with X to get the final result.
Final = 1 3 2 4 8 6 7 5

If we observe the indices, we can make this: "aabbbbaa"; which is a palindrome.}

Similarly, we can make this for odd length. There will be one character with odd frequency. we will take first index of that character from our vector[] array, then everything else follows exactly same.
Before merging Y with X, we need to push that odd frequency index to X first.

Car-pal Tunnel: In this problem we are given N tunnels and each consecutive tunnel has D meter distance. There are C cars each having same velocity S meter per second.

Each tunnel has a toll booth that takes Ai second to process a single car. At the time of processing one car, no car can come to that booth for processing. All the tunnels are linearly connected via these toll booths. We need to calculate the delay time between the first and last car after all of them is processed by all the toll booths.

Solution:

After a bit of observation, we will see that, the maximum time of a toll booth will be the distance between any two cars. So if there are C cars, then the answer will simply be (C-1)*maximum (Ai). Let’s see this case:

3
5 15 8
2 3 1

Here, 3 toll booth which have 5,15,8 second to process each car respectively. We have 2 cars each having velocity 1 meter per second. Each tunnel has 3 meter distance. So for a single car to cross a tunnel, it needs 3/1 = 3 second. Now let’s see, when the first car is being processed at the first booth, after 5 second, it will go out from the booth and second car will start processing. 

• 1 second goes, first car moves 1 meter, second car’s process time is also 1 sec.
• 2 second goes, first car goes 1 meter, second car’s process is 2 second.
• 3 second goes, first car is now at second booth for processing, second car’s 3 sec processing time is finished at first booth.

 So the distance between two cars will be 3 second.

Now, after 4,5,6 second, the second car will arrive at the second booth, but the first car is still being processed at that booth. So the second car will stop there. So our delay is now updated to 15 second,
as we clearly know, after processing of the first car (which will take 15 second for 2^nd booth) only then the second car can start processing. So the distance between them will be then 15 second. So the answer is 15*(2-1) = 15; [15 is the maximum toll booth time for a particular booth].

This observation is correct when C is equals to two. If there are more cars, then we need to keep the distance is calculation too. The delay is D/S for every car that takes D/S second to pass D meter distance. But if we happen to come to any case where D/S is greater than maximum of toll booth time, then we need to take the maximum (D/S, toll booth time). Notice this is applicable when there are cars more than two. If only two car is present, then maximum of toll booth is the correct solution.

LightOJ: Points in Rectangle

Problem link: loj 1266

Technique: Binary Indexed Tree

If you don't know about Binary Indexed Tree, first learn it. You can also check BIT here BIT

Given two types of query,

• 0 x y: we got a new point at co-ordinate (x,y) [ if already a point exist in the same co-ordinate, this query does nothing ] 
• 1 x1 y1 x2 y2: we are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x1 < x2, y1 < y2).

We will maintain a 2-D BIT(Binary Indexed Tree) to solve this problem. For query 0 x y, we will call update function each time we got a new point (x,y). For the second query, we will call out query_sum function with parameter (x,y); it means we will get the sum of the rectangle that's lower left co-ordinate is (1,1) and upper right co-ordinate is (x,y). Let's see a testcase:

1
4
0 1 1
0 2 6
1 1 1 6 6
1 2 2 5 5

We got two points (1,1) and (2,6), let's plot these points:

Now let's see the first query, we have to find how many points are inside (1,1) and (6,6). We will call out query_sum function with parameter (6,6), And this will cover the whole area from (1,1) to (6,6) and we will get output = 2
Ok, for the second query we need to find points inside (2,2) and (5,5). We will call our query_sum function with (5,5) and the selected area would be like this:

But we have some extra area here as our query starts from (2,2). So we need to remove those extra area. Basically we need to calculate our desired area as follow:

area = query_sum(x2,y2)-query_sum(x1-1,y2-1)-query_sum(x2-1,y1-1)+query_sum(x1-1,y1-1)

Let's see how does it look, Here:

A = query_sum(x2,y2)

B = query_sum(x1-1,y2-1)

C = query_sum(x2-1,y1-1)

D = query_sum(x1-1,y1-1)

     

 

We added D because, while subtracting B and C, D got subtracted twice. So we need to balance it by adding. Hope you understand what we need to do here.

Code:

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

Akash and GCD 1

Problem link: Akash_gcd_1

We need to perform query based on given function F, that

F(x) = GCD(1, x) + GCD(2, x) + ..... + GCD(x, x)
Where GCD is the Greatest Common Divisor
Now in the problem, given an array A of size N, there are 2 types of queries:

1. C X Y: Compute the value of F(A[X]) + F(A[X+1]) + F(A[X+2]) + .... + F(A[Y]) (mod 10^9+7)
2. U X Y: Update the element of A[X] = Y

Solution:

At first we need to pre compute the value of F(x). Also we need help of Euler's Totient Function for this purpose. You can learn Euler Totient from here: Euler's Totient
Also we need to compute summation of GCD(i,n) for i = 1 to n. If you don't know how to do that, see here: GCD summation

This problem can be solved by segment tree. But as we only need prefix sum and simple update query, we can also solve it using binary indexed tree. As binary indexed tree is easy to code and simple, it's preferable.

Code:

Notice at line 86, the computed value might go negative less than 10^9+7. So we used a while loop to check while the value is below zero, we will add the mod value to make it positive. If we checked the negative value mod in the qeury function, this wouldn't be necessary.

OpenGL: National Parliament of Bangladesh 3D Model

In my final year Graphics Lab, I implemented a 3D model of National Parliament of Bangladesh using OpenGL.

If you don't have glut installed in your codeblocks, then see this link :OpenGL installation


Features:

• Day-night mode ( press 'n' OR 'N' )
• Intensity changing ( press 'i' )
• Fog mode ( press mouse right and left key )
• Sun-moon show ( press 's' OR 'S' OR 'm' OR 'M' )
• Light mode ( press 'l' )
• Zoom mode ( press 'z' to zoom, 'x' to unzoom )
• Text show ( press 't' to show text: "National Parliament of Bangladesh" )
• Rotation mode ( press 'e' OR 'E' , 'r' OR 'R' to rotate camera )
• Up-down mode ( press 'd' OR 'D' to down the camera, 'u' OR 'U' to uplift it )
• Arrow keys to roam freely

Special Features:

• Water flowing done by addinng 10 different images of a sample water flow. I used timer funtion to update the images (texture) and show them in output. Then it seems like the water is really moving
• Same thing goes for flag moving
• Also I used same technique to move trees [ though it doesn't look so good :( ]

Snapshots:

It's just a sample 3D model I implemented. Though it's really tough using OpenGL to draw as realistic as you want, but it is still fun to code :)
Here is the github link to the project. You can take a peek if you like.

link: https://github.com/sifatshishir/National-Parliament-3D-using-OpenGL

If you have problems running the project, you can follow these steps:

• 1) create a project on codeblocks. 
• 2) add all the header files and corresponding .cpp files, and non coding files such as .bmp, .bin, .txt and so on.
• 3) Copy the texture code from main and bring to your project main.
• 4) Run.
• 5) If it works, good. else, go to 6
• 6) left click on the project folder name which will on the left side under the project tab. click add files and select all of the files in 2.
• 7) select in both debug and release and save.
• 8) If it runs, good, else, go to 9.
• 9) go to the project, then properties. from there, go to build target.
• 10) change the execution working dir to your folder/bin/debug
• 11) run
• 12) if it works, fantastic, or else to go 13
• 13) copy the .bmp .txt. bin files (non coding files) and place in your folder/bin/debug. delete all the .o from your folder/obj/debug and copy the .bmp .txt. bin files (non coding files).
• 14) run

Toph: Range Product

Problem link: Range Product

Solution:

Given N and K, we have to find how many integers of K subarray has maximum product which starting index of the subarray is minimum. Also all the integers will be power of 2.
So, at first we will store the power of all the integers in an array. Then we will simply use brute force to check for maximum subarray summation (As we took only power, so we will check for summation here).

Why we took the power? Why we didn't simply multiply? As the multiplication's value will be far greater than long long in C++ data type, we simply can't do that. Also in the problem description there is no mention about modulo operator, so we definitely can't multiply. So we took out the power of 2's and add them to get our maximum muliplication subarray.

Toph: XOR Master

Problem link: XOR Master

Solution:

In this problem we are given N integers. We have to count the number of pairs (i,j) (1<=i<=j<=N) for which A[i] XOR A[j] will contain at least 1 in it's bit pattern.

Say for the case here:
4
1 2 2 2

Here are 3 such pair that A[i] XOR A[j] has at least one 1 in it's bit pattern. They are:

1 XOR 2 = 01(Binary of 1) XOR 10(Binary of 2) = 11 (has two '1's) ; for three 2's, and a single 1, we get 3 such pair of (1,2)

But as we can see, 2 XOR 2 = 10 XOR 10 = 00, here no '1' is present. So this will not be counted.

So, how can we solve this? Firstly, see that one integer can get at least one '1' in it's bit pattern if it is XOR-ed with any integers except itself. So, a simple binary search with upper_bound technique can be really helpful to find solution in O(log N). For frequent values, we can store them in a map data structure that is built in C++ function.

Toph: Horrible Queries

Problem link: Horrible Queries

Solution:

In this problem, we will be given some integers from 1 to 50. And also integer L,R,K. We need to find how many unique values have at least K occurence in the subarray between L & R, where L<= R.
As numbers can only be between 1 to 50, we can implement this simply without the use of segment tree. What we need to do is that, we will create 50 array of size N (each for 1 to 50 integers) to compute the occurence of every integers in a cumulative way. Then for each query, we will simply check for every integers if cumulative sum (occurence of that integer) of that integer in given range is at least K or not. Then we will simply increase the counter to get our answer. Try to implement it any way you like keeping in mind about the cumulative frequency of occurance. Then you can check my code below.

Toph: Arya and OR

Problem link: Arya and OR

Solution: 

Firstly, the maximum value we could get is the largest element of the array. So we will sort the array. Then our maximum value could get greater by doing OR ( | ) with other elements of the array. So in that case, what we will do is that, each time we will make bitwise OR with the largest element of the array with other elements in descending order. So, gradually, we will get values after everytime we OR them. If our current value is greater than our maximum value, then we will simply update the maximum value.

As there is a term "arbitrary group of numbers"
Arbitrary group should mean any group possible from the whole array, and in that case the bitwise or of the whole array is always the maximum answer

**ps: We don't even need sorting for this problem. Simply compute OR of all the numbers.

Code:

Codeforces Round #460 (Div. 2)

• Supermarket

Find the minimum value of (a/b) for every n supermarkets. This will be considered as unit value of one kilo apple. Then simply multiply m with minimum(a/b) to get the answer.

• Perfect Number

If we observe carefully, there is a pattern. From 19, every 9-th number should be a Perfect Number according to the statement. But we will also check their digit sum each time whether they match 10 or not. If they match 10, then we will increase our counter.

• Seat Arrangements

First we will find how many different combination in row-wise. If we get '.' in any position of the grid, we will simply check next + k - 1  row for our answer. If row+k-1 >= n, there is no combination. Same thing goes for column as well. Else we will increase our counter.
The legendary hack case for this problem is this:

2 2 1
..
..

If we do according to our approach, there will be overlapping while counting row wise and column wise. So we need to check, if k == 1 or not. If k == 1, then the answer will be summation/2, as we counted each position twice.

A client server multichat program for network programming

This was like my 4th year's network programming lab's project. The main task is to create a server that will help some clients to make communication with each other, like any social media services like Facebook, Whatsapp, Messenger etc.

Software Used: XAMPP server, NetBeans IDE.

Codes, sql files are given in the folder. Create a database in XAMPP named multichat. Then import the sql file. These are the instructions for the program: 

• 1. Type 'create User_name Password' to create an account 
• 2. Type 'login User_name Password' to login your account
• 3. Type 'logout' to logout from your account 
• 4. Type 'joinchatroom Chat_room_name' to join a chatroom 
• 5. Type 'leavechatroom' to leave from your current chatroom
• 6. Type 'showchatroom' to show all available chat rooms 
• 7. Type 'showuser' to show all logged in user available
• 8. Type 'showfriend' to show your friend list 
• 9. Type 'showrequest' to show your pending friend request 
• 10. Type 'connect Friend_name' to send friend request to your friend
• 11. Type 'yes Friend_name' to accept a friend request 
• 12. Type 'no Friend_name' to reject a friend request 
• 13. Type 'message Friend_name Message' to send private message to your friend 
• 14. Type anything else besides these commands to chat with your friends :)

At first, run the Xampp and start apache and sql connection, then run the server.java in the server project and after that we can run client.java as many ( I set at most 50 user ) times to create new client that can communicate.

Snapshots of the project

Firstly we will create a user using ‘create’ command like this:

Be careful about spacing. Ok, now login part:

The username is incorrect. Same thing goes for incorrect password too.

Now we are logged in. All the other commands are similar like this. Commands: 

• 1. create: creates an user account in the database. 
• 2. login: login command requires three space separated strings. If not found three strings, then it will show invalid command in the console. If the user is already logged in, then it will also show already logged in. Else command will check username and password from client table in the database and the user will be online. 
• 3. logout: logout will sign out the user from the program.
• 4. joinchatroom: The user will be able to join a chat room using this command as follows:

**If there are already people in a chat room, and they are online; if then a person joins that chat room, every other members of that room (currently logged in) will receive a message to welcome the new user 

• 5. leavechatroom: User can leave his chat room. User can enter another chat room using joinchatroom command. If he is already in a chat room, then he will automatically be removed from previous room. Basically, a user can be inside one chat room at a time.
• 6. showchatroom: This will show how many chat rooms are currently available which has at least one member. If there is no member in a chat room, that room will be deleted.

• 7. showuser: Show all currently logged in user.

• 8. showfriend: It will show the user’s friend list.

• 9. showrequest: This will show pending friend request. 
• 10. connect: Send a friend request to a user. If user doesn’t exist in the database, then it will show incorrect user.

** Also case like: sending friend request to own self, sending request to user that already been sent etc are also handled, Try typing command like these to check. 

Ok, now if Sifat logs in, then he will automatically see pending requests from different users.

• 11. yes & no: If Sifat type yes aladin, then he and aladin will become friend. If types no aladin, then aladin’s request will be rejected and aladin will be notified via a message. If aladin is not online, then the message will be pending, else aladin will receive rejection instantly.

• 12. message: Type message aladin to send aladin a private message.

As aladin doesn’t have friend named Sifat, so private message won’t be possible. So let’s make friends:

Now, both of them can share private message. Suppose, aladin sent a message to Sifat. If Sifat is online, he will receive the message. If Sifat is offline, the message will be stored as pending message. When Sifat will log in, he will then receive all the pending messages from different users.

**If user is not in any chat room, all of his messages will be global, an everyone who are logged in globally will receive that message(Broadcast). Private message between friends is Unicast and inside chat room, messages will be counted as multicast (only user in the chat room will receive messages).

You can find my project here: https://github.com/sifatshishir/Client-Server-Multichat