# Find run ascending lists faster

In this question I asked you to determine if a run ascending list could be made. It was code-golf so naturally most the answers are very slow. But what if we want it to be fast. In this challenge I ask you to solve the same task except your goal will be to minimize asymptotic time complexity.

Here's the challenge restated:

A run ascending list is a list such that runs of consecutive equal elements are strictly increasing in length.

In this challenge you will be given a list of $$\n\$$ positive integers, $$\x_i\$$, as input. Your task is to determine if a run ascending list can be made from the numbers $$\1\$$ to $$\n\$$ with each number $$\k\$$ appearing exactly $$\x_k\$$ times.

## Rules

You should take as input a non-empty list of positive integers. You should output one of two distinct values. One if a run ascending list can be made the other if it cannot.

Your answers will be scored by their worst case asymptotic time complexity with respect to the size of the input.

The size of an input list $$\x_i\$$ will be considered to be $$\\sum_{n=0}^i 8+\lfloor\log_2(x_i)\rfloor\$$ bits. Although you are allowed to use formats that do not have this exact memory usage for convenience.

The brute force algorithm has a complexity of $$\O(2^n!)\$$.

The tie breaker will be .

## Testcases

Inputs that cannot make a run ascending list

[2,2]
[40,40]
[40,40,1]
[4,4,3]
[3,3,20]
[3,3,3,3]


Inputs that can make a run ascending list a potential solution is given after the , for clarity but is not necessary for you to compute.

[1], [1]
[10], [1,1,1,1,1,1,1,1,1,1]
[6,7], [1,1,1,1,1,1,2,2,2,2,2,2,2]
[7,6], [2,2,2,2,2,2,1,1,1,1,1,1,1]
[4,4,2], [1,3,3,1,1,1,2,2,2,2]
[4,4,7], [1,3,3,1,1,1,2,2,2,2,3,3,3,3,3]
[4,4,8], [1,3,3,1,1,1,2,2,2,2,3,3,3,3,3,3]

• Anyone got any idea of the time complexity of @Jitse's answer from the linked bug?
– Neil
Commented May 27, 2022 at 16:51
• It’s important to be more precise about how the number of bits in a list is defined. Although $O(\ln x) = O(\lg x)$ are the same, $O(2^{\ln x}) ≠ O(2^{\lg x})$ are not. It’d be best to concretely write down a specific binary encoding of lists, and ask for the time complexity w.r.t. the number of bits in that specific binary encoding (even if the code is still allowed take input in a more convenient format). Commented May 29, 2022 at 0:06
• @AndersKaseorg I'm not sure I quite understand the purpose of your comment, so I think I've addressed it. Using $\ln$ was a mistake and I had intended to write $\log_2$, I'm not sure how much that mistake contributed to thigns, but I've made some changes that hopefully make things sufficiently precise. Commented May 29, 2022 at 0:23
• Sure, it’s precise now. It’s information-theoretically impossible, as the number of distinct lists assigned a size of $s$ “bits” is about $0.00369147 ⋅ 2.00760761^s$, which outgrows $2^s$, but maybe you’re okay with that as long as it’s only for comparative measurement. Commented May 29, 2022 at 1:23
• @AndersKaseorg It's good to know, I suspected it would be possible, but I didn't really care to verify carefully since I am okay with it. Commented May 29, 2022 at 1:34

Python, I'm not sure of the exact complexity. Probably exponential in the worst case.

import itertools

def run_ascending(sizes, low=1, prev=0):
if not any(sizes):
return True
if any(0 < x < low for x in sizes):
return False
key = (low, prev) + tuple(sorted(n for n in sizes if n))
return False
for i, s in enumerate(sizes):
if not s:
continue
if s == prev:
prev = 0
continue
s = sizes[i]
for k in itertools.chain((s,), range(low, (s + 1) // 2)):
sizes[i] -= k
r = run_ascending(sizes, k + 1, sizes[i])
sizes[i] += k
if r:
return True