Задача с собеседования в Яндекс
Дается массив 'a' длины n. Найдите количество пар i, j (1 <= i < j <= n), что a[i] + a[j]= 0.

Решение:
Давайте будем проходить по массиву слева направо зафиксировав позицию j, тогда мы должны найти количество таких i, что i < j и a[i] = -a[j]. Но если бы мы создали словарь dict и записывали бы туда количество вхождений каждого числа, когда проходились слева направо т.e dict[a[j]]++ мы бы за O(1) смоги бы находить количество i, что i < j и a[i] = -a[j]. Ровно это и сделаем.
Время работы (N)
Псевдокод в комментариях:

Задача которая встречалась на разных собеседованиях.

Дается массив чисел a1, a2, …., an. Найти максимальную по длине подпоследовательность, которые образует непрерывный набор чисел.
Например вам дали массив
10, 2, 4, 7, 5, 8, 3
Ответом будет 4 так как вы можете взять числа 2, 3, 4, 5

Решение:
Конечно вы можете отсортировать массив и за О(n) выделить максимальную по длине отрезок в котором числа идут друг за другом, но такой алгоритм требует O(n*logn) времени. Собеседующий вас попросит решение за О(n).
Чтобы решить задачу за О(n) давайте заведем словарь has, где has[x]=1 если число х встречается в массиве. После пройдемся слева направо по массиву, пусть вы сейчас зафиксировали число x, теперь вы хотели бы знать максимальное число r, что x+1, x+2, ….., r встречаются в словаре, а также минимальное число l, что в словаре встречаются числа x-1, x-2, …..,l.
Чтобы найти такие l, r вы можете в цикле пройтись увеличивая/уменьшая указатели пока числа встречаются в словаре. Таким образом вы нашли l, r и пытаетесь обновить ответ, но такое решение пока О(n^2), чтобы работало за линию вы должны создать словарь used в котором будете отмечать те числа которые вы посетили в словаре has, чтобы не пытаться искать l, r для уже посещенного х.
Время работы алгоритма О(n).

Псевдокод в комментариях.

Помимо благотворительной деятельности, "Алгоритмы" также проводят индивидуальные/ групповые занятия и консультации по подготовке к собеседованиям, олимпиадам, ШАДу и прочим контестам.

Как проходят занятия?
Занятия проходят дистанционно: чаще всего по скайпу или телеграм. Преподаватель демонстрирует экран и вместе с вами обсуждает материал и решает задачу. По времени стандарт 2 часа, но можно и 1 час. Даже после занятия в любое время вы можете обратиться к преподавателю за советом по задаче, дз, материалам, подготовке, жизни и тд.

Какие гарантии?
Наш основной проект существует уже более 8 лет. У наших преподавателей очень богатый человеческий капитал: академики всех наук, большой преподавательский стаж, опыт работы в крупных российских и зарубежных компаний (в том числе FAANG)

Какая цена?
Цена очень доступная и является одной из самых низких на рынке для сегмента подготовки по алгоритмам, в другом месте за индивидуальный подход и авторские материалы с вас сдерут в 2 раза больше, а в других местах вас будут учить по общедоступным задачам и материалам из интернета, создавая иллюзию подготовки, хотя в карманах таких преподавателей оказываются вполне реальные ваши деньги.
Цена по алгоритмам определяется следующим образом:

— 3000 рублей за час индивидуальных занятий;
— 1875 рублей за час занятий в паре с одного ученика;
— 1500 рублей за час занятий в группе из трёх человек

Лучший вариант для групповых занятий: взять к себе в напарники коллегу/ однокурсника или знакомого. Это позволяет обеспечить сплочённость группы и сопоставимый уровень учеников.

Менторство
Также если занятия вам сильно не по карману, то есть вариант менторства: примерно каждую неделю или по мере продвижения вам высылают теоретические материалы и задачи конкретно под ваш уровень и цель, отвечают на любые вопросы и проверяют решения задач (ежедневная связь). Общение происходит исключительно текстом/войсами (созвониться можно лишь по стандартной ставке). Стоимость менторства: 10000 рублей за 4 недели.

Консультации
Для тех у кого есть вопросы по поступлению в ШАДы, магистратуры, подготовке или по карьере, или в общем по жизни. Вы получите внимательный анализ ваших целей, вопросов и сбор релевантной информации, подборку вариантов и оптимальных направлений подготовки, которые лучше всего подходят для выбранных вами целей, оценку ваших шансов и сроков на достижения цели, все реальные инсайды от наших учеников, которые учатся, работают в подобранных местах, и, разумеется, созвон с нашим специалистом, на котором вы сможете обсудить все детали, обсудить стратегию достижения цели и получить ответы на все возникающие вопросы. Стоимость 4500 рублей за консультацию.

Пробное собеседование
Для тех, кто хочет получить реальный боевой опыт в прохождении собеседований по конкретной секции (алгоритмическая, техническая, ШАД и тд) в конкретные компании от ведущих специалистов, которые сами провели десятку собесов, а прошли еще больше. После mock-интервью вы получите внимательный анализ вашего уровня, код ревью и оценку шансов на успешное прохождение, а также все инсайды и советы как увеличить эти шансы.

По всем вопросам и записи на занятия: @vice22821

Задача с собеседования в Яндекс
Вывести Yes, если массив отсортирован и сдвинут и No, иначе.
Пример:
[5, 8, 11, 2, 3, 4] ответ Yes
[3, 8, 11, 2, 3, 4] ответ No

Решение:
Давайте найдем количество неубывающих последовательностей, например для 3, 8, 11, 2, 3, 4 мы выделим последовательность 3, 8, 11 и 2, 3, 4. Если количество таких отрезков больше двух то очевидно ответ No. Это можно сделать например двигаясь слева направо и смотреть количество знаков >, если их хотя-бы 2 то выводим No.

Теперь у нас два варианта, либо количество последовательностей было 1 или 2, если 1 то выведем Yes, если их два то мы должны проверить что первый элемент из первой последовательности неменьше чем последний элемент из второй последовательности. Если это условие выполняется то выводим Yes, иначе No.

Время работа O(N).

Бонус: Если ответ Yes, сможете ли вы за O(N) и без дополнительной памяти сделать ваш массив отсортированный ?
Например был массив 5, 8, 11, 13, 2, 3, 4 сделать 2, 3, 4, 5, 8, 11, 13 в том же массиве

Задача которая встречалась на разных собеседованиях.
Даются две строки s, t. Вы хотите превратить строку s в строку t. Для этого вы можете проделывать сколь угодно раз следующую операцию: выбрать позицию i в строке s и сделать swap(s[i], s[i + 2]).
Вывести Yes, если можно получить строку t из строки s.

Решение:
Заметим, что у позиций i и i + 2 одинаковые четности, соответственно ваши операции на самом деле заменить два элемента которые стоят в позициях с одинаковой четностью.
Пусть s0 это буквы которая стоят в четных позициях и s1 для нечетных, аналогичное t0 и t1. Заметим что нам надо s0 превратить в to а s1 в t1, но уже свапать можем две соседние позиции.
Мы можем превратить строку s0 в t0 если все буквы встречаются равное количество в строке s0 и t0, аналогично и для s1, t1.
Время работы O(N)

Псевдокод в комментариях.

Товарищи, вот и разбор программирования на стажировку Тинькофф! Архив с кодом оставлю в комментариях. А если хотите научиться ловко разбираться в алгоритмах и тащить собесы/олимпиады, то записывайтесь на занятия и менторство!

1000 шэров (поделиться с другом) и выкатываем разбор математики.

Баянистая задача, которую нужно знать всем.

Дается набор неотрицательных чисел. Известно, что каждое число встречается два раза, кроме одного числа, которое встречается один раз. Найдите число которое встречается один раз. (не использовать словари и дополнительный массив)

Решение:
Воспользуемся фактом а XOR a = 0. Если мы проискорим все числа из массива получил в результате число которое встречалось один раз, так как все числа которые встречались два раза убьются.
Время работы О(N)

Задача с собеседования в Яндекс
Дан массив 'a' длины N. Массив описывает цену единицы товара на протяжение N дней. Каждый день вы выпускаете одну единицу товара и отправление в склад.
В i-тый день вы можете продать определенное количество товаров из склада по стоимости ai. Ваша задача продать все товары таким образом чтобы получить максимальную прибыль.
Например вам дали массив 1, 3, 1, 2 ответ 10.
Так как первый и второй товар продадите по стоимости 3, а третий и четвертый по стоимости 2.

Решение:
Так как в i тый день вы производите новый товар, то продать его можете в день j, где i <= j. Очевидно вы должны продать товар i в день j для которого i <= j и a[j] -> max.

Давайте пройдемся справа налево по массиву поддерживаю максимальное число из массива 'a' которое вы встретили. Пусть это число равно mx. Тогда из рассуждений выше, вы должны просо добавить в ответ mx.

Время работы O(N)

Псевдокод в комментариях.

Задача с собеседования в Яндекс.
Дается строка s которая состоит из нулей и единиц. Вы должны удалить ровно одно число из строки таким образом, чтобы максимальная по длине подстрока состоящая из одинаковых чисел была максимальной.
Например:
s = 110111011100
ответ 6
Решение:
Давайте зафиксируем позицию i которую удалим. Очевидно в оптимальном ответе выгодно удалять такую позицию, что подстрока будет содержать позицию i. Таким образом вы должны найти максимальное количество 1/0 справа от i и слева от i. Пусть количество 1 справа равно r1, а количество единиц слева l1. Аналогично r0 и l0 для нуля. Тогда вы должно обновить свой ответ от max(r0+l0, r1+l1).

Весь вопрос как найти r0,r1,l0,l1.
Давайте научимся находить r0, r1, для каждой позиции.
Для этого пройдемся справа налево по строке. Если s[i]=1 то сделаем r1[i]=r1[i+1]+1, r0[i]=0, а если s[i]=0 сделаем r0[i]=r0[i+1]+1, r1[i]=0.

После аналогичным образом посчитаем l0, l1 (двигаясь слева направо)

Тогда ответом будет
max (max(l0[i-1]+r0[i+1], l1[i-1]+r1[i+1])) по всем i.

Время работы О(N)

Задача с собеседования в Яндекс.
Дается строка s и число k. Найти максимальную по длине подстроку [l, r] для которого количество пар (i, j) таких что l <= i < j <= r и s[i] = a, s[j] = b не превосходит числа k.
Например:
s = aabeab
k = 2
ответ l = 0, r = 4 -> r - l + 1 = 5

Решение:
Задачу решать будем методом двух указателей. Давайте левый указатель l поставим на начало строки, а правый указатель r будем сдвигать в цикле. Если бы мы знали количество пар (i, j), что l <= i < j <= r и s[i] = a, s[j] = b тогда мы могли бы двигать указатель l к указателю r пока количество пар (i, j) больше чем k. Иными словами вы нашли для каждого r самый левый подходящий l. Остается вопрос, а как вообще находить количество пар (i, j).
Для этого заведем две переменные cnta и cntb, где первая переменная - это количество букв 'a' которые вы встретили в подотрезке [l, r], а втора количество букв 'b'.
Таким образом увеличиваете cnta, cntb в зависимости чему равно s[r].
Давайте количество пар хранить в переменной 'cnt' в таком случае каждый раз когда s[r] = 'b' вы должны делать cnt += cnta.
Благодаря этому вы можете сдвигаться l к r пока cnt > k и уменьшать cnta, cntb, cnt в зависимости чему равен s[l].

Остается ответить на вопрос почему два указателя работает. Доказательство такое. Если в подотрезке [l, r] количество пар (i, j) не больше чем k, тогда и для [l + 1, r] количество пар не будет больше числа k.
Если количество пар (i, j) в [l, r] больше чем k, тогда и в [l - 1, r] больше чем k.

Время работы O(N).

Псевдокод в комментариях.

Задача с зарубежных стажировок.

Определим разницу между двумя буквами, как разницу между позициями в алфавите, например для букв 'a' и 'd' разница 3.

Определим разницу между двумя строками s, t одинаковой длины, как diff += (разница между буквами s[i], t[i]) для каждого i.

Вам даются n строк [s1, s2, ..., sn] состоящие из маленьких букв латинского алфавита , каждая строка длины k. Гарантируется, что n * k <= 1e5.
Вы должны построить палиндром длины k, такой что суммарная разница между строками s1, s2, ..., sn минимально возможная.

Решение:
Давайте будет строить первую половину палиндрома (вторая половина однозначно определяется).
Давайте переберем позицию i палиндрома и переберем букву inp которую вставим на позиции i и k - i - 1. Теперь мы должны узнать суммарную разницу между строками s1, s2, ..., sn именно в позициях i и k - i - 1, для этого достаточно перебрать строки sj и посмотреть какие буквы стоят на позициях i и k - i - 1. Среди всех inp мы поставим на позицию i и k - i - 1 такой inp что суммарная разница была минимальной. Таким образом построим палиндром.

Многие могут подумать, что решение долгое, так как мы для каждой позиции i перебираем n строк, а еще и вычисляем сумму для каждого inp, но решение будет работать быстро, так как по факту мы для каждой позиции i рассмотрели n строк (но на позициях i и k - i - 1). Таким образом мы получается каждую позицию для каждой строки рассмотрели ровно один раз, а это пока n * k. Теперь остается умножить на 26, так как inp перебирается 26 раз.

Время работы алгоритма O(n * k * 26)

Задача с зарубежных стажировок.

Дается массив неотрицательных целых чисел а.
Определим стоимость массива как max(|a0-a1|, |a1-a2|, …..|a[n-2]-a[n-1]|)
Так же вам дают целое неотрицательное число max_value. Вы можете выбрать число х, 0<=х<=max_value и заменить нули из массива а на х.
Ваша задача определить число х таким образом, чтобы стоимость массива после изменения была минимальной.

Решение:
Давайте найдем максимальное и минимальное положительное число которое соседствует с нулем из массива a. Пусть эти числа mx, mn соответственно.
Тогда ответом будет min( (mx+mn)//2, max_value)
Время работы O(N)

Задача с ШАДа
Дается массив a. Найдите длину максимально чередующейся подпоследовательности.
Максимальная чередующая подпоследовательность - это набор индексов i1, i2, .., ik где k максимальное и a[i1] < a[i2] > a[i3] < a[i4] > a[i5] < .... a[ik], а также i1 < i2 < i3 < ... < ik

Решение:
Решать будем через динамическое программирование.
Пусть dp[i][0] - длина максимальной чередующей подпоследовательности, которая заканчивается на позицию i, а также знак до числа a[i] был <
dp[i][1] - определим также как и dp[i][0], но знак до a[i] был >
Базой будет dp[i][j] = -INF для всех i, j, а также dp[i][1] = 1 для всех i, (0 <= i < n)

Переходы: dp[i][0] = max(dp[i][0], dp[j][1] + 1) для всех j < i и a[j] < a[i], аналогично и dp[i][1] = max(dp[i][1], dp[j][0] + 1) для всех j < i и a[j] > a[i].

Такое решение работает за O(n^2). На самом деле это можно оптимизировать с помощью дерево отрезков до n*logn но решение за квадрат принимали.

Задача с зарубежных стажировок.
Дается массив целых чисел a. Найдите максимальную сумму на подотрезке массива a.
Например: 2 -3 1 1 -1 2
Ответ: 3

Решение:
Люди которых я собеседовал начинают думать сначала в сторону бинарный поиск, два указателя.

Давайте обсудим бинарный поиск.
Если вы решили решать задачу бинарным поиском вы должны задаться вопросом, а где монотонность. Не надо вслепую верить в какую-то идею во время собеседования, так как вам предстоит объяснять и доказывать свое решение.
Что касается монотонности - рассмотрим отрезок [l, r] и отрезок [l, r- 1] видите ли монотонность суммы (увеличивается/уменьшается сумма) ?
Ответ НЕТ, таким образом бинарить нельзя.

Два указателя:
Чтобы решать задачу двумя указателями вы должны ответить себе на вопрос, если я буду сдвигать один из указателей не сделаю ли я хуже ?
Например перебираете указатель r в цикле и сдвигаем указатель l к себе..... Такая себе идея, но часто слышал во время собесов.

А теперь обсудим правильное решение. Вы должны отталкиваться от железно правильного решения, а именно перебрать все отрезки [l, r] и посчитать сумму в этом подотрезке. Работает за O(n^2).
Оптимизируем до линии.
Давайте сначала попытаемся найти максимальную сумму на каком то префиксе. А именно рассмотрим все [0, i] по возрастанию i. Пусть на этом префиксе сумма равна sum. В какой момент вы можете гарантированно сказать, что нам незачем рассматривать префиксы большей длины ?
Очевидно если sum < 0 нам незачем рассматривать префикс [0, i + 1] лучше бы начала рассматривать все отрезки, которые начинаются с позиции i + 1, а именно все отрезки [i + 1, j].
А такую задачу мы решать уже умеем, например удалить префикс длины i и запустить решение выше.
Ответом будет max(sum).
Время работы O(N)
Псевдокод в комментариях.

Задача с собеседования в Яднекс.
Даются два отсортированных массива. Найдите медиану двух массивов.
Имеется ввиду что вы должны взять эти два массива, объединить в один, после отсортировать и найти медиану.
Решения за O((n + m) * log(n + m)) и O(n + m) не принимались. Нужно решать за O(min(log m, log n)).
Использовать O(1) дополнительной памяти.

Решение:
Задача кодится достаточно больно. Во время собеса было отведено 40 минут на ее решения.
Так как в интернете есть хороший разбор, решил поделиться ссылкой.

Задача с ШАДа
Даются два массива a1, a2, ..., an и b1, b2, b3. ,,, bm, а также вам дают числа A, B, s. Вы должны выбрать несколько чисел из массива a и b таким образом, чтобы сумма взятых чисел была максимальной, но есть ограничение: За каждое взятое число из массива a вы заплатите A, а за каждое взятое число из массива b заплатите B. Вы хотите получить максимальную сумму взятых чисел, но заплатив не более s.

Например:
a = [4, 3, 1, 2]
b = [1, 1, 5, 6, 6]
A = 3, B = 4
s = 16
Ответ 21. Возьмем число 4 из первого массива и числа 5, 6, 6 из второго массива заплатив 15.

Решение:
В общем случае эта задача о рюкзаке которая решается динамическим программированием, но нам дали специально такие ограничения, которые позволяют решить задачу без дп.
По факту мы хотим взять x максимальных чисел из массива a и y максимальных чисел из массива b, чтобы сумма взятых чисел было максимальным и A*x + B*y <= s.

Сначала решим задачу для x = 0. Для этого достаточно взять y самых больших чисел из массива b, что B * y <= s.

Теперь будем увеличивать число x. При каждом увеличении x мы возьмем самое большое число из массива a, но мы можем столкнуться с ситуацией A * x + B * y > s. В такие моменты мы будем уменьшать число y и выкидывать самые маленькие числа, которые мы успели набрать из массива b - это можно делать двумя указателями.

Таким образом мы рассмотрим все возможные пары (x, y) и для каждой пары найдем максимальную сумму. Среди всех таких сумм стоит вывести максимальную.

Время работы O((n + m) * log(max(n, m))

Псевдокод в комментариях.

Задача с контеста Тинькофф

Даны n нестрого возрастающих массивов Ai и m нестрого убывающих массивов Bj. Все массивы имеют одну и ту же длину l. Далее даны q запросов вида (i, j), ответ на запрос — такое k, что max(A[i][k], B[j][k]) минимален. Если таких k несколько, можно вернуть любое.

(1 <= n, m <= 900)
(1 <= l <= 900)
(1 <= q <= n * m)

Решение:
По факту в запросе нам дают два вектора и просят найти минимальный максимум.
Посмотрим на последовательность max(A[i][k], B[j][k]) заметим, что у нас последовательность сначала невозрастает, а потом неубывает.
Если бы все числа были бы различны то мы могли бы видеть такой график:
\ /
\ /
\ /
\ /
\/
Вам нужно найти нижний угол. Эту позицию вы можете найти бинарным поиском сдвигая левую границу если a[mid - 1] > a[mid], но все усложняется тем, что у нас могут быть одинаковые символы и наш график мог выглядеть:
/
\ ———- /
\—— /
\ /
\——/
Теперь именно так бинарить нельзя и наше решение ломается.
Но давайте лучше посмотрим на max(A[i][k], B[j][k]) где первый массив неубывает, а второй невозрастает и по факту мы хотели бы найти самую левую позицию t, такую что A[i][t] >= B[j][t] - а такую штуку мы можем бинарить. Нужно просто сдвигать правую границу бинарного поиска, если A[i][mid] >= B[j][mid].

Второе возможное решение - это тернарный поиск, но сложно будет учитывать равенства.

Время работы O(q * log(l))

Задача с ШАДа

Дается массив положительных целых чисел a длины n <= 1e5.
Набор чисел называется хорошим, если любое число из набора не больше суммы двух других чисел из набора. Найдите хороший набор из массива с максимальной суммой.
Например
5
3 2 5 4 1
Возьмем числа 3, 2, 5, 4

5
1 2 4 8 16
Возьмем числа 8, 16

Решение:
Отсортируем массив a и будем искать ответ в отсортированном массиве.
Пусть мы взяли числа на позициях i1, i2, ..., ik. Чтобы набор был хорошим нам необходимо и достаточно, чтобы выполнялось неравенство a[i1] + a[i2] >= a[ik].

Что вы можете сказать про i1, i2 в оптимальном ответе ?

Утверждение i1 + 1 = i2 - это правда так как иначе вы могли передвинуть i1 к позиции i2 - 1 сохраняя неравенство a[i1] + a[i2] >= a[ik], но уже с большей суммой.
Из этого утверждение получаем вывод:
i1 + 1 = i2
i2 + 1 = i3
i3 + 1 = i4
......
То бишь индексы - это непрерывный отрезок.
Зная эти факты вы наверное уже поняли, что задачу будем решать двумя указателями. Для этого достаточно для каждого l находить максимальный r для которого выполнено неравенство a[l] + a[l + 1] >= a[r].

Время работы: O(n * logn)

Задача с собеседование в Яндекс

Напишите декоратор '@profiler', который при вызове функции будет замерять время ее исполнения
(в секундах, можно дробное) и количество рекусивных вызовов произошедших при последнем вызове функции.
Для работы со временем в питоне есть замечательный модуль datetime.
Декоратор не должен затирать основные атрибуты функции: __name__, __doc__, __module__.
Пользоваться глобальными переменными запрещено, сохранять результаты замеров нужно в атрибутах функции.
Атрибуты назовите last_time_taken и calls.

Задача с Шада
Имеется n касс. Каждая касса работает определенное время работы.
Найдите количество секунд, когда все кассы работают одновременно.
Формат времени работы каждой кассы определяется 6 числами h, m, s, h1, m1, s1 (час, минута, секунда открытие и закрытие кассы соответсвенно)

Решение:
Давайте время начала работы кассы и время закрытие переведем в секунды, то есть сделаем h*3600 + m*60 + s, h1*3600 + m1 * 60 + s1.
Заметим, что время работы кассы теперь определяется отрезком. В случае если время работы меньше времени закрытие мы разобьем на два отрезка [beg, 24*3600], [24*3600, end].
Отсортируем все отрезки по левому значению и пройдемся циклом заведя счетчик открытых касс. Как только количество открытых касс равно n увеличиваем ответ.
Время работы О(n * logn)
Можно решить и за линию.

Задача с Шада
На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое задается одним целым числом — расстоянием в метрах от начальной отметки. Все монеты расположены правее начальной отметки. Али-баба бегает по дороге и собирает монеты, начиная делать это в момент времени 0. За одну секунду он пробегает ровно один метр. У каждой монеты есть крайний срок, до которого (включительно) ее нужно подобрать, иначе монета исчезнет. Али-баба должен собрать все монеты и сделать это за минимально возможное время. Он может стартовать в любой точке прямой, собирать монеты в произвольном порядке, но обязательно нужно успеть собрать все монеты и при этом минимизировать затраченное время. Если собрать все монеты не получится вывести No solution.
(1 <= n <= 1e3) - количество монет.
Каждая монета определяется двумя числами (xi, ti) - место положение и время за которое нужно взять

Решение:
В задаче вы должны выбрать стартовую позицию от которой начнете движение. Пусть это точка xi тогда ваши движение представляется последовательностью R и L (где R - движение на одну позицию вправо, а L на одну влево).

Решим задачу динамическим программированием.
Давайте отсортируем все монеты по координате в которой они стоят.
Пусть dp[l][r][0] - минимальное количество минут необходимое, чтобы набрать все монеты на позициях с l по r и при этом в конце вы окажитесь в позиции xl, аналогично dp[l][r][1], но уже окажитесь на позиции xr.

Вы можете обновить состояние dp[l - 1][r][0] через dp[l][r][0] или dp[l][r][1] в первом случае у вас должно выполняться условие x[l] - x[l - 1] + dp[l][r][0] <= t[l - 1], а во втором x[r] - x[l - 1] + dp[l][r][1] <= t[l - 1]. Аналогично обновляем и dp[l][r + 1][1].

База дп. Поставим для всех l, r (1 <= l, r <= n) dp[l][r][0] = dp[l][r][1] = INF и после dp[l][l][0] = dp[l][l][1] = 0 так как мы можем сами выбирать с какой позиции нам начинать.

Выводим No solution если dp[1][n][0] = dp[1][n][1] = INF, иначе выводим min(dp[1][n][0], dp[1][n][1])
Время работы O(n^2)