Rectangle: Given four integers a, b, c and d, we have to determine if there's a rectangle such that the lengths of its sides are a, b, c and d (in any order) .
Solution: The easiest problem of this set. We just need to find 2 unique integer each having frequency 2. Or only a single integer having frequency 4, in case it is a square (also a rectangle).
Maximum Score: Given N integer sequences, each sequence having N integers, we need to find the maximum number we can get by taking only a single element from each sequence so that, element of i-th sequence is strictly greater than element of (i-1)-th sequence.
Solution: We will solve this in reverse order. First think, if we need to make out score maximum, we should always take the maximum number of the last sequence. After that we will take integer strictly less than that one from previous sequence. Say we have sequence:
1, 2, 10
9, 5, 12
2, 12, 8
We will take values from last sequence. First we took 12, maximum value of the last sequence. Then we come to previous sequence. We need to take value from this sequence which is strictly less than 12. Simple binary search using lower bound technique will give us the index of our desired value. If no such index is present then there is no solution. Of course we need to sort every sequence for this too.
K-Concatenation: Given an array A of size N, we need to make K copies of the array using concatenation of the array values, and then find the maximum subarray sum of that final array.
Solution: As N and K is so big, we can't simply concate A by K times and then find the maximum subarray sum. So, what we can do? we can observe somethings.
First observation: If summation of every element of the array is positve, then the result is summation of all the elements * K.
Second observation:If all elements are negative, then the answer is the greatest number of all the elements.
Third observation: If there are mixed elements, then we can find largest subarray sum in 1-D space using Kadane's algorithm. Now for using Kadane, there is some observations too. If K == 1, we have simply array A, and with the help of Kadane, we can easily find largest subarray sum from there. Notice, if K > 2 what should we do? As we have mixed elements, no matter how large K is, only concatening 2 times is enough for us to find the largest sum. Ok, why 2 times? See a case A = 1 -2 1 and K = 4 suppose, then we get
1 -2 1 1 -2 1 1 -2 1 1 -2 1 ; if we use Kadane here, we will get 2 as our maximum sum.
1 -2 1 1 -2 1 ; if we use Kadane here, we will also get 2. As we are concatening, each time a new concatenation arises, it depends on the previous structure also. So by concatening 2 times, we will get what, by concatening K times, we will get same result.
Final observation: It is the most important of all. Notice these case:
A = 1 1 -9 2 3 4, K = 3, so, we get:
B = 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4
Now, we will check first observation: total sum of A = 2, as K = 3 times, so we get = 6. We will store this value to storage1.
Now, for second observation, all elements are not negative, so we will store a big negative number like -9999999999999.... to storage2.
Third observation, as there are mixed elements, we will use Kadane's algo to find maximum subarray sum for 1 1 -9 2 3 4 1 1 -9 2 3 4 . And that is 11. So, storage3 = 11.
But let's see our final array : 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4; If we take this subarray, we get 13. So this is the final observation of this problem. We need to find two maximum values of our initial array A. We will call it forward_max and backward_max.
forward_max = 1 1 -9 2 3 4 = 9
backward_max = 1 1 -9 2 3 4 = 2
So, our storage4 will be:
forward_max+ S*(k-2) + backward_max ; S = summation of array A = 2
As, we took forward_max of our first part, backward_max of our last part, we are left with K-2 parts between. so we need to take all the remaining K-2 parts sum. Also notice, for final observation, K should be > 2
Our final result will be maximum of all the four storages.
Partition the numbers: Given N and X, we need to partition N numbers in such two sets, that both set will have equal sum after subtracting X from N elements(consider elements from 1 to N).
Solution: First we will calculate summation of N elements using series sum formula: N*(N+1)/2 . Now subtract X from this sum. So, sum = N*(N+1)/2 - X.
Now, if sum is odd then there is no solution, as we can't make an odd number partitioned in two disjoint sets. Also if N <= 3, there is no solution.
Now, when sum is even, we will make sum/2 using our 1 to N numbers without X. We will iterate from N to 1, each time we will check if needed sum is getting zero or not. if we can subtract a value, we will do that, and mark that value as set 1. One important thing is to notice that, while subtracting an integer, we need to check if the remaining sum can be represented by other available integers or not. There is may approach to solve this problem. Implement it however you want keeping some corner case in mind.
String Merging: You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.
Solution: This is a simple dynamic programming problem. Greedy solution won't help you there. What we need to do is simply find the longest_common_subsequence of String A and B. Then our result would be M + N - LCS(A,B). But first, finding LCS between A and B we need to modify A and B string in such a way that no same character right beside each other. If A = "aaaxyyyzza", we need to modify it as "axyza", as there is no same character right after one character. Then we will perform LCS operation in our modifued string and get the final result.
Solution: The easiest problem of this set. We just need to find 2 unique integer each having frequency 2. Or only a single integer having frequency 4, in case it is a square (also a rectangle).
Maximum Score: Given N integer sequences, each sequence having N integers, we need to find the maximum number we can get by taking only a single element from each sequence so that, element of i-th sequence is strictly greater than element of (i-1)-th sequence.
Solution: We will solve this in reverse order. First think, if we need to make out score maximum, we should always take the maximum number of the last sequence. After that we will take integer strictly less than that one from previous sequence. Say we have sequence:
1, 2, 10
9, 5, 12
2, 12, 8
We will take values from last sequence. First we took 12, maximum value of the last sequence. Then we come to previous sequence. We need to take value from this sequence which is strictly less than 12. Simple binary search using lower bound technique will give us the index of our desired value. If no such index is present then there is no solution. Of course we need to sort every sequence for this too.
K-Concatenation: Given an array A of size N, we need to make K copies of the array using concatenation of the array values, and then find the maximum subarray sum of that final array.
Solution: As N and K is so big, we can't simply concate A by K times and then find the maximum subarray sum. So, what we can do? we can observe somethings.
First observation: If summation of every element of the array is positve, then the result is summation of all the elements * K.
Second observation:If all elements are negative, then the answer is the greatest number of all the elements.
Third observation: If there are mixed elements, then we can find largest subarray sum in 1-D space using Kadane's algorithm. Now for using Kadane, there is some observations too. If K == 1, we have simply array A, and with the help of Kadane, we can easily find largest subarray sum from there. Notice, if K > 2 what should we do? As we have mixed elements, no matter how large K is, only concatening 2 times is enough for us to find the largest sum. Ok, why 2 times? See a case A = 1 -2 1 and K = 4 suppose, then we get
1 -2 1 1 -2 1 1 -2 1 1 -2 1 ; if we use Kadane here, we will get 2 as our maximum sum.
1 -2 1 1 -2 1 ; if we use Kadane here, we will also get 2. As we are concatening, each time a new concatenation arises, it depends on the previous structure also. So by concatening 2 times, we will get what, by concatening K times, we will get same result.
Final observation: It is the most important of all. Notice these case:
A = 1 1 -9 2 3 4, K = 3, so, we get:
B = 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4
Now, we will check first observation: total sum of A = 2, as K = 3 times, so we get = 6. We will store this value to storage1.
Now, for second observation, all elements are not negative, so we will store a big negative number like -9999999999999.... to storage2.
Third observation, as there are mixed elements, we will use Kadane's algo to find maximum subarray sum for 1 1 -9 2 3 4 1 1 -9 2 3 4 . And that is 11. So, storage3 = 11.
But let's see our final array : 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4; If we take this subarray, we get 13. So this is the final observation of this problem. We need to find two maximum values of our initial array A. We will call it forward_max and backward_max.
forward_max = 1 1 -9 2 3 4 = 9
backward_max = 1 1 -9 2 3 4 = 2
So, our storage4 will be:
forward_max+ S*(k-2) + backward_max ; S = summation of array A = 2
As, we took forward_max of our first part, backward_max of our last part, we are left with K-2 parts between. so we need to take all the remaining K-2 parts sum. Also notice, for final observation, K should be > 2
Our final result will be maximum of all the four storages.
Partition the numbers: Given N and X, we need to partition N numbers in such two sets, that both set will have equal sum after subtracting X from N elements(consider elements from 1 to N).
Solution: First we will calculate summation of N elements using series sum formula: N*(N+1)/2 . Now subtract X from this sum. So, sum = N*(N+1)/2 - X.
Now, if sum is odd then there is no solution, as we can't make an odd number partitioned in two disjoint sets. Also if N <= 3, there is no solution.
Now, when sum is even, we will make sum/2 using our 1 to N numbers without X. We will iterate from N to 1, each time we will check if needed sum is getting zero or not. if we can subtract a value, we will do that, and mark that value as set 1. One important thing is to notice that, while subtracting an integer, we need to check if the remaining sum can be represented by other available integers or not. There is may approach to solve this problem. Implement it however you want keeping some corner case in mind.
String Merging: You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.
Solution: This is a simple dynamic programming problem. Greedy solution won't help you there. What we need to do is simply find the longest_common_subsequence of String A and B. Then our result would be M + N - LCS(A,B). But first, finding LCS between A and B we need to modify A and B string in such a way that no same character right beside each other. If A = "aaaxyyyzza", we need to modify it as "axyza", as there is no same character right after one character. Then we will perform LCS operation in our modifued string and get the final result.
No comments:
Post a Comment