Give array A consist of N (1 <= N <= 10^5) positive integer less than 10^6. Given Q (1 <= Q <= 10^5) queries, for each query of the form (L, R) (1 <= L <= R <= N), print out:
min(A[L], max(A[L 1], min(A[L 2], ...A[R]))))
Note that we DON'T take the min value of (A[L 2], A[L 3], ..., A[R-1], a[R]). 'Min' and 'max' are interleaved.
- For example: A[10] = {3, 1, 4, 5, 5, 2, 7, 8, 1, 1} and 1 query (1, 8):
min(A[1], max(A[2], min(A[3], max(A[4], min(A[5], max(A[6], min(A[7], A[8])))))))
= min(3, max(1, min(4, max(5, min(5, max(2, min(7, 8)))))))
= min(3, max(1, min(4, max(5, min(5, max(2, 7))))))
= min(3, max(1, min(4, max(5, min(5, 7)))))
= min(3, max(1, min(4, max(5, 5))))
=min(3, max(1, min(4, 5)))
=min(3, max(1, 4))
=min(3, 4)
= 3
- My solution is for each query, consider all A[i] (L <= i <= R) to get the result. But it is not possible because N <= 10^5. Is there any other solution to this problem? Thanks everyone.
CodePudding user response：
One way to optimize this is to use dynamic programming.
For all R - L 1 >= 3, note that
Q(L, R) = min(A[L], max(A[L 1], Q(L 2, R))
Furthermore, note that min(a, max(b, c)) = min(a, b) = a if a <= b as max(b, c) >= b >= a. This helps conclude that Q(L, R) = A[L] for all L where A[L] <= A[L 1], regardless of the value of R. You may also choose to use the fact that max(a, min(b, c)) = max(a, b) = a if a >= b to reach a similar conclusion for max(A[L 1], Q(L 2, R)) (and hence Q(L, R)) if A[L] > A[L 1] >= A[L 2].
CodePudding user response：
Suggesting this awk solution, which is easy to convert to your programming language or pseudo code:
Added some comments to explain the script logic.
Essentially scan the array back, flipping/swapping array values by current compare function min/max.
script.awk
function echoArr( title, arr, arrSize) { # echo the current array into a single line
printf ("%s: ", title);
for (idx = 1; idx <= arrSize; idx ) printf ("[%d]=%-7d", idx, arr[idx]);
print "";
}
function swapOnMaxOrMin(arr, idx, compareIndicator) { # swap arr[i] with arr[i-1] following compareIndicator
# compareIndicator > 0: swap arr[i] with arr[i-1], if arr[i] > arr[i-1]
# compareIndicator < 0: swap arr[i] with arr[i-1], if arr[i] < arr[i-1]
if (compareIndicator > 0 ) { # max compare
if (arr[idx] > arr[idx - 1]) { # swap arr values
tempInt = arr[idx - 1];
arr[idx - 1] = arr[idx];
arr[idx] = tempInt;
}
}
if (compareIndicator < 0 ) { # min compare
if (arr[idx] < arr[idx - 1]) { # swap arr values
tempInt = arr[idx - 1];
arr[idx - 1] = arr[idx];
arr[idx] = tempInt;
}
}
}
END {
numsArrSise = int($1); # Array size is field #1 `N`
topNumber = int($2); # top number in array is field #2 `999999`
for (i = 1; i <= numsArrSise; i ) numsArr[i] = int(rand() * topNumber) 1; # popluate array with random numbers
echoArr("Initial ", numsArr, numsArrSise); # display the initial array
queryBottom = int($3); # lower index in query `L`
queryTop = int($4); # top index in query `R`
if (queryBottom >= queryTop) { # assert `L` < `R`
printf "rejected: %d >= %d ", queryBottom, queryTop;
exit;
}
if (queryTop > numsArrSise) { # assert `R` < `N`
printf "rejected: %d > %d ", queryTop, numsArrSise;
exit;
}
if (queryBottom < 1) { # assert 0 < `L`
printf "rejected: %d > %d ", queryBottom, 1;
exit;
}
compareIndicator=1; # start comparing with `max()`
for (i = queryTop; i > queryBottom; i--) { # scan down array from `R` ---> `L`
title = sprintf("%s(-,-)", compareIndicator > 0 ? "max": "min", i-1, i); # set echo title: max(i-1,i) or min(i-1,i)
swapOnMaxOrMin(numsArr, i, compareIndicator); # swap values for numsArr[i-1] with numsArr[i] based on compare indicator
echoArr(title, numsArr, numsArrSise); # echo the current array after the swap
compareIndicator *= -1; # rotate/flip max() with min()
}
printf("arr[%d]=%d\n", i, numsArr[i]); # print final result
}
Running this script:
Where N=10 L=1 R=10
Used max number 52 instead of 999999
$ awk -f script.awk <<< $(echo 10 52 1 10 )
Initial : [1]=49 [2]=31 [3]=16 [4]=31 [5]=39 [6]=41 [7]=23 [8]=18 [9]=41 [10]=6
max( 9,10): [1]=49 [2]=31 [3]=16 [4]=31 [5]=39 [6]=41 [7]=23 [8]=18 [9]=41 [10]=6
min( 8, 9): [1]=49 [2]=31 [3]=16 [4]=31 [5]=39 [6]=41 [7]=23 [8]=18 [9]=41 [10]=6
max( 7, 8): [1]=49 [2]=31 [3]=16 [4]=31 [5]=39 [6]=41 [7]=23 [8]=18 [9]=41 [10]=6
min( 6, 7): [1]=49 [2]=31 [3]=16 [4]=31 [5]=39 [6]=23 [7]=41 [8]=18 [9]=41 [10]=6
max( 5, 6): [1]=49 [2]=31 [3]=16 [4]=31 [5]=39 [6]=23 [7]=41 [8]=18 [9]=41 [10]=6
min( 4, 5): [1]=49 [2]=31 [3]=16 [4]=31 [5]=39 [6]=23 [7]=41 [8]=18 [9]=41 [10]=6
max( 3, 4): [1]=49 [2]=31 [3]=31 [4]=16 [5]=39 [6]=23 [7]=41 [8]=18 [9]=41 [10]=6
min( 2, 3): [1]=49 [2]=31 [3]=31 [4]=16 [5]=39 [6]=23 [7]=41 [8]=18 [9]=41 [10]=6
max( 1, 2): [1]=49 [2]=31 [3]=31 [4]=16 [5]=39 [6]=23 [7]=41 [8]=18 [9]=41 [10]=6
arr[1]=49
Where N=12 L=2 R=8
Used max number 999 instead of 999999
awk -f script.awk <<< $(echo 12 999 2 8 )
Initial : [1]=924 [2]=594 [3]=307 [4]=579 [5]=740 [6]=787 [7]=436 [8]=332 [9]=779 [10]=101 [11]=785 [12]=835
max( 7, 8): [1]=924 [2]=594 [3]=307 [4]=579 [5]=740 [6]=787 [7]=436 [8]=332 [9]=779 [10]=101 [11]=785 [12]=835
min( 6, 7): [1]=924 [2]=594 [3]=307 [4]=579 [5]=740 [6]=436 [7]=787 [8]=332 [9]=779 [10]=101 [11]=785 [12]=835
max( 5, 6): [1]=924 [2]=594 [3]=307 [4]=579 [5]=740 [6]=436 [7]=787 [8]=332 [9]=779 [10]=101 [11]=785 [12]=835
min( 4, 5): [1]=924 [2]=594 [3]=307 [4]=579 [5]=740 [6]=436 [7]=787 [8]=332 [9]=779 [10]=101 [11]=785 [12]=835
max( 3, 4): [1]=924 [2]=594 [3]=579 [4]=307 [5]=740 [6]=436 [7]=787 [8]=332 [9]=779 [10]=101 [11]=785 [12]=835
min( 2, 3): [1]=924 [2]=579 [3]=594 [4]=307 [5]=740 [6]=436 [7]=787 [8]=332 [9]=779 [10]=101 [11]=785 [12]=835
arr[2]=579