Page 10 - Krész, Miklós, and Andrej Brodnik (eds.). MATCOS-13. Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science. Koper: University of Primorska Press, 2016.
P. 10
for i + 1. Then: elements in block bi. Observe that 1 ≤ B ≤ n/2, since two
elements form either an ascending or descending sequence,
Xk + g(i + 1 − k) ≥ Xj + g(i + 1 − j) and in the case B = 1 the “function” is either convex or
Xk − Xj ≥ g(i + c − j) − g(i + c − k). concave. This step takes O(n) time, and allows us to par-
tition G into disjoint intervals where the property of sorted
Which holds for all c ≥ 1, since the residues on the right- residues holds.
hand side at most decrease.
What follows from Lemma 2.1 is that each element from X The algorithm works by moving through the list L and for
occupies at most one interval on our line i = 1...n. each block (start, end, asc), it finds the optimal combinations
of Yi = Xk + Gi−k whenever i − k is inside the interval
We would also like to know, given two elements Xk and Xj (start, end). Once these combinations have been found, they
and j < k, for which gap values will Xk be smaller than Xj. are stored as Yi if they are lower than the current value and
This leads to the inequality: the algorithm moves onto the next block, where the same
process is repeated. Observe that these subproblems can
Xk + g(a) ≤ Xj + g(b) ∀b, a : b − a = k − j. be solved by a slight modification of the algorithms from
[1], where we use the convex algorithm if asc = 1 and the
Rearranging this gives us concave algorithm otherwise. Once we solve the subproblem
in a block, we will not revisit it and so the space can be
Xk − Xj ≤ g(k + c) − g(j + c). reused. The algorithm requires O(n) extra space, which
matches the space requirements of [1].
We can now find the maximal value of c for which the in-
equality still holds in O(lg n) by employing binary search. The time required to solve the subproblem on block bi comes
from the algorithm described in Section 2. In our case, the
Now we are ready to describe the algorithm. First we assign binary search is performed on bi, so the time is O(n lg |bi|).
X1 as the interval that covers the entire line. Then, the al- Over all subproblems the time becomes:
gorithm works by traversing the list of candidates X2, ..., Xn
and comparing the current candidate Xk with the element B
Xj, which corresponds to the rightmost interval on the line.
One can now determine for which values of i the new candi- O(n lg |bi|).
date is better, and the interval can be updated. In the case
that the new candidate is better than the previous one for i=1
the entire interval, we simply remove the old candidate, and
repeat the process on the rightmost remaining interval. Turning the sum of logarithms into the logarithm of the
product we get:
In order to analyze the time required by the algorithm, we B
note that each new candidate from X will perform at least
one binary search, which takes O(lg n) time. Multiple binary O(n lg( |bi|)).
searches may be performed once intervals are removed from
the rightmost end of the line, but observe that each element i=1
X is only added once, so after being removed it is never
reinserted. Therefore, the algorithm takes O(n lg n) time. Assume B is fixed. Since the logarithm is a monotonically
increasing function, the time is maximized when B |bi| is
i=1
maximized. Recall that the geometric mean is less than or
equal to the arithmetic mean. Then we have:
B
( |bi|)1/B ≤ n/B
i=1
3. ALGORITHM B
Observe that the function g only takes on integral inputs. ( |bi|) ≤ (n/B)B.
Therefore, we can consider a more general computation:
given a sequence of values X1, ..., Xn and a sequence of val- i=1
ues G1, ..., Gn for 1 ≤ k ≤ n, compute for all 1 ≤ i ≤ n:
Thus, we can upper bound the time by O(Bn lg( n )). Re-
B
gardless of G, the time is never worse than the straight-
Yi = min1≤k
when B = O(1). If the elements of G come from a function
This allows us to do away with the strict convexity require- g(·), which is defined in the domain [1, n], then B can be
ments. Consider the sequence of values: upper bounded by the number of inflection points1 of g(·)
G2 − G1, G3 − G2, ..., Gn − Gn−1. in that region. Recall for example, that a polynomial of de-
In a preprocessing step, we can traverse this sequence to gree d has at most d − 2 inflection points. Therefore, if the
discover blocks which contain elements in ascending (resp.
descending) order. These are precisely the regions of the values in G come from a polynomial, we can upper bound
“function” which are convex (resp. concave). Build the list
L which, for each block, contains an element (start, end, asc) the running time by its degree.
that stores information about the block boundary (start,
end ) and whether the block is in ascending (asc = 1) or de- 4. FUTURE WORK
scending (asc = 0) order. Let us denote the number of such
blocks b1, b2, ..., bB by B, and let |bi| denote the number of Since we are no longer working with functions explicitly, but
rather sequences, we can also obtain a speedup by working
on X in an analogous way. For example, we could traverse X
1These are points where convexity changes into concavity
and vice-versa.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 10
Koper, Slovenia, 10-11 October
elements form either an ascending or descending sequence,
Xk + g(i + 1 − k) ≥ Xj + g(i + 1 − j) and in the case B = 1 the “function” is either convex or
Xk − Xj ≥ g(i + c − j) − g(i + c − k). concave. This step takes O(n) time, and allows us to par-
tition G into disjoint intervals where the property of sorted
Which holds for all c ≥ 1, since the residues on the right- residues holds.
hand side at most decrease.
What follows from Lemma 2.1 is that each element from X The algorithm works by moving through the list L and for
occupies at most one interval on our line i = 1...n. each block (start, end, asc), it finds the optimal combinations
of Yi = Xk + Gi−k whenever i − k is inside the interval
We would also like to know, given two elements Xk and Xj (start, end). Once these combinations have been found, they
and j < k, for which gap values will Xk be smaller than Xj. are stored as Yi if they are lower than the current value and
This leads to the inequality: the algorithm moves onto the next block, where the same
process is repeated. Observe that these subproblems can
Xk + g(a) ≤ Xj + g(b) ∀b, a : b − a = k − j. be solved by a slight modification of the algorithms from
[1], where we use the convex algorithm if asc = 1 and the
Rearranging this gives us concave algorithm otherwise. Once we solve the subproblem
in a block, we will not revisit it and so the space can be
Xk − Xj ≤ g(k + c) − g(j + c). reused. The algorithm requires O(n) extra space, which
matches the space requirements of [1].
We can now find the maximal value of c for which the in-
equality still holds in O(lg n) by employing binary search. The time required to solve the subproblem on block bi comes
from the algorithm described in Section 2. In our case, the
Now we are ready to describe the algorithm. First we assign binary search is performed on bi, so the time is O(n lg |bi|).
X1 as the interval that covers the entire line. Then, the al- Over all subproblems the time becomes:
gorithm works by traversing the list of candidates X2, ..., Xn
and comparing the current candidate Xk with the element B
Xj, which corresponds to the rightmost interval on the line.
One can now determine for which values of i the new candi- O(n lg |bi|).
date is better, and the interval can be updated. In the case
that the new candidate is better than the previous one for i=1
the entire interval, we simply remove the old candidate, and
repeat the process on the rightmost remaining interval. Turning the sum of logarithms into the logarithm of the
product we get:
In order to analyze the time required by the algorithm, we B
note that each new candidate from X will perform at least
one binary search, which takes O(lg n) time. Multiple binary O(n lg( |bi|)).
searches may be performed once intervals are removed from
the rightmost end of the line, but observe that each element i=1
X is only added once, so after being removed it is never
reinserted. Therefore, the algorithm takes O(n lg n) time. Assume B is fixed. Since the logarithm is a monotonically
increasing function, the time is maximized when B |bi| is
i=1
maximized. Recall that the geometric mean is less than or
equal to the arithmetic mean. Then we have:
B
( |bi|)1/B ≤ n/B
i=1
3. ALGORITHM B
Observe that the function g only takes on integral inputs. ( |bi|) ≤ (n/B)B.
Therefore, we can consider a more general computation:
given a sequence of values X1, ..., Xn and a sequence of val- i=1
ues G1, ..., Gn for 1 ≤ k ≤ n, compute for all 1 ≤ i ≤ n:
Thus, we can upper bound the time by O(Bn lg( n )). Re-
B
gardless of G, the time is never worse than the straight-
Yi = min1≤k
when B = O(1). If the elements of G come from a function
This allows us to do away with the strict convexity require- g(·), which is defined in the domain [1, n], then B can be
ments. Consider the sequence of values: upper bounded by the number of inflection points1 of g(·)
G2 − G1, G3 − G2, ..., Gn − Gn−1. in that region. Recall for example, that a polynomial of de-
In a preprocessing step, we can traverse this sequence to gree d has at most d − 2 inflection points. Therefore, if the
discover blocks which contain elements in ascending (resp.
descending) order. These are precisely the regions of the values in G come from a polynomial, we can upper bound
“function” which are convex (resp. concave). Build the list
L which, for each block, contains an element (start, end, asc) the running time by its degree.
that stores information about the block boundary (start,
end ) and whether the block is in ascending (asc = 1) or de- 4. FUTURE WORK
scending (asc = 0) order. Let us denote the number of such
blocks b1, b2, ..., bB by B, and let |bi| denote the number of Since we are no longer working with functions explicitly, but
rather sequences, we can also obtain a speedup by working
on X in an analogous way. For example, we could traverse X
1These are points where convexity changes into concavity
and vice-versa.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 10
Koper, Slovenia, 10-11 October
