Помогите с улучшением моего решения

Question

Ограничение времени         1 секунда
Ограничение памяти  256Mb

Андрей очень любит двоичные последовательности — последовательности, состоящие только из цифр 0 и 1. В особенности он любит последовательности, в которых цифры чередуются.

Недавно Андрей придумал новое обозначение: sn — это двоичная последовательность длины n, в которой цифры чередуются, а первая цифра равна 0. Например, s6=010101, s3=010, а s1=0.

Сегодня Андрею на глаза попалась двоичная последовательность t. Ему стало интересно, какова минимальная длина последовательности sm, для которой строка t является ее подпоследовательностью. Напомним, что b называется подпоследовательностью a, если из a можно вычеркнуть некоторые цифры, чтобы получилась последовательность b. Иными словами, Андрей хочет найти минимальное число m, для которого верно, что можно вычеркнуть из последовательности sm некоторые цифры, чтобы получилась последовательность t. Помогите Андрею справиться с этой непростой задачей

Формат ввода:

Единственная строка входных данных содержит строку t, состоящую из нулей и единиц (1 ≤ |t| ≤ 105).

Формат вывода:

Выведите минимальное число m, для которого верно, что t является подпоследовательностью sm.

def isSubsequence(s, t):
        s = list(s)
        for i,(a,b) in enumerate(zip(t,s)):
            if a != b:
                s.insert(i,'.')
        return len(t) == len(s)
l = input() 
m = len(l)*2 
r = '01'*m 
m = len(r) 
while not isSubsequence(l, r):  
    r = r[:-1]  
    m -= 1 
print(m)

Мое решение слишком долгое и я не знаю как его оптимизировать.

Answer 1

Можно использовать бинарный поиск по решению (конкретнее - поиск самого левого подходящего)

Для начала левая граница бинарного поиска left = len(l), правая right = 2*len(l)

Проверяете - выполняется ли для текущей длины (mid=(left+right)/2) isSubsequence.

Сложность получится O(nlogn).

Подозреваю, что может существовать линейное решение, но пока не увидел его.

Answer 2

Присваиваем начальное значение 1 длине подпоследовательности, потом если первый элемент равен 1, то увеличиваем на 1. Далее проходим до конца строки и при встрече t[i]!=t[i+1] увеличиваем на 1 значение длины, а при встрече t[i]=t[i+1] увеличиваем на два. Может тут ошибки, но вроде работает.

def subseqlen(t):
    result=1
    lent = len(t)
    if t[0]=='1':
        result += 1
    if (lent==1): return result
    for i in range (lent-1):
        if(t[i]!=t[i+1]):
            result += 1
        else:
            result +=2
    return result

t = str(input("Введите последовательность t: "))
print("Длина подпоследовательности равна %d"%subseqlen(t))

Answer 3

Чего-то мне кажется, что надо просто пройти по исходной последовательности и "вставить" нужные цифры в тех местах, где их не хватает.

def calc(seq):
    i = 0
    for v in seq:
        i += 1 if i % 2 == int(v) else 2
    return i

print(calc('1100'))  # результат = 7

"Расшифровка" алгоритма.
i - позиция в выходной последовательности.
Берём цифру из исходной последовательности. Если она "правильная", то просто перемещаемся на следующую позицию i += 1 (в обоих последовательностях). А если "не правильная", то в выходную последовательность виртуально добавляем правильную цифру и цифру из исходной последовательности, и, соответственно, в этом случае смещаемся на 2 позиции в выходной последовательности i += 2.

БЛОГ НА HUSL

Помогите с улучшением моего решения

Ответы (3 шт):