Arkady Seletsky
BAN USERNotice than when moving from k to k + 1 the value of M[k] = max (a[k], a[k + 1], a[k + 2], ...) could either remain the same, or could decrease if a[k] is that max element. If it is the case, we need to find new max element among a[k + 1], a[k + 2], ...
To avoid doing linear search every time we can have some data structure that keeps elements in sorted order and yields a max element efficiently. Also it has to support remove(x) operation efficiently. A balanced binary search tree with could do. It provides log n performance for both max() and remove(x) operations.
The algorithm:
1. Add all array elements to the tree T // n log n
2. Let MAX_DROP = Integer.MIN_VALUE.
2. Let k = 0.
3. Search and remove value a[k] from T. // log n
4. Let CUR_MAX be of remaining elements in T. // log n
5. Let CUR_DROP = CUR_MAX - a[k]
6. If (CUR_DROP > MAX_DROP) MAX_DROP := CUR_DROP;
7. k := k + 1
8. Repeat starting from 2 while k <= n - 2.
9. Return MAX_DROP.
The time complexity of this algorithm is O(n log n) worst case. The space complexity is O(n).
In case input array contains duplicate elements the algorithm above needs to be modified. We need to keep in tree T number of occurrences of each element. So essentially it will be multi-set (a bag). The remove(x) operation should decrement count in the node, and remove it from tree only if the count becomes 0.
Instead of doing m := m - n; count + =1; thing we can do m := m - k * n, count += k; each step where k is either m/n if m % n > 0, or m/n -1 if the remainder == 0.
This algorithm is actually Euclid algorithm to find gdc(m, n). Very nice problem!
BTW guys, the m: = m - n solution and all recursion solutions have exponential (!) complexity. Yes, they require T = n steps, but the input is not an array of n numbers, but a single number n encoded with log n bits. So n = exp(log n).
E.g. is the input occupies 20 bits the number n itself could be as great as 2^20, and the algorithm could take as much time, e.g. if m == 1.
Here is the full algorithm:
int minSteps(int m, int n) {
if ((m < 1) | (n < 1)) {
return -1;
}
// rules are symmetric, let m be the greatest
if (m < n) {
int tmp = m;
m = n;
n = tmp;
}
int count = 0;
while (m != n) {
int k = ceil(m, n) - 1;
// let's do k steps back to (m - k *n, n)
int rem = m - k * n;
count += k;
// since rem <= n, let's swap horizontal and vertial positions to have (m >= n) again
m = n;
n = rem;
}
// m == n
if (m == 1) {
return count;
} else {
return -1; // m and n are not co-prime, cell (m, n) is not reachable from (1, 1)
}
}
int ceil(int m, int n) {
assert(m >= n);
assert(n >= 1);
int r = m % n;
if (r > 0) {
return m / n;
} else {
return m / n - 1;
}
}
This is the only correct solution for this problem. During pre-computation step it reverses permutation, e.g. for each possible value 0, 1, 2, ... finds its index in the original array. To serve request we iterate over values in ascending order, e.g. 0, 1, 2, ... and check whether index[val] is in range [a, b). The first found value yeilds 0th statistics in question, second - 1st statistics, etc.
Processing request takes O(n) time since we just iterate over index array. Building index array during pre-computation step takes O(n):
for (int i = 0; i < n; i += 1) {
int val = a[i];
index[val] = i;
}
Since partial sums S[] make a sorted array we can use binary search to find whether there is a value that matches target, e.g. equals to S[k] + T, where k is the start index. We need to precompute partials sums.
This algorithms has O(n log n) time complexity worst case and O(n) space complexity.
boolean search(int[] A, int T) {
int n = A.length();
// S[i] = sum_{k < i} A[k]
//
// Hence,
// sum_{i <= k < j} A[k] == S[j] - S[i]
//
// E.g.:
// S[0] = 0
// S[1] = A[0]
// ...
// S[n] = A[0] + A[1] + ... + A[n-1]
int[] S = computePartialSums();
for (int i = 0; i < n; i += 1) {
boolean found = binarySearch(S, i + 1, n + 1, T + S[i]);
if (found) {
// sum_{i <= k < j} A[k] == T
return true;
}
}
return false;
}
// fromIndex inclusive
// toIndex exclusive
boolean binarySearch(int[] a, int fromIndex, int toIndex, int searchValue) {
}
Some sorting based solutions here have a bug.
- Arkady Seletsky February 10, 2018We need to pull all instances of given time before making a final decision on current number. E.g. if at the same time 2 openings and 1 closings the total increment should be +1. But if in your algorithm openings come before closings we'll get +2!
Concrete example: {1, 2}, {2, 3}, {2, 4}. Since quick sort is not stable it could be the case than we get 1O, 2O, 2O, 2C, 3C, 4C. I use "O" to denote opening, "C" to denote closing instead of playing with sign. Your algorithm returns 3, but the correct answer is 2.
In other word algorithm should process closings before openings if they come at the same time.