code-golf, fastest-algorithm, and array-manipulation
Looks like this post hasn't gotten any problems called out, but also not that much support. If you could leave even a brief comment if you don't like it, that would be much appreciated.
(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]
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 linked in the title (which I've copied here), 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.)
The challenge
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.
Input:
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[0] xs[1] xs[2] xs[3] ...
i1 j1
i2 j2
i3 j3
...
Output:
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).
Scoring:
Lower score is better; score is determined by
at(b)^2+as(b)
Where 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 n, and as is the asymptotic space usage Ө(n) in the size of xs interpreted as a function of n.( All constant coefficients in such Ө(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 Ө(n) time and Ө(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...)
Test cases:
Input:
31 41 59 26 53 58 97
1 4
0 2
5 6
Output:
26
31
58
Input:
1
0 0
0 0
Output:
1
1
Input:
-4 28 31 -54
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3
Output:
-4
-4
-4
-4
28
28
-54
31
-54
-54
Sandbox Questions:
Would the asymptotic runtime count as a non-observable requirement?
is this too long and/or abstruse lol
I’m not sure how to word the scoring section to narrow down the most obvious, basic O(n) expression — an algorithm that’s Ө(n) is also Ө(n/16384-50000) by definition. Is what I have clear enough? Have I left any loopholes?
I kind of wanted to encourage people to try to implement Fischer-Heun or one of the more time-efficient intermediates in the slides, without restricting them to one particular algorithm (e.g. challenge: you have to make a Fischer-Heun structure). Does the scoring system make sense for this? Is it fair to have, for example, a Jelly answer using the naive algorithm in 3 bytes (score 10) compete with a Jelly answer using the Fischer-Heun structure in 30 bytes (score 31); but a naive Python answer with score 3000+ compete against with a Python Fischer-Heun with score 300?
