Showing posts with label toph. Show all posts
Showing posts with label toph. Show all posts
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.
Tuesday, February 6, 2018
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.
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.
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.
Thursday, February 1, 2018
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.
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.
Wednesday, January 31, 2018
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:
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:
Subscribe to:
Posts (Atom)