7
\$\begingroup\$

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]
\$\endgroup\$
5
  • \$\begingroup\$ Anyone got any idea of the time complexity of @Jitse's answer from the linked bug? \$\endgroup\$
    – Neil
    May 27 at 16:51
  • \$\begingroup\$ 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). \$\endgroup\$ May 29 at 0:06
  • \$\begingroup\$ @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. \$\endgroup\$
    – Wheat Wizard
    May 29 at 0:23
  • \$\begingroup\$ 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. \$\endgroup\$ May 29 at 1:23
  • \$\begingroup\$ @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. \$\endgroup\$
    – Wheat Wizard
    May 29 at 1:34

1 Answer 1

2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.