How to find the nth smallest subarray sum bigger than x in a progression where the first two numbers are given?
It might be enough to try each relevant subarray length to find the next element. If we binary search on each length for the optimal window, we can have an O(n * log(n) * sqrt(n))
solution.
But we can do better by observing that each subarray length has a low bound index that constantly increases as n
does. If we keep a pointer to the lowest index for each subarray length and simply iterate upwards each time, we are guaranteed each pointer will increase at most n
times. Since there are O(sqrt n)
pointers, we have O(n * sqrt n)
total iterations.
A rough draft of the pointer idea follows.
UPDATE
For an actual submission, the find_index
function was converted to another increasing pointer for speed. (Submission here, username "turnerware"; C code here.)
let n = 100000
let A = new Array(n)
A[0] = 2
A[1] = 3
let ps = new Array(n + 1)
ps[0] = 0
ps[1] = A[0]
ps[2] = A[0] + A[1]
let ptrs = new Array(n + 1).fill(1)
function find_index(target, ps){
let low = 0
let high = ps.length
while (low != high){
let mid = (high + low) >> 1
let cur = ps[mid] - ps[0]
if (cur <= target)
low = mid + 1
else
high = mid
}
return low
}
function find_window(d, min, ps){
let cur = ps[ptrs[d] + d - 1] - ps[ptrs[d] - 1]
while (cur <= min){
ptrs[d]++
cur = ps[ptrs[d] + d - 1] - ps[ptrs[d] - 1]
}
return ptrs[d]
}
let start = +new Date()
for (let i=2; i<n; i++){
let target = A[i-1] + 1
let max_len = find_index(target, ps)
let cur = ps[max_len] - ps[0]
let best = cur
for (let d=max_len - 1; d>1; d--){
let l = find_window(d, A[i-1], ps)
let cur = ps[l + d - 1] - ps[l - 1]
if (cur == target){
best = cur
break
}
if (cur > A[i-1] && cur < best)
best = cur
}
A[i] = best
ps[i + 1] = A[i] + ps[i]
}
console.log(A[n - 1])
console.log(`${ (new Date - start) / 1000 } seconds`)
Just for fun and reference, this prints the sequence and possible indexed intervals corresponding to the element:
let A = [2, 3]
let n = 200
let is = [[-1], [-1]]
let ps = [A[0], A[0] + A[1]]
ps[-1] = 0
for (let i=2; i<n + 1; i++){
let prev = A[i-1]
let best = Infinity
let idxs
for (let j=0; j<i; j++){
for (let k=-1; k<j; k++){
let c = ps[j] - ps[k]
if (c > prev && c < best){
best = c
idxs = [[k+1,j]]
} else if (c == best)
idxs.push([k+1,j])
}
}
A[i] = best
is.push(idxs)
ps[i] = A[i] + ps[i-1]
}
let str = ''
A.map((x, i) => {
str += `${i}, ${x}, ${JSON.stringify(is[i])}\n`
})
console.log(str)