Find run ascending lists faster

Question

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 code-golf.

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]

Answer 1

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

import itertools

bad = set()

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))
    if key in bad:
        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
    bad.add(key)
    return False