Итак всем привет сегодня мы с вами Разбираем отборочный контест стаж в компании Яндекс по направлению backend значит сезон 2024 осень Прежде чем начать я напомню что у нас есть Telegram канал в котором мы выкладываем решение задач с разных стажировок в коде значит выкладываем различный материал по подготовки к алгоритмическим собеседованием значит ссылка на канал будет в описании к видео Подписывайтесь распространяйте оче сильно поже Вот теперь давайте перейм собственно к задачам значит первая задача А в чём её суть у нас Дана двумерная табличка состоящая из символов значит отражающая представля сдатся часа например Давайте какой-нибудь пример с посмотрим
из следующих символов Давайте C например А здесь какая-нибудь Т решётка S что там ещё можно сделать так сделаем решётка решётка и т получили табличку размера 3 на3 значит словом в табличке называется непрерывная последовательность символов в строке или в столбце длиной не менее двух и вот вам требуется вывести получается из всех возможных слов которые есть в данной табличке в данном кроссворде требуется вывести а получается в качестве ответа лексикографические минимальное слово да причём длина слова должна быть не меньше двух символов Ну хорошо на самом деле задача решается абсолютно в лоб Тут даже ограничение особо не влияет ни
на что Да у нас м До Д То есть Вполне себе там есть они позволяют не знаю практически любое решение сюда написать Ну Собственно как будем решать задачу собственно реализуем просто что написано в условии Давайте переберёмся возможные строки буде Като року например вот первую строку зафиксировали А теперь Ируся по всем значит элементам этой строки Ну и пока мы не встретили соответственно значит решётку Да решётка обозначает у нас пустую клетку То есть как бы здесь слово заканчивается Вот поэтому если бы допустим у нас какое-нибудь слово было типа кон решётка тес решётка Т здесь натри слова 2
но корректных слов у нас только и два потому что слово длины меньше двух не считается вот да то есть решётка тоже какой-то разделитель да какая-то чёрная клетка в кроссворде которая собственно заканчивает слово то есть слово у нас ограничено чем либо концами этой таблички либо соответственно А значит чёрными клетками обозначающими решётки Вот хорошо давайте значит перебираем первую строку и вот пока мы не ткнули либо значит в последний элемент либо в решётку будем просто запоминать все слова которые у нас получились Ну первое слово очевидно здесь он и Оно занимает всю строку всю первую строку дальше Давайте ещё
по строкам смотрим У нас ещё есть слово Т слово с на самом деле мы их не запоминаем потому что их длинны меньше двойки они нам не нужны вот здесь тоже слово Т нам не нужно тепер Давайте перебирать вертикальные клетки вертикале у нас есть Т то есть опять же да фиксируем столбец перебираем все элементы столбца пока ткнули т в чёрную клетку собственно выбираем строки у на есть слово есть слово о но меньше двух мы их не не берём Да есть слово NS вот ну собственно Давайте теперь посмотрим какие вообще какое здесь минимально лексикографически минимальное слово получается
ну сравниваем первые символы очевидно что эта строка нам точно не подходит потому что как минимум символ C у нас меньше чем символ N остаётся две другие строки Вот давайте дальше смотрим вот в алфавитном порядке что у нас раньше идёт о или T Ну кажется о да соответственно это слово у нас меньше собственно его нужно вывести в ответ ну давайте собственно перейдём к коду Да тут ничего сложного нету простая реализация значит если что вышит всё шаблоны Да шаблонный код начинается Решение вот с дев строчки значит считываем n им размеры поля дальше считываем само поле символьное да
А дальше Давайте запоминать Вектор строк собственно все слова которые мы можем вытащить из этого рда Т Давайте сначала запомним все горизонтальные слова то есть слова расположены по горизонтали итери по всем строкам на каждом шаге фиксируем строку Давайте значит введём промежуточную строку которая будет собственно отвечать за вот этот набор текущего слова Да дальше перебираем все элементы строки что мы делаем чит если мы вдруг нака на чёрную клетку И в тоже время у нас значит строка с набранная промежуточна не пустая да то есть Мы набрали какое-то слово проверяем что длина этого слова больше единички то есть не
менее двойки да И если это выполняется то складываем значит строка S которую мы сейчас набрали это есть какое-то слово складываем её Значит значит это слово в массив ST Да где мы храним соответственно все возможные слова Вот ну и говорим что теперь S - это пустая строка то есть строка прервалась нам нужно начать заново Иначе если у нас соответственно текущая клетка не чёрная да то мы можем продолжить набирать текущее слово поэтому прибавляем строке текущую клетку и продолжаем движение вправо в конечном итоге Да может получиться Так что у нас например вот в данном случае да рассматривали первую
строку мы ни разу не наткнулись на чёрную клетку и в конце концов у нас может получиться Так что длина будет больше единички да то есть мы в конце набрали какое-то слово но его не положи Да поэтому проверяем что слово корректное да то есть Его длина больше единички и кладём его собственно Вектор строк то же самое абсолютно делаем по вертикали значит перебираем Столбцы фиксируем какой-то значит текущий столбец вводим промежуточную строку Ируся по элементам столбца делаем абсолютно все те же действия со столбцом Да натыкается на чёрную клетку проверяем что слово дли слова больше единички кладём его в
векторы слов вот иначе продолжаем движение всё тоже самое в что мы делаем в конце Мыт сортируем просто массив всех слов которые получился Да вводим минимальный элемент он же нулевое сортировка строк происходит в соответстви с лексико графическим порядком поэтому ответ на задачу будет корректным если мы просто от сортируем сроки собственно Всё что касается задачи а она же самая лёгкая задача Ничего здесь сложного тепер Давайте перем задава под отрезка значит В чём суть задачи б суть задачи б в следующем вам Дана перестановка из N элементов значит даётся там определение перестановки подо отрезка Да ну и говорится что
тако медиана последовательность нечётной длины вот что нужно сделать нужно определить количество подо отрезков перестановки которые имеют нечётную длину и медиана Значит этих под отрезков в точности равна заданному числу Да числа и дат у нас меньше равно 10 ВП бо и число оно у нас меше ра логично Да и Боше это медиана желаемая медиана подрезка это собственно количество элементов перестановки Ну дальше соно Да пояснения всякие даются наверное не стоит давать комментарию Что такое медиана Что такое подо отрезок и что такое перестановка Давайте сразу перейдём к решению значит первый элемент первый значит момент которым нужно воспользоваться значит
если у вас есть перестановка Что это значит Почему именно перестановка Ну Ключевое свойство перестановки то что все элементы различны Это очень важный момент задачи супер Ну и второй момент приставки он же на самом деле не сильно нам там помогающий да да задаче чтот все элементы ограничены числом то есть а всегда будет меньше равно хорошо Ну в данной задаче есть такое самое наивное решение Давайте просто зак перем все порезки да нас будет ложных цикла первый к перет левую ни Поре второй цикл перебирает правую границу подо отрезка Потом значит запомним в массив да Значит все элементы этого
подо отрезка от сортируем его кнм в середину если значит серединный элемента это B то медиана значит нашего масива равняется B иначе значит под массив плохой переходим к следующему ну асимптотика такого алгоритма будет на самом деле N в тре что очевидно в данных условиях слишком уж много это два вложены цикла потом е один вложены цикл для того чтобы сохранить все элементы от Да и е соотвественно отсортировать тоже будет чит получается к здесь считывание сортировка получается как раз таки алгори слишком долгое и решение далеко не оптимальное сам де существует гораздо более приятное ИП рение потре ме ра
Ну во-первых какие условия дож быть для этого чит первое вопервых должна прижать порезку есть если не прику очевидно Медиа быть не может долж принадлежать отрезку это первое условие нечётной длины Да значит давайте посмотрим у нас здесь есть какие-то элементы последовательности который меньше и больше соотвественно порек уже отсортирован в порядке возрастания поэтому здесь можно уже как рассматривать значит вот здесь что у нас получается елины сумали этих от А теперь что получается чтобы была медианой подрезка необходимо чтобы количество элементов больших B Да здесь все вот эти элементы и количество элементов меньше B были в точности равны между
собой да то есть именно тогда будет стоять ровно посередине этого отрезка то есть количество элементов Давайте очим по отрезке от до которые меньше B должно быть равно количеству элементов на подо отрезке на этом который больше И при этом заметьте Да вот на самом деле если бы мы у нас были там точнее элементы были бы не различными Да какие-то повторки встречались бы на самом деле слева могли быть как элементы меньше равноб так элементы больше равно это бы очень сильно затрудняло Процесс поиска медиан и вообще не очень не очень понятно бы было как это искать то гораздо
сложнее чем зде в данно случае вс хороо можем Эмен строго больше справа рого меньше вот Ну хорошо Так тепер давайте перейдём отсортированного под отрезка Да к нерку Ну условие в точности должно выполняться всё равно то есть ЕС отрезок элементов вот здесь и вот здесь которые меньше B суммарное количество элементов значит здесь и здесь которые больше B Это количество количество должно быть их количество должно быть равно да то есть это условие оно здесь основополагающее и самое важное Вот и будет работать соответственно АТ для любого подо отрезка Да ну почему так ну потому что если бы отсортировать
вот этот подо отрезок у нас как раз-таки все элементы меньше бы стали бы слева чит потом шло бы B потом все элементы больше B справа но раз их количество равно Поэтому отступ от значит отступ числа B от левой границ от правой границы было бы одинаков да и получилось бы что B являтся медианой так хорошо Ну теперь вопрос как считать вот это вот количество больших меньших как вообще сравнивать это всё Давайте воспользуемся следующей техникой значит данная идея может быть встречена в задаче ту сам на Рид коде да Э вроде одна из самых простых задач вот очень
похожая идейка на самом деле что будем делать Давайте значит найм число во-первых найм позицию числа Масси просто массив здесь Да изначальный здесь число где-то есть Ну и там дальше остальные Като элементы Дава найм позицию числа а теперь что будем делать значит давайте заведём то есть неупорядоченный да Значит cnt м так да cnt значит давайте какой-нибудь K Это количество позиций количество позиций справа от элемента B элемента B А значит имеющих баланс Ну хорошо всё Конечно супер но непонятно что такое баланс Давайте значит разберёмся Давайте заведём отдельную переменную назовём например балл которая будет обозначать баланс соответствующего соответствуй
позиции что это такое Давайте ид к концу массива и если мы встречаем значит элемент с значением больше чем мы увеличиваем баланс на единичку Если же мы встречаем элемент меньше то мы уменьшаем баланс на единичку Что это значит Это значит смотрите теперь по значению баланса мы можем одеть Ках них больше И насколько да то есть если у нас допустим баланс равняется едини Это значит что допустим вот этой позиции Да это чит что вот на вот этом подрезке количество чисел больших B больше количество чисел меньших B ровно единичку да А если у нас допустим баланс на этом
подо отрезке равен нулю Да вот на вот этом подрезке например Это значит что количество чисел больших и количество количест чисел меньших одинаково на этом подрезке да то есть таким вот таком вот трюком да такой вот идей мы можем на самом деле понимать значит разницу между количеством элементов больших и меньших хорошо Теперь давайте вот эту переменную бал изменять двигаясь слева направо и для каждой позиции просто класть её в собственно это как раз таки будет да CN количество позиций справа эта имею Балан Теперь давайте сделаем практически тоже самое только двигаясь значит в левую сторону и теперь и
теперь только да на самом деле уже будем двигаться если мы в том случае двигались от вот этого элемента Да за элементом B вправо то в данном случае будем двигаться соответственно так только сейчас давайте поймём а а на самом деле Т под массив из состоящей просто из элемента тоже считается Да ну тогда никаких там особо ограничений нету Просто идём Значит от элемента B вправо и от элементов B влево и что будем делать также пересчитывать баланс для каждой позиции Да И вот смотрите допустим у нас баланс на вот этой вот позиции Да вот мы дошли Вот до
сюда оказалось что баланс допустим B равняется какому-то значению а давайте даже так напишу прям переменный баланс равен значению а да И при этом это А может быть как больше нуля так и меньше нуля собственно знача ках чисел больше меньших или больших и вот чтобы смотрите то есть Нам нужно для вот этого подо отрезка вот этого нужно найти комплементарный ему подо отрезок справа Да что если мы просуммировать а баланс вот этого порезка будет мину а то суммарный баланс будет равен нулю и как ки мы получим подо отрезок у которого баланс равен нулю то есть количество элементов
меньше меньших и больших одинаково да вот это вот Ключевая идея поэтому что получается Мы двигаемся слева направо начиная справа налево да от позиции к началу массива значит юто соотвественно к ответу Да данной позиции прибавляем значение вот этого вот значит хш таблицы в позиции минус баланс Да как раз таки мы получаем количество собственно закрывающих да скобок или там количество правых границ правее б Да что вот такой вот под отрезок получается хорошим вот собственно Это вся идея задача Да пройтись потом от к началу и привить к отту все вот такие вот значения вот собственно Это вся идея
работает это этот алгоритм за что здесь Вполне себе приемлемо Да собственно на этом идее Наверно всё давайте перем к коду и подробнее объясню как это всё за кодить значит выглядит следующим образом ма Ну в данном случае нумерация единички идт потому что знаю Мне так удобнее Здесь было Теперь давайте найм позицию элемента P значит запоминаем переменную да котора хни будет хранить будущую позицию элемента Ируся по массиву встречаем если то говорим что позиция это равняется и да и заканчиваем выполнение цикла то есть По истечению вот этого блока кода мы как ки полум позицию эта в Масси дам
сохраняем ordered MH таблицу cnt Да г я повторяю cnt Т - Это количество позиций справа от элемента B имеющих баланс K теперь заводим переменную баланс Да итерируемый B то увеличиваем баланс на единичку Если меньше B уменьшаем баланс на единичку и увеличиваем соответственно количество позиций имеющих баланс бал на единичку вот обращаю внимание что мы идём от позиции idx то есть от элемента здесь бы мы не обрабатываем ни разу случай равенства Да ан один раз будет Как раз таки здесь это самом деле неважно неважно Да потому что баланс в данном случае будет но да количество элементов больших
и меньших на вот под отрезке содержащем только элемент очевидно равен нулю вот этот баланс поэтому Изра корректно учёт с балансом ноль дальше сохраняя переменную ответа опять же за нулям баланс и идём теперь от и Иса к начала то есть от позиции B Где Где расположено число b к началу массива и то же самое делаем встречаем больший элемент значит прибавляем баланс меньший элемент уменьшаем баланс и к ответу прибавляем количество элементов правее количество позиций правее B имеющих баланс отрицательны То есть комплементарный к нашему текущему балансу Да почему Потому что е Мы про суммируем их как раз получим
подо отрезок с балансом количество подо отрезков начинающихся в позиции и да заканчивающийся где-то правее б с балансом но Ну и выводим ответ на экран
