(Inspired by the first problem solved in Stanford’s advanced data structures course.)
Despite the academicese-heavy name, the problem we're going to solve is almost unbearably simple.
We have a list of numbers.
[31, 41, 59, 26, 53, 58, 97]
We're going to cut some contiguous snippet out of that list of numbers.
[31, 41, 59, 26, 53, 58, 97] |41, 59, 26, 53|
And then we're going to find the minimum of that snippet. In this case, that's quite obviously 26. That's all.
And the obvious solution is pretty fast, too, with \$O(n)\$ time and \$O(1)\$ space in the size of the list:
minval = arbitrarily large value for (i=first snippet index, i<last snippet index, i++) if (list[i]<minval) minval = list[i]
So what's with the fastest-algorithm?
Where it gets interesting is when you try to see how efficient you can make it when you have a fixed list but a large number of range minimum queries -- snippets to find the minimum of. This version of the problem is useful, for example, if you have a huge time series you want to load only once, but you want to find the minimum of many different subintervals of that time series.
In such a scenario, it would actually be faster in practice to literally precompute all \$n^2/2\$ queries, store it in a table, and then just retrieve data from that table for an \$O(1)\$ time and \$O(n^2)\$ space solution. ^dynamic programming solution taken from the Stanford slides
And then if you're clever enough, you realize that you only have to store each query with size that's a power of two -- you can just combine those power-of-two minima to sum to an arbitrarily sized query, and achieve the same results with constant time and linearithmic rather than quadratic space.
Interestingly, if you keep optimizing, you can get to an \$O(1)\$ time and \$O(n)\$ space solution using a sort of augmented list known as a Fischer-Heun structure. I'd love to go into the details of the structure here, but explaining how it weaves into Cartesian tree building on fixed-size snippets would make this question about 50 pages long. It's explained in the Wikipedia page, however, along with several faster-than-linear intermediate structures.
(If you can get past a research paywall, here's the original Fischer & Heun 2011 paper. And if you’d prefer the much more verbose but much more hand-holdy Stanford lecture style, here are the follow-up slides that goes into this solution, including lots of intermediates.)
You can either write a full program or a function that calculates the result of a series of range minimum queries given a fixed list. Scoring is set up such that in general, the shortest and most-efficient-over-lots-of-queries code wins.
A list of integers
xs, followed by a series of
i, j pairs denoting the start and end of the snippet, inclusive (so the 26 example above uses indices i=1 and j=4). The list of integers is guaranteed to have at least one integer, and
0 <= i <= j < len(xs). This can be taken in any format that works best for your language — for example, one list for
xs and one list of tuples for the
i, j pairs; or maybe all the different pairs as a variable number of arguments. For a full program that takes in input from stdin, I’ll fix a format for the input:
xs xs xs xs ... i1 j1 i2 j2 i3 j3 ...
An ordered collection of the range minima for each
i, j query, in the same order that they were given. In case an unordered map (such as a Python dictionary) from each
i, j query to its range minimum works better for your language, that will also be allowed as an output; as long as it's obvious which minimum is related to which query.
Once again, for a full program that prints to stdout or a file, I’ll fix the format to have each range minimum on each newline (trailing newlines permitted).
Lower score is better; score is determined by
b is the byte count of your code,
at is the asymptotic runtime
Ө(n) of the algorithm in the size of
xs interpreted as a function of
as is the asymptotic space usage \$\Theta(n)\$ in the size of
xs interpreted as a function of \$n\$. (All constant coefficients in such \$\Theta(n)\$ expressions must be 1, and only the fastest growing term may be kept in expressions, as is standard.)
Therefore, the above pseudocode solution, which uses \$\Theta(n)\$ time and \$\Theta(1)\$ space, and is 126 characters, would have a score of
(b => b**2 + 1)(126)=15876+1=15877. (Of course, the pseudocode isn't really valid since it's missing a construct to deal with multiple queries, and also because it's uncompilable pseudocode...)
31 41 59 26 53 58 97 1 4 0 2 5 6
26 31 58
1 0 0 0 0
-4 28 31 -54 0 0 0 1 0 2 0 3 1 1 1 2 1 3 2 2 2 3 3 3
-4 -4 -4 -4 28 28 -54 31 -54 -54