Task: Given two arrays a,b of length n that are symmetries, permutations of [1, ..., n], calculate an array c = [ a[0]!/b[0]! , ... , a[n-1]!/b[n-1]! ] in O(n) time. (So divide the factorials of the values in a and b at the given index.)
I don't seem to be able to come up with a solution. The idea that in my perception may come closest to the solution may be sorting the arrays from high to low in distance from a[i] and b[i]. And then save the result of the first a[0]!/b[0]! and only have to whittle down a little bit when you advance to the lower differences. But that doesn't account for the intervals of (a[i],b[i]) and (a[j],b[j]) possibly just not overlapping.
Now I am uncertain whether this may just be a mistake in the requirements given, though one is given unlimited space.
You can create a fourth array such that d[i] <- i * d[i-1] by Theta(n) (notice that d[1] <- 1). Now, pass through a and b and compute c like the following:
for i <- 1 to n
c[i] <- d[a[i]]/d[b[i]]
In the above, arrays are an one-based index.