tamasir
BAN USERThe data structure is a min-heap in a matrix.
You do a regular binary search by picking only midway points along the diagonal, slicing the remaining set of numbers in half (or near half) each time.
Eg for a 10x10 matrix has 100 elements so pick the 7th diagonal element for the halfway point this means there are 7x7 = 49 elements greater than the halfway. You do a binary search to find the largest diagonal element smaller than the key.
Roughly this step is O(log n)
Once you are left with one diagonal element all that remains is to check all the elements to the right of the diagonal and all the elements below. This step is O(n) in the worst case.
Here is a solution without recursion or DP.
Define the combinations by the number of 1s, 2s and 3s in the sequence,
eg 112 has n3 =0, n2 = 1 and n1 =2
and 1111 has n3 = n2 = 0 and n1 =4
This way we can define different combinations by n1,n2,n3,
eg for n1=2,n2=1,n3=0 the three possible combinations are:
112
121
211
the total combinations = (n1+n2+n3)! / (n1! * n2! * n3! )
The maximum possible n3 for a number n is n/n3.
So all we have to do is loop over all the possible n1,n2,n3 for the given n and add the totals along the way.
The code is:
int C(int n){
int total = 0;
for(n3 = 0; n3<= n/n3; n3++){
for(n2 = 0; n2 = (n - 3*n3)/2;n2++){
n1 = n - 3*n3 - 2*n2
total += fact(n1+n2+n3)/fact(n1)*fact(n2)fact(n3)
}
}
return total;
}
Criticisms and comments welcome.
- tamasir January 09, 2013Follow this algorithm:
1. Start from the left
2. Count the largest consecutive decrease in the remaining sequence = n_D
eg, "ID", n_D = 0
eg, "DI", n_D = 1
eg, "DD", n_D = 2
eg, "II", n_D = 0
3. Pick the n_Dth smallest of the available numbers
4. Repeat
The idea of this algorithm is that you always pick the smallest number that will be able to 'survive' the longest incoming decrease.
For example, "IDIDI":
IDIDI, n_D = 0 , pick 1
DIDI, n_D = 1, pick 3
IDI, n_D =0, pick 2
DI, n_D = 1, pick 5
I, N_D = 0, pick 4
add in the remaining, 6
This can be done in time O(n) and space O(n)
How about we just use a stack?
Let the the max number of elements we are after is N, in this case N = 3.
Traverse the array, A, and do:
if (not stack.empty) and (A[i] < stack.top):
stack.pop()
stack.push(A[i])
If (stack.empty) or (A[i] > stack top):
stack.push(A[i])
if stack.size == N then we are done!
Time : THETA(n)
Space : 3
You have three coke machine volume intervals:
- tamasir February 06, 2013(arrange them by increasing max, so max1<max2<max3)
min1,max1
min2,max2
min3,max3
The desired interval is m,n
if a linear combination of the soda machines min,max is completely contained in m,n:
m<min<max<n then a solution is possible, otherwise it is not guaranteed.
Now all you have to do is check if such a linear combination exists, and
start with the machine with the lowest max:
min1,max1 -> is this contained in m,n ?
if not add next machine and so on...