Разбор задач на стажировку в Тинькофф. Задача 5

Всем привет в этом видео Я разберу пятую задачу из текущего алгоритмического отборочного контеста на стажировку в теньков Но прежде чем начать предлагаю подписаться на мой Telegram канал именно там Я разберу все остальные задачи с этого отбора помимо этого там я также разбираю задачи со вступительных контеста другие компании Яндекс Ozone контур при этом выкладываю решение интересных задач разборы наиболее важных тем для собеседований и много полезной информации также подписывайтесь на этот YouTube канал ставьте лайки Дели с мнение в комментариях ну а мы начинаем Ну и переходим непосредственно к задаче я не буду читать полностью условие оно представлено

здесь на экране поэтому сразу немножко перейду к такому формализма значит давайте сделаем задачу более формальной перейдём от бруска и засечек К соответственно массиву из элементов Да соответственно промежутки между числами это у на как ки заечки бруски иним в ЧМ же состоит задача задача состоит в следующем У нас есть получается массив требуется разделить его на соответственно Некоторое количество непрерывных под последовательностей таких что сумма элементов в каждом подо отрезке будет соответственно меньше или равна S то есть каждая сть будет сонно маленькой корректность ния каждая из этих частей должна быть маленькой замечательно теперь соответственно Давайте поймём Да ответим

на первый вопрос Вот есть у нас массив З У нас массив изн чисел Как именно оптимально будет его разбить на соответственно вот такие вот части прият количество частей должно быть минимально Да поэтом заключает собственно оптимальность разбиения Ну допустим Нарисуем массив из семи элементов И вот я утверждаю на самом деле что с помощью достаточно простого жадного алгоритма Мы всегда сможем получить минимальное количество разрезов для того чтобы соответственно сделать массив а правильным корректным Значит будем идти слева направо и на каждом шаге нашего жадного алгоритма мы будем пытаться каждую новую часть сделать максимально длинной и при этом а

по-прежнему сумма её элементов должна быть меньше или равна S что я под этим понимаю Значит на Первом шаге жадного алгоритма Я хочу взять длинней непрерывную последованность непрерывный префикс такой что сумма элементов на нём будет меньше или равна S и если я возьму в эту сумму ещё И следующий элемент то в таком случае сумма превысит s да то есть получается я набираю такую последовательность которая грубо говоря будет предельной Да мы в неё по максимуму засунем членов этой последовательности Да так чтобы сумма не превышала с тогда мы соответственно сделаем распил вот здесь отбросим вот эту часть и

уже будем рассматривать разбиение оставшиеся части на соответственно куски не больше длины не больше чем S То есть получается мы свели нашу большую задачу к более маленькой под задаче вот собственно с помощью таких разбиений Да каждый раз набирать самую длинную часть имеющую сумму не более чем вот собственно количество необх оптимальным количеством на самом деле На этом этапе многие из вас могут уже поверить в правильность этого решения и в правильность того что корректность действительно этого же алгоритма что он реально будет набирать будет делать оптимальное количество распилов однако для тех кто сомневается и в целом для того чтобы

потренироваться доказывать жадные алгоритмы Я приведу доказательства этого утверждения с помощью метода exch arguments значит Представьте что у вас есть соответственно последовательность из N элементов в данном случае в качестве примера Давайте возьмём последовательность из семи элементов шесто и а се и соответственно одна и та же последованность А4 А5 А6 и А7 Вот давайте рассмотрим действительно оптимальное разбиение дап ние этос так и соответственно разбиение построенное нашим Жам алгоритмом назм его разбиение 2 вот собственно суть доказательства состоит в том что если мы докажем что количество распилов в первом разбиении совпадает с количеством пило во втором разбиении то силу

оптимальности первого разбиения второе разбиение тоже будет оптималь оптимально разние буде провост значит мед Exchange argument состоит в том что мы потихонечку маленькими преобразованиями стараемся переходить от одного разбиения ко второму и на каждом шаге будем доказывать что мы никак не нарушаем ни корректность ни оптимальность разбиения что я имею в виду значит давайте соответственно рассмотрим первый распил в первом разбиении что если они допустим у нас в двух разбиения не совпадают да первый распил во втором разбиении у нас после третьего элемента здесь после второго элемента они не совпадают что если мы вот этот распил сдвинем на одну позицию

сюда то есть поместим его вот сюда соответственно нарушится ли корректность первого разбиения и давайте докажем что на самом деле нет Почему Потому что во-первых для вот этого куска Да у нас был соответственно вот такой вот кусок Стал вот такой вот кусок для него корректность не нарушена почему Ну потому что в силу корректности первого разбиения длина вот этого куска была меньше рана S Ну очевидно что длина так сказать под куска также будет меньше равна S поэтому для него корректность нарушена не будет далее Что происходит для соответственно вот такого куска Да действительно граница сдвигается вправо действительно все

аита у нас положительны но да как бы сумма увеличивается Однако мы видим что в нашем ритме каждая соответственно каждый кусок имеет длину меньше или равно S и он является максимальным по включению да Поэтому если мы сдвинем вот это вот разбиение вправо и мы соответственно перед тем как сдвигать они собственно не совпадали в этих двух разбиения тогда соответственно и сумма На вот этом вот отрезке также будет меньше или равна S отсюда мы не нарушили корректность разбиения но при этом смогли сдвинуть первый распил на единицу вправо Давайте пом какого момента можем сдвигать вправо на сам тех пор

пока собст первый распил не совпадут в этих двух разбиения то есть мы этот первый распил сдвинем как раз таки ровно в это вот место да избавимся от вот этого и переднем его вот сюда Таким образом мы не нарушили ни корректность то же самое сделаем со вторым распилом да Опять же сдвинем его вот сюда и доказывается что корректность не нарушается абсолютно Аналогично первом распилу И вот так соответственно просто сдвигами распилов да мы собственно переходим от оптимального разбиения к нашему разни построено с помощью жадного алгоритма Ну и раз первое разбиение оптимально и мы никаких новых распилов не

проводили Мы всего лишь двигали старым то количество распилов первом и втором случае будут одинаковы а соответственно раз первое Значит первое разведение оптимально то и второе построено с помощью рядного алгоритма также будет оптимальным На этом мы собственно заканчиваем доказательства того что действительно разведение построено с помощью нашего алгоритма также будет оптимальны окей на самом деле это уже достаточно большой шаг в решении мы с вами поняли Как именно строить оптимальное разбиение замечательно Давайте теперь переходить к следующему этапу решения Значит от нас с вами просят найти вот такую вот сумму единички до n сумма соответственно от R от L

до N F от L F от как она собственно считается вот если возьмём часть массива с индексами от L D R скажем что теперь вот это у нас новый массив собственно возьмём его оптимальное разбиение и вот сколько кусков в нём получится собственно этому значению и будет равняться наша функция от L и R и собственно нужно взять посчитать сумму значений этой функции для всех подо отрезков нашего массива и Казалось бы перебирать отрезки все под отрезки невозможно Да в силу того что у нас есть ограничения стоит вот на на не превышает 250 Да потому что перебор всех

по отрезков занимает будет у наск времени опять же частичный бал скорее всего задача зайдёт Однако на полный балл будет заслать её тяжело Поэтому нужно что-то более оптимально и вот когда у вас соответственно задаче просят найти какую-то информацию о всех подрезка Ино не позволяет пере всеки в игру следующий такой вот трюк значит давайте представим графический какой-нибудь массив Значит так у нас будет это у нас будет Al А П 1 А П 2 ну и так далее То есть здесь а и так далее и так далее а а давайте только мы е продлим зде будет замечательно О

ну и там дальше до а первого соответственно иногда бывает полезно в таких задачах зафиксировать одну из границ отрезка Ну вот Давайте зафиксируем например левую границу зафиксировали левую границу и собственно посчитаем Теперь попробуем научиться считать сумму сумму значит LR от R от L до соответственно N вот такую вот сумму будем считать то есть мы считаем сумму вот этих вот функции для всех подо отрезков начинающихся в для вот такого отрезка для вот такого отрезка для вот такого отрезка Ну и так далее на правой границе у нас просто будет сдвигаться до стоит сказать что таких отрезков у нас

будет сколько у нас будет N ми Да если конечно у нас на самом деле Ну нумеруется в данном случае единички поэтому таких отрезков будет N L П 1 на самом деле начинающихся в значит начинающихся в с Элемента а заканчиваю где-то правее замечательно А теперь мы соответственно хотим вот такое значение посчитать и давайте сейчас найдём такой индекс G это собственно будет минимальный индекс а такой что соответственно сумма на отрезке от L до G будет больше чем S то есть грубо говоря индекс J - это будет первый такой индекс что сумма на соответствующем отрезке в массиве будет

превышать S То есть получается сумма на вот таком вот отрезке да Получается от Al до а -1 будет по-прежнему меньше или равна S Да вот здесь вот как раз-таки всплывает у нас жадный алгоритм мы нашли теперь наи длинней непрерывную последовательность начинающейся в позиции L и имеющую сумму меньше или равно S собственно если мы добавим элемент А наше сумму наша корректность у нас этот отрезок перестанет быть маленьким и собственно нарушится корректность разбиения замечательно нашли такой отрезок что теперь вот смотрите какие вообще могут быть отрезки начинающиеся в позиции на есть два класса отрезков отре коры заканчиваются до

позиции такие отрезки Да и отрезки заканчивающиеся после позиции То есть их правая граница будет лежать где-то вот здесь вот здесь Ну и так далее да такие отрезки получаются Давайте посчитаем ответ для них независимы Что будет соотвественно с отрезками которые заканчиваются раньше индек знаем сумма элементов на вот таком вот отре тогда ведь сумма и на вот этом отрезке который является под отрезком исходного отрезка она тоже будет меньше или равна S То есть получается весь отрезок будет сам по себе маленьким куском и соответственно никаких распилов для него производить не нужно Он уже маленький Да не нужно никак

его разбивать поэтому значение функции для вот такого отрезка от L Дони и значение функции будет равно единички Да у нас ровно один кусок будет в оптимальном разбиении на больше нам пилить его не нужно Давайте посчитаем количество таких отрезков количество таких отрезков будет на самом деле J - L да да Таких вот отрезков начинающихся в позиции L и заканчивающихся где-то раньше J то есть вот такие вот такие вот такие вот такие вот отрезки для них значение функции будет равно е вот Ну соответственно так J ми соответственно общий вклад вот эти отрезки в нашу сумму дадут какой

Ну единичка умноженная на количество таких отрезков J - L То есть просто J - L это что касается таких отрезков да Значит это у на получается F L Так давайте это получается будет сумма значения функций R1 соответственно где R1 у нас будет меньше с такими отрезками разобрались с отрезками которые заканчиваются правее дела обстоят намного хуже значит допустим отрез вот такой будет Да он заканчивается с оптимально разбить так чтобы каждый кусок имел длину не больше чем с но мы знаем что оптимальное разбиение может быть построено по методу жа алгоритма Давайте попробуем построить собственно найти Первый кусок

в нашем разбиении Но мы же его уже нашли Да вот он вот наш кусок оптимальный в разбиении Почему Потому что он имеет соответственно самый длинный с суммой меньше начинающейся позиции будет первы кусок вот этого даже другим выде его мы пытаемся сейчас разбить вот такой вот отрезок на соответственно оптимального разбить чтобы количество частей было минимально первая часть у на будет Вот такая А дальше смотрите а дальше мы переходим к разбиение вот этого отре изго самый большой кусок начинающийся позиции L А дальше перешли к разбиении отрезка начинающегося позиции G и заканчивающееся где-то там вот смотрите Ключевая идея

заключается в следующем вот что если мы будем идти справа налево по нашему массиву и Допустим мы будем запоминать вот такое вот значение у нас будет своеобразная динамика для каждой позиции и DP и Давайте определим как собственно сумму и до N F от и То есть определим как сумму значений функции для всех отрезков начинающихся в позиции и Давайте вот так вот нашу динамику определим А теперь смотрите если мы идём допустим по массиву справа налево Давайте предположим Что мы умеем считать значение для совестно всех дух и от N до L П 1 и нам нужно научиться пересчитывать

DP L Как нужно его пересчитать значит смотрите для любого такого синего отрезка наше разбиение будет выглядеть как разбиение Значит мы берём Первый кусок и собственно разбиение отрезка с ожи этого по правый конец Теперь смотрите если мы просуммировать R от L до соответственно Давайте только R от J у нас получается будет до N F от L и R то соответственно Это что получается у нас в каждое разбиение будет входить Первый кусок То есть это будет о и таких кусков сколько будет Сколько будет Вот таких вот отрезков начинающихся в позиции J А таких отрезков у нас будет

ров N + получается это единичка войдёт в итоговую сумму N - J п о раз а во что превратятся вот эти вот суммарные разбиения этих отрезков Но мы уже посчитали Да это просто плюс сумма получается R от собственно J N F от J и соответственно R Ну вот это вот мы знаем это просто dpj да получается что мы сделали Мы каждый такой отрезок представили в виде композиции двух отрезков первый отрезок имеет максимальную длину максималь по включению при этом такой что сумма на нём будет меньше равна S а разбиение а сумму разбиения по всем вот таким

отрезком начинающийся в позиции J и заканчивается это правее мы уже знаем это DP J Да вот по определению соответственно мы понимаем Да что теперь DP L - Это что это соответственно вот этот вклад в нашу сумму это J - L и соответственно вот этот вклад это получается п N - J + 1 соответственно и плюс dpj и мы теперь научились считать Вот это значение всё Вуаля Мы практически решили задачу это сокращается у нас J то есть ответ будет зависеть от J только вот в этом месте получаем N - L + 1 и ещё плюс dpj

всё Мы научились пересчитывать нашу динамику остаётся идти справа налево и собственно постепенно насчитывать ответом конечно же будет ответ - Это просто сумма значений нашей динамики и от единички до n сумма всех ТП тых отлично и вот теперь последний нюанс Да последняя штука которую нужно сделать чтобы решить задачу нужно понять А как именно мы будем собственно искать вот этот вот индекс J ведь просто идти нашей позиции L вправо пытаясь набрать эту сумму будет невыгодно Да у нас опять же смотрим ограничение N и на помощь приходит ударный поиск давайте заметим что если у нас Да во-первых у

нас все АИ положительны А что это значит А это значит что если мы зафиксируем левую границу отрезка и будем правую границ увеличивать то сумма соответствующих отрезков будет только возрастать да то есть получается что сумма на отрезке она ф а что мы знаем про монотонно функции про монотонные функции мы знаем что мы соотвественно разделяю границу Нати Бин поиском то есть условно здесь позиция и вот здесь все остальные какие-то позиции позиция и мы хотим найти первую такую позицию что сумма на отрезке от была больше чем ткнули где-то в середину нашего отрезка в середину посчитали сумму на этом

отрезке значит представим что эта сумма будет больше чем тогда разделяю границу нужно искать где-то Вот в этом районе то есть отрава Вот эту вот излишек и ищем уже сужаем диапазон поиска до вот такого если же у нас оказывается что мы ткнули середину отрезка и сумма На вот этом отрезке будет меньше то есть смысл продолжать разделя искать разделяющую границу где-то вот здесь вот Нати э разделяю границ с помощью бинарного поиска Ну а сумму на отрезке быстро искать можно с помою метода префикс сумм Напомни что значит сума на отрезке от ЕС мы посчитаем массив префикс сумм где

это сумма элементов массива на префиксе ини это будет а сумма на фие G тогда соответственно сумма на нашем отрезке сумма элементов на этом отрезке это сумма элементов на всм префиксе минус какой-то мусор который мы вычитаем Таким образом мы находим сумму на собственно таком вот отрезке таким образом с помощью метода префиксный сумм бинарного поиска и достаточно простого динамического программирования мы с вами легко находим ответ на нашу задачу вот ну и Давайте теперь последнее остаётся оценить по времени сколько будет наша программа работать занимает от времени просто линейный проход по нашему массиву Ну соответственно уже по счёт ответа

мы для перебираем все позиции Да и для каждой позиции запускаем бинарный поиск умножаем лорим от Ну и собственно пересчёт значения динамики у нас занимает о от единиц времени это просто у нас такая формула получается иго асимптотика нашего рения и завершает идейную часть решения нашей задачи Ну и теперь можно смело переходить к конгу вот так вот выглядит программное решение задачи Ну и Давайте разберёмся с ним построчно здесь я объявляю функцию Get которая по заданному массиву префиксный сумм и по заданным границам отрезка L и R находит сумму элементов массива заданном диапазоне да э сумма равняется R ми

L - 1 если L у нас не первый элемент массива Ну и собственно переходим теперь к основной части решения функции solve Я объявляю переменный N и S считываются клавиатуры Обратите внимание прям очень большое внимание на то что переменная S у нас если вы пишете c+ + обязаны иметь тип данных ло здесь я это учитываю Я просто переопределять нуж быть типы данных лон чтобы не произошло переполнение объявляю собственно исходную последовательность считывают далее объявляю массивы ф и ДП массив префиксный сумм и массив динамического программирования далее собственно я считаю массив префиксный сумм Да просто стандартный алгоритм прочитать Об

этом можно где угодно объявляю переменную ответа и теперь начинаю роваться с конца массива к началу постепенно перечитывая значение динамики значит объявляю границы бинарного поиска да то есть мы от каждой позиции будем стараться теперь найти такую ближайшую позицию что да сумма на отрезке будет больше чем S значит проверяю что тако Такая позиция вобще существует Да что если у нас оказывается сумма на отрезке с Итого элемента по последний элемент Да если эта сумма оказывается меньше равно S то собственно такого плохого первого индекса мы не найдём и нам значит ДП ИТ имеет соответственно вот такой вот вид то

есть грубо говоря для каждого отрезка начинающегося позиции и значение функции будет равно единички Ну таких отрезков у нас N ми и вот обновляем собственно значение динамики прибавляем это значение к переменной А и переходим к следующей итерации цикла а иначе Такая позиция существует и мы бы хотели найти её с помощью бинарного поиска собственно запускаем бинарный поиск з опять же стандартная реализация бинарного поиска ткнули в середину у нас сумма меньше на S сдвинули левую границу иначе сдвинули правую границу да то есть просто здесь меняем диапазоны собственно поиска То есть получается что Left Да после всего всей итерации

всех итераций цикла у нас Left - Это первый индекс который собственно удовлетворяет вот такому вот условию Да что сумма элементов массива с Элемента и по элемент Left будет больше чем S тогда получается Left - 1 - Это последняя такая хорошая позиция Да что сумма на отрезке будет меньше на S Вот и Собственно как мы уже описали в идее решения мы знаем как пересчитывать нашу динамику Я пояснил всё-таки в идее мы использовали нумерацию с единички элементов массива здесь мы используем нумерацию с нуля поэтому здесь вот эта единичка пропадает Да вот п о пропадает здесь я написал

собственно вывод почему это так собственно обновляем значение это п N ми прибавляем это значение к ны и переходим собственно к новой итерации цикла таким образом после всех итераций после одного прохода справа нале по сего массива мы получим Наш ответ собственно за время O от N Log N