Saturday, April 14, 2018
Saturday, March 31, 2018
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:
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.
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
- (2, 2) = 2 ^ 2 = 0
- (2, 4) = 2 ^ 4 = 6
- (2, 5) = 2 ^ 5 = 7
- (2, 4) = 2 ^ 4 = 6
- (2, 5) = 2 ^ 5 = 7
- (4, 5) = 4 ^ 5 = 1
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.
Wednesday, February 21, 2018
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 AB % C.
Solution: We can calculate it by using modular arithmetic. We know
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:
In this problem, we are given three integers A, B, C; we need to calculate AB % 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)
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:
Tuesday, February 20, 2018
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.
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
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
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
Sunday, February 18, 2018
কম্বিনেশন ( Combination )
কোন বড় গ্রুপ থেকে কিছু সংখ্যক জিনিস নিয়ে ছোট ছোট গ্রুপে ভাগ করাই হল কম্বিনেশন। এখানে পারমুটেশন এর মত অর্ডার এর কোন প্রভাব থাকেনা। যেমনঃ ৩ টি জিনিস থেকে আমরা ২ টি জিনিস নিতে পারি এভাবেঃ
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।
অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)
(x + y)0 = 1
(x + y)1 = x + y
আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) n
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ
এখন কো-এফিশিয়েন্টগুলি হবেঃ 1 4 6 4 1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ
(x + y)n = (nC0)(xny0) + (nC1)(xn-11y1) + (nC2)(xn-22y2) + ... + (nCn)(x0yn); [nCk = combnation of k element from n or n choose k]
আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ
কিন্তু এভাবে আমরা সর্বোচ্চ ২১-২২ ফ্যাক্টরিয়াল পর্যন্ত হিসাবে করতে পারবো। এর চেয়ে বেশি আমরা সি++ এ করতে গেলে আমাদের বিগ-ইন্টিজার লাইব্রেরি ব্যবহার করতে হবে। তবে পাইথন এ আমরা হিসাব করতে পারবো এবং এই হিসাবের কমপ্লেক্সিটি হল O(n).
আমরা বড় বড় কম্বিনেশন এর জন্য, nCk mod m এরকম কিছু একটা করে রেজাল্ট একটি নির্দিষ্ট লিমিটের মাঝে রাখতে পারি।
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।
অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)
বাইনোমিয়াল কো-এফিশিয়েন্ট ( Binomial Coefficient )
বাইনোমিয়াল কোএফিশিয়েন্ট হল অর্ডার বিবেচনা না করে ভিন্ন ভিন্ন সম্ভাবনাকে নেয়া। শুনতে কঠিন লাগলেও ব্যাপারটি আসলে কিছুইনা। আমরা n জিনিস থেকে k জিনিস নিবো, অর্ডার বিবেচনা না করে। এটিকে কতভাবে নেয়া যাবে, এটিই বাইনোমিয়াল কোএফিশিয়েন্ট, অর্থাৎ কম্বিনেশন।
আমরা কিছু সিরিজ এর এক্সপানশন দেখিঃ
(x + y)0 = 1
(x + y)1 = x + y
(x + y)2 = x2 + 2xy + y2
(x + y)3 = x3 + 3x2y + 3xy2 + y3
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4
এসব সিরিজ কে আমরা এভাবে লিখতে পারি কমন ফর্মেঃ
আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) n
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ
আমরা n = 4 নিয়ে দেখিঃ
(1 + x)4 = x4 + 4x3 + 6x2 + 4x + 1এখন কো-এফিশিয়েন্টগুলি হবেঃ 1 4 6 4 1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ
(x + y)n = (nC0)(xny0) + (nC1)(xn-11y1) + (nC2)(xn-22y2) + ... + (nCn)(x0yn); [nCk = combnation of k element from n or n choose k]
আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ
১। ফ্যাক্টরিয়াল ( Factorial )
আমরা সরাসরি nCk ফর্মুলা ব্যবহার করে nCk বের করতে পারি।
ফর্মুলাঃ nCk = [ n! ] / [ k! * (n-k)! ]
ফর্মুলাঃ nCk = [ n! ] / [ k! * (n-k)! ]
আমরা বড় বড় কম্বিনেশন এর জন্য, 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)
n (n-1) (n-2) (n-k+1)
--- * ------ * ------ * ----------
k (k-1) (k-2) (1)
আমরা একে এভাবে লিখতে পারিঃ
nCk (n,k) = 1 ; if k == 0
আমরা একে এভাবে লিখতে পারিঃ
nCk (n,k) = 1 ; if k == 0
else (n/k) * nCk (n-1, k-1)
৪। প্রাইম এর পাওয়ার ( Power of Prime )
আমরা ফ্যাক্টরিয়াল এর কোন প্রাইম এর পাওয়ার বের করতে পারি এভাবেঃ
Pprime = floor[ n/prime ] + floor[ n/prime2 ] + .....
এখানে 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)
এরপরে আমরা ppower করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।
Pprime = floor[ n/prime ] + floor[ n/prime2 ] + .....
এখানে 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)
এরপরে আমরা ppower করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।
৫। চাইনিজ রিমেইন্ডার থিওরেম ( Chinese Remainder Theorem )
যদি আমাদের এরকম বের করতে বলা হয়ঃ nCk mod m where m is not prime , সেক্ষেত্রে আমরা m কে প্রাইম এ ফ্যাক্টরাইজ করার পরে CRT(Chinese Remainder Theorem) ব্যবহার করে মান বের করবো।
Subscribe to:
Posts (Atom)