Here's an interesting situation I encountered recently:
Given a L of N (1 ≤ N ≤
100000) integers, where L0..k is sorted in descending order and
Lk..N is sorted in ascending order for some secret k,
determine the minimum value in the list. Additionally, this list has the property that:
- In L0..k, if a < b < c then La-Lb ≥ Lb-Lc.
- In Lk..N, if a < b < c then Lc-Lb ≥ Lb-La.
You may only look at roughly 1000 elements in the list.
The vague bound on permitted number of lookups is due to the way the
original problem was phrased. In the original problem, there was a function
with discrete domain and range instead of a list, and the function was slow to
evaluate. As long as my program ran in under 3 seconds for some test case, it
was marked correct for that test case; knowing the speed of the judging
computer, this allowed for roughly 1000 function calls.
To rephrase the problem, the list's values form a sort of discrete
parabola (though there are no guarantees on symmetry), and we have to find its
minimum.
EDIT: I later found out that ternary search was a correct solution. However, one of my friends used the parabola-like property to do a standard binary search over the difference between successive points: i.e., its derivative, (if such a term is defined for this situation), which is a monotonic function. Kudos to Charlie for that beautiful solution).
After trying to code a couple of inevitably buggy ternary searches, I
tried a different approach, based on the notion of gradient descent. The
idea here is that we have a function whose minimum we want to find, so we pick
some starting point on the slope of the function and sort of 'slide' down the
slopes (though really, this 'slide' is more of a 'hop' to another point on the
function's slope), stopping once we reach the minimum. This is also related to
the notion of simulated
annealing . When implementing gradient descent with a continuous function,
there are two ways of getting the slope of our current point: either
differentiate the function at the point (thus giving an exact result) or just
approximate it by picking two close points.
I used the latter approach for this problem. We can get the 'tangent' of
some point on the list by comparing two adjacent points. For example, if our
current position in the list holds the value 1000 and the subsequent position
holds the value 500, we should jump forward by a large amount; but if the
subsequent position held the value 990, we're probably quite close to the
minimum, so we should jump forward by a small amount.
It turns out that 1000 list lookups is a hell of a lot, so even dodgy
heuristics like these work most of the time -- it's a number of lookups vs.
speed of convergence trade-off, and since our permitted number of lookups is
very generous, we can be confident we'll converge to the correct solution.
Pretty much, all I had to do was implement something like this. Note that this specific code is largely untested.
# this list is small, but the solution works on very large lists as well
L = [123912, 12000, 11000, 9000, 5000, 4600, 4300, 4250, 4230, 4228, 4231, 4235, 4250, 5400, 6900, 10000, 234432, 23423432, 8645632423436]
min_point, min_val = -1, float('inf')
# start at list item 0, but really we could start anywhere
cur = 0
# initialise the jump size to some value that's slightly smaller than the size of L
jump = int((len(L)-1 - cur) / 1.5)
for i in xrange(500):
# this could theoretically go over the length of the list, but that won't happen
# due to the pattern of jumps. i don't think you can ever normally get to the
# rightmost element, but this should really be proved
adj = cur + 1
# perform two lookups: one for the current point, one for the adjacent point
val_cur = L[cur]
val_adj = L[adj]
# have we found a new best?
if val_cur < min_val:
min_point, min_val = cur, val_cur
if val_adj < val_cur:
# point to the right is smaller than point to the left...
# meaning we are on the left of the min, meaning jump right
cur += jump
else:
# otherwise, jump left
cur -= jump
# perform a vague reduction of the jump size that will allow it to reach 1 within
# 500 steps (this should be dependent on list size, but this is all a huge hack).
# just make sure it doesn't get to 0 prematurely, we always want to allow adjacent jumps!
jump = max(0, int(jump * 0.8))
# and, magic!
print min_point, min_val
Pretty cool, huh? This is a very crude version of gradient descent,
but hey -- it works, and it's surprisingly effective. It found the precise
minimum value in all ~30 cases, including ones that were specifically designed
to break heuristic programs like this. Sometimes you've just gotta hack
something up.
EDIT 2: Here's an implementation of Charlie's algorithm:
# this list is small, but the solution works on very large lists as well
L = [123912, 12000, 11000, 9000, 5000, 4600, 4300, 4250, 4230, 4228, 4227, 4231, 4235, 4250, 5400, 6900, 10000, 234432, 23423432, 8645632423436]
min_point, min_val = -1, float('inf')
# start at list item 0, but really we could start anywhere
start, end = 0, len(L) - 1
while start <= end:
mid = (start + end) / 2
print start, end, mid
mid_val, next_val = L[mid], L[mid+1]
if mid_val < min_val:
min_point, min_val = mid, mid_val
if next_val > mid_val:
# we're on the pos grad. slope
end = mid - 1
else:
start = mid + 1
print min_point, min_val
