Задача бэкенд Тинькофф (Hard).

Представьте, что у вас есть матрица из 0 и 1 размера n * m, где n * m <= 1e6. В матрице на каждом столбце есть ровно один непрерывный отрезок из единичек.
Например:
0 1 1
0 0 1
1 0 0

За одну операцию вы можете выбрать отрезок из единиц (по столбцу) и переместить их наверх/вниз на один, если не выйдете за пределы массива.
Например я из примера выше могу получить за одну операцию
0 1 0
0 0 1
1 0 1

Расстановка является хорошей, если можно из каждой единицы добраться до каждой другой единицы двигаясь в соседние клетки по 4 сторонам.

Ваша задача за минимальное количество действий получить хорошую расстановку.

Решение:
Пусть, dp[i][j] - минимальное количество операций необходимое, чтобы получить хорошую расстановку для столбцов 1, 2, 3, ..., i, но так, чтобы отрезок из единиц на i-том столбце покрывал позицию (i, j).

Давайте научимся обновлять дпшку. Пусть на i том столбце единички изначально находятся в позициях [s, e] (У нас же единички - это непрерывный отрезок по каждому столбцу).
Как обновляется dp[i][j], если s <= j <= e ?
Конечно же через min(dp[i - 1][s], dp[i - 1][s + 1], ..., dp[i - 1][e])
Отлично, а как быть с остальными j, которые лежат вне отрезка [s, e] ?

Давайте начнем наш отрезок двигать вверх, то есть наш отрезок [s, e] переместиться в [s - 1, e - 1], потом в [s-2, e-2] и так далее. По факту мы ходим скользящим окном и нам надо быстро узнавать минимум на отрезке для dp[i - 1], например, когда отрезок переместился на [s-1, e-1] мы обновляем нашу дпшку через 1 + min(dp[i-1][s-1], dp[i-1][s], ..., dp[i-1][e-1]).

Задача сводится к тому, чтобы быстро находить минимум на в скользящем окне.
ДО - не рекомендуется писать, так как будет TL.

Монотонный стек или Sparce Table самое то!
Если хочешь научиться решать такие задачи то приходи на курсы Алгоритмы Хард, которые начнутся 28 июля.

Асимптотика алгоритма O(n*m)
Код в комментариях

от и возможность для школьников познакомиться с работой в IT! Открыт набор в онлайн-лагерь «IT-дайвинг» — бесплатную программу от VK Education для учеников 7-11 классов. Здесь можно будет узнать о востребованных цифровых направлениях — от ML и разработки до креатива и управления проектами. А еще участников ждет работа над кейсами в выбранном направлении, обратная связь и мастер-классы от экспертов VK. Чтобы попасть в программу, нужно зарегистрироваться в чат-боте до 11 августа.

Вот и задания на все открытые финтех курсы Тинькофф! Конечно, в плане образовательного контента спорно, но участников академии активно хантят HRы на стажировки и позиции в штат, потому не упускаем еще одну возможность получить заветный оффер уже этой осенью😎😎

Задания в БОТАЛКЕ. Там же можно обсуждать. Ждем 500 шэров и делаем разбор!

Полный цикл отбора в Яндекс (Бэкенд 2024)

Продолжаем сопровождать наших выпускников и радовать вас инсайдами, товарищи.

Вступительный контест
Подавался на бэкенд С++, сначала скинули ссылку на контест. Задания нашел тут, просто прорешал заранее и сдал. Первую задачу мне решил ГПТ. Вторая задача была на хэш-таблицу + строки. Третья задача была сортировка + префикс сумма. Четвертая задача была одной из самых сложных, но решалась через префикс суммы. Пятая задача была на алгоритм БОР.

Кстати, товарищи, на курсе бэкенд разработка вы найдете подробный разбор (видео + код) этих задач.

В ту же неделю пришло письмо с приглашением на собеседование, списались с HR по тг. HR оказался приятным, на все мои вопросы подробно отвечал и не игнорил.

Алгоритмическая секция 1
Задача 1: дается массив из 0 и 1. Нужно за один проход поставить все нули в начало массива. Задача баян, в группе выкладывали задачу.
Задача 2: дается массив 0 и 1. Найти длину максимального подотрезка, состоящего из 1, после удаления ровно одного нуля. Решил быстро, и в запасе оставалось еще 20 минут.
Собеседующий решил просто так не сидеть и дал 3 задачу.
Задача 3: дается строка, найти максимальную по длине подотрезок, состоящий не более чем из k различных букв. Тоже какая-то баянистая задача на два указателя...
Остается 5 минут, и собеседующий говорит: «Го, еще одну задачу, достаточно, чтобы ты рассказал идею».
Задача 4: дается массив чисел. Найти наибольший по длине подотрезок, что сумма чисел в этом подотрезке равно 0. Ну и я ему предлагаю решения с префикс-суммой и хеш-таблицей за O(1).

Алгоритмическая секция 2
Задача 1: Дается массив из 0 и 1. Найти такую позицию нуля, что расстояние до ближайшей единицы максимально возможное. Рассказываю решения за линию и пишу код.
Задача 2: Дается бинарное дерево поиска, проверить, что это дерево является сбалансированным.
Рассказываю линейное решение, пишу код, исправляю пару багов. Остается еще 15 минут, я 5 минут позадавал ему вопросов по компании, и на этом разошлись.

Алгоритмическая секция 3
Задача 1: Условие было длинное, единственное, что запомнил, что там были отрезки (как временные интервалы), которые были даны в отсортированном порядке, и нужно было написать бинпоиск)
Задача 2: Дается натуральное число n. Нужно представить число n в виде суммы квадратов. Написать программу, которая находит количество представлений числа n.
Если честно, был удивлен, что предложили такую задачу, так как она решается простой баянистой дпшкой за n*sqrt(n), к счастью, оказывается, это же решение от меня ожидали.

Приходит HR с обратной связью. Говорит, что теперь будут подбирать мне команды. Кидается 4 ссылки на команды, говорит, выбирай, что интересно, я сказал, что хочу во все попробовать. Мне начали по очереди ставить собесы в команды.

Собес 1
Пришел лид одной команды, сказал, что ему важно, чтобы хорошо знали ООП на С++.... Он начал спрашивать все по ООП, показывал примеры кодов и задавал, сколько раз какой-то объект скопируется и т. д.
В общем, собес состоял только из ООП.

Собес 2
Пришли собесить два парня, такие разговорчивые. Начали узнавать, чем занимался, есть ли у меня опыт по БД, Linux. Потом дали около алгоритмическую задачу, в которой нужно было использовать map и указатели.

Собес 3
Интервьюер Говорит, что в его команду нужен человек, который знает многопоточности. У меня от этого слова уже в глазах потемнело.... Потом он сказал, что понимает такие темы, скорее всего, стажеры не знают....
И начинает по поверхности многопоточности задавать вопросы, я, конечно же, ничего ему не отвечаю.
После он мне дает задачу и говорит: «Давайте попытаемся решить многопоточностью, есть у вас идеи?» Я говорю: «Нет», и собес на этом заканчивается.

Собес 4
Сходу мне дает задачу:
Поступают запросы вида:
+ x (Добавить число x в множество)
- x (Удалить число x из множества)
get min (вернуть минимальный элемент из множества)
get max (вернуть максимум из множества)
Такое решение нужно написать за линию. При этом в множестве могут быть повторы.

В итоге два приглашения и два отказа. Чисто хватило алгосов.

Все задачи, которые встретились на собесе ШАДа 2024 года.

1) Дается массив/строка и число k. Найти максимальный по длине подотрезок в котором <=k различных элементов.
Решать нужно за O(n) а памятью O(min(k, количество различных букв)). Также могли спросить как работает словарь если использовали словарь.

2) Дается массив чисел. Вернуть true, если за один swap можно массив сделать отсортированным по возрастанию.
Очень жаль людей, которым попалась эта задача, так как некоторым попадались холявке, а эта я считаю сложной задачей для собеса, так как очень много подводных камней.

3) Даются две строки s, p. Найти все позиции в строке s, что подстрока s[i: i + len(p)] является анаграммой для строки p.
Решать за линию использую словарь. Некоторых спрашивали как работает словарь.

4) Даются два массива a, b. Длина массива b равно k. Найти количество подпоследовательностей массива a, что они равны массиву b.
То есть найти количество различных множеств (i1, i2, ..., ik), что a[i1] = b[0], a[i2] = b[1], ..., a[ik] = b[k-1]
-Решение за квадрат удовлетворит собеседующих.

Хотя-бы одна из этих задача будет и в следующем году, так что рекомендую разобрать все задачи если поступаешь в след году.

(Если вам попалась другая задача то поделитесь условием в комментариях)

Какие языки ботать Backend разработчику

Если вы начинающий специалист, то здесь есть некий парадокс.
По-хорошему нужно покопаться в C++ / C, ведь они довольно низкоуровневые и с помощью этих языков можно лучше понять, как устроена память, некоторые процессоры, concurrency, да и немного покопаться в операционных системах. На этих языках можно поперекладывать сырые байтики, поставлять туда ассемблерных вставок, повызывать всякие syscall’ы, почитать код Linux ядрa - часто хорошие учебные курсы тесно связаны с данной парой языков, а выучить какой-либо язык после плюсов не составит труда.

На этих языках было написано много классического и они полезны для изучения и понимания, но на рынке на них довольно сложно найти вакансии, а нормальные вакансии - в особенности. Это касается и стажировок: на плюсах их очень мало. На ум приходят лишь что-то специфичное в духе Kaspersky, Quantitative research. В каком-то сезоне в Тинькофф открыли лишь 5 вакансий. В тот же Яндекс можно попасть, зная лишь С++, но на чистых плюсах вакансий реально немного и поиск может затянуться. Нередко по моим наблюдениям и скромному мнению плюсы используются там, где они не нужны, где легче было бы написать проект на Go.

Также, разработчику когда-нибудь нужно будет настрочить что-нибудь на Python: какой-нибудь тупой скриптец или же написать на нем тесты. Так что знать его тоже полезно. Но на вакансии, где вы будете писать только на Питоне лучше не идти: на нем никогда не будут писаться какие-то серьезные проекты. Если проект и написан на питоне, то скорее всего это либо какой-нибудь вялый питон джанго, либо какой-нибудь легаси проект. На такое не ведитесь — будете ощущать себя макакой!

Как мне кажется один из самых лучший языков для изучения — это Go. Сейчас все новые и крутые проекты пишутся на нем, с ним не так сложно найти работу, как на плюсах, он прост и красив в изучении, также полезен, если разобраться в том, как он устроен изнутри.
Касаемо поиска работа, например, у меня была ученица с питерского ПМИ ФКН, у которой за плечами был лишь годовой курс плюсов. Она быстро прошла все собесы на стажера Яндекс, но долго ждала, когда поставят финальные собесы. По итогу HR увидела на ее гитхабе какой-то скромный пет проект, написанный на Go и предложила попробоваться, сказав "у нас здесь так много вакансий на Go". Затем девушку ждал тупой собес с руководителем и релокейт в Москву.

Также, можно попробовать что-то поклацать на Java. Язык также "старый" и буквально любая микроволновка была написана на нем, поэтому с ним вы точно не пропадете. Если наступят тяжелые времена, то можно начать писать на нем моды для майнкрафта.

Все же, нужно понимать, что язык — это лишь инструмент. Не нужно его выбирать, как жену — одну на всю жизнь! Главное — знания и понимания того, как устроен компьютер и распределенные бекенд системы, инженерия. Всему этому мы уделяем большое внимание на нашем курсе по бэкенд разработке, ведь в основном, языки похожи друг на друга, поэтому перейти на новый язык на хорошем уровне для хорошего инженера— это дело максимум недели, а для выпускников наших курсе— дело двух минут!

Полный цикл отбора в Яндекс (МЛ 2024)

Сейчас студенты наших прошлых курсов под моим чутким сопровождением ломанулись проходить отборы в Яндекс, поэтому продолжаю радовать вас инсайдами и актуальными вопросами.
Далее представлен слегка отредактированный текст нашего выпускника.

Вступительный контест
Задания нашел тут, просто прорешал заранее и сдал, но зашли только 4 задачи. Первую и пятую мне решил ГПТ, только нужно было поправлять. Шестая просто посчитаит количество вхождений конкретных слов, а потом сортируем. Вторую мне скинул знакомый. Этого хватило, а знакомому хватило трех задач.

Кстати, товарищи, на курсе машинное обучение вы найдете подробный разбор (видео + код) этих задач.

МЛ секция
Сначала дали очень простую задачу на два указателя: в строке найти длину наибольшей подстроки, состоящей не более чем из двух уникальных символов. Я даже растерялся и начала копать не туда. Интервьюер предложил рассмотреть на примере и я сразу сообразил. Потом была простая задача по мл. Она разобрано здесь. И немного поспрашивали базу про классификацию, про линейную регрессию и регуляризацию.

Алгоритмическая секция
Первая задача: сжимать список целых чисел в диапазоны, которые там встречаются. Например, [1, 3, 2, 8, 11, 9, 0] -> "0-3, 8-9, 11".
Вторая задача: для множества точек на плоскости с целыми координатами определить есть ли у них вертикальная ось симметрии.
Для тех, кто в теме, задачи довольно баянистые. Их даже можно найти здесь.
Задачи я решил быстро и еще оставалось время, собеседующий дал мне задачу: написать бинарный поиск.

Дальше ждали собесы с командами.

Собес 1 (Яндекс Доставка)
Лайтово. Спросили просто про опыт, чем занимался. Поговорили про хакатоны, мои пет проекты. Мог только похвастаться кредитным скорингом и рекомендацией фильмов, которые я стырил и адаптировал по заветам Поступашек🙈😎.
Рассказали про себя и чем предстоит заниматься. Нужно выдумывать всякие фичи в катбуст, чтобы в реальном времени предсказывать приедет курьере или нет.

Собес 2 (Яндекс Деньги)
Здесь уже было потновато. Сначала попросили рассказать про случайный лес и градиентный бустинг, уточняющие вопросы по теории. Дальше попросили рассказать в общих чертах про АВ тесты и заострили внимание на ошибке 1го и 2го рода, p-value, мощность. Спрашивали про опыт работы в линуксе и написания скриптов на баше, попросили написать простой SQL запрос в блокнотике (есть табличка - фио, зарплата, отдел, надо вывести людей получающих минимальную зарплату в своем отделе). Затем был мл кейс: какие вопросы (из 100 имеющихся) задавать пользователю для идентификации мошенника. Чем-то подобным и предстоит заниматься в команде: по поведению пользователя на сайте и в приложении научиться понимать, бот это или нет. Поговорили про метрики классификации, а также про реализацию моего решения.
Вообще для подготовки к мл кейсам, помимо бота классической теории, советую смотреть всякие статьи на Хабре, конференции от Яндекса, Тинькофф и тд. Понятно, что в первую очередь смотреть выступления конкретной команды, с которой будет собес, и выступления левых команд, но в той же области.

Собес 3 (Яндекс Музыка)
Было много вопросов про метрики, какие знаю, физический смысл ROC-AUC. Дальше спросили: есть одна фича и один таргет, обучили регрессию, но весь тест лежит правее всего трейна— что выдаст линейная регрессия, KNN и случайный лес? И затем мл кейс, как сделать рекомендации плейлиста на сегодняшний день. Все основные повороты описаны здесь

В итоге три приглоса. На собесах ожидал хоть один вопрос по глубокому обучению, но его не было.

Вот и разбор алгоритмов на стажировку в Яндекс! Обязательно делимся с друзьями. Ждём 5 тыс просмотров на ютуб ролике и выкладываем аналитику.

Смотрим! Смотрим! https://youtu.be/AdfjZ4u8GLg

Задача для тех кто пишет на С++.
Это одна из задач, которая попалась во время собеседования.

Задача:
Вам приходят запросы двух видов.
1) Добавить в конец элемент 'x'
2) Удалить самое ранее добавленное число.
(По факту у нас очередь)

Вам можно пользоваться только одним std::vector. Но вам известно, что в любой момент времени в очереди могут находиться не более n чисел.

Имея один вектор размера не более n научитесь обрабатывать все запросы.

Решение:
Давайте создадим вектор a размера n. Будем циклически записывать числа в массив.
https://en.wikipedia.org/wiki/Circular_buffer
Вот такое вот решение господа

Думаю будем полезно всем кто будет проходить собес на С++.

Эти пет проекты должен сделать каждый ML специалист

Устроиться можно попасть и без проектов, но если у вас их нет, то мл кейсы будут решаться неуверенно и на финалах будете выглядеть слабее других. Никто не ждет гениального проекта с инфраструктурой— реализовать какие-то бейзлайны и понимать специфику задач уже достаточно для стажера и джуна.
Уже делали подобную подборку для аналитиков здесь, советую присмотреться.

1. Кредитный скоринг
Стоит ли давать кредит— довольно популярная задача и отличный выбор для новчиков, чтобы самостоятельно проделать все этапы. Сначала берем любой датасет на kaggle по запросу Credit Scoring. Проводим EDA, генерируем гипотезы, фичи, готовим данные для модели и делаем бейзлайн: логистическая регрессия. Затем уже можно попробовать случайный лес, градиентный бустинг, KNN или еще что по вкусу— сравниваем метрики. И на последок не забываем проанализировать результаты и культурно презентовать. Можно провести АВ тест на смой первой модели.
Все варианты решения и реализации можно найти в интернетах: GitHub, Хабр. Очень полезным будет посмотреть всякие выступления на конференциях по этой теме для вдохновения, да и это очень поможет на мл кейсах.

2. Наивный Байесовский классификатор (НБК)
Для конкретики будем классифицировать письма на спам. Опять же обработаем данные: удаляем числа, знаки препинания, стоп-слова, стемминги, лемматизацию.
Объединяем все методы предварительной обработки и создаём словарь слов и счётчик каждого слова в наборе данных для обучения:
1. Вычисляем вероятность для каждого слова в тексте и отфильтровываем слова со значением вероятности меньше порогового. Такие слова будут нерелевантными.
2. Для каждого слова в словаре создаём вероятность, что это слово окажется в спаме. Определяем условную вероятность для использования её в НБК.
3. Вычисляем прогнозируемый результат с помощью условных вероятностей.
НБК реализовать не сложно. Куда интересней погрузиться во всю теорию, которая за этим стоит, в вероятностные модели. К тому же, кейс фильтрации спама и подобного часто встречается на собесах.

3. MLOps
Можно наладить какой-то минимальный прод для проектов: например телеграм бот или FastAPI. Можно еще автоматизировать пайплайн с помощь AirFlow и попробовать запустить инфраструктуру не только локально, но и облаке. Конечно нужно будет поизучать Docker, Cuber, Hadoop, Spark, HDFS, Kafka. Но на самом деле ничего трудного— после нашего курса дата инженер будете делать такие вещи по щелчку пальцев.

4. Ранжирование и матчинг
Для начала лучше пробежаться глазами по статье и посмотреть, что пишут в интернетах. Можно выделить три подхода к задаче: поточечный, попарный, списочный. Советую начать с первого как самого простого. Для конкретики будем предсказать оценку релевантности для запросов тестового датасета. Здесь можно кстати поучиться парсить web-страниц и собирать сырые данные, размечать их с помощью какого-нибудь Яндекс-Толока. Делаем регрессию, а затем Random Forest Regressor, XGBoost, lightGBM, CatBoost.
Совсем продвинутые могут попробовать языковые модели в духе FastText, Word2Vec, DSSM и более сложные: BERT, можно даже попробовать архитектуру трансформеров.

5. Рекомендашки
Очень популярный кейс на собесах. Для начала лучше пробежаться глазами по этому разделу и посмотреть, что пишут в интернетах. Затем начинаем реализовывать самое простое как бейзлайн, например, content-based рекомендации, KNN. Дальше можно попробовать факторизации матрицы рейтингов по svd разложению или по более эффективной als архитектуре и функции ошибок bpr. Затем можно попробовать W2V подход, чтобы использовать последовательность взаимодействий пользователя для построения рекомендации следующего предмета.
Для знатоков DL можно попробовать DSSM, SasRec/Bert4Rec, MultVAE, Merlin или графовые нейронки: GCN-подобные архитектуры.
Также стоит попробовать обучение с подкреплением: многоруких бандитов.
Ну и конечно рекомендательные системы можно попробовать рассмотреть как задачу ранжирования.

Вот и разбор аналитики на стажировку в Яндекс! Обязательно делимся с друзьями. Ждём 5 тыс просмотров на ютуб ролике и выкладываем МЛ. Советую поторопиться: контест вот-вот обновят.

Смотрим! Смотрим! https://www.youtube.com/watch?v=k4C9aWR6YJ4

Задача Яндекса.
В последние дни все чаще встречается задача:
Дается массив из целых чисел длины n > 1. Вы должны вернуть минимальное произведение, которое можно получить из двух чисел массива. (позиции чисел должны быть уникальны)

Решение:
Конечно нужно решать за линию.
Пусть max1, max2 - два максимальных числа из массива, при этом max1 >= max2.
Пусть min1, min2 - два минимальных числа из массива, при том min1 <= min2.

Если min1 <= 0 и max1 >= 0 то ответом будет min1 * max1

Иначе мы получаем два варианта:
1) Все элементы положительные, в таком случае нужно вернуть min1 * min2
2) Все элементы отрицательные, в таком случае вернем max1 * max2

Именно так лаконично рассмотреть случае.

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

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

Яндекс обновил контест на стажировку осень-зима. Задания уже лежат тут, там же можно их обсудить вместе с админами. И конечно разбор нового контеста будет на наших курсах, так что присмотритесь к ним.

Стажировка в Яндексе - самая крупная стажировка из всех, больше всего мест и их точно хватит на всех. Весьма прозрачный отбор, о котором писали здесь. Для успешного прохождения на собесы обычно достаточно решить 2/3 заданий, а в прошлый раз только половину.

Также не забываем посмотреть полный цикл собесов в Яндекс наших учеников:
Бэкенд
Аналитика
Машинное обучение

Яндекс собирается выделить ещё больше мест в ШАД, а значит попасть туда станет ещё проще. Лучше начинать потихоньку-понемногу готовиться уже сейчас. Вместе с МА разбираем примерчик из собеса прошлого набора, чтобы вы оценили свои силы!

Смотрим! Решаем! https://youtu.be/DxfV8JdqQlo

Задача Яндекса.
Новая задача в Яндексе, которая уже попалась 5 моим знакомым. Советую, если в скором времени собираетесь в Яндекс, разобрать эту задачу.

Вот сама задача
Если вкратце то дается набор точек на плоскости и спрашивается, правда ли существует линия параллельная оси 'y', которая симметрично отражает данные точки.

Решение также по ссылке можно увидеть.

Вопросы, которые задают на собеседование:

1) Вот вы поняли что координата прямой через которую делается отражения имеет координату (minX + maxX) / 2, но почему этого деления нету в коде ?

Тут два варианта, либо вам придется писать деление на два в вашем коде и работать с double (может дробями) либо не делить.... Но если вы решаете не делить то надо объяснить почему.
А ответ следующий, если прямая через которую делаем отражение имеет координату s, тогда точка (x, y) отразится в точку (2*s-x, y).
Заметим что мы s умножаем на два!!!
Так что мы могли бы взять s = (minX + maxX) и говорить что точка отражается на позицию (s-x, y).

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

2) В Яндексе скорее всего попросят учитывать повторы, то есть если две точки лежат на позиции [-1, 1] и одна точка на позиции [1, 1] то ответ False, так как одна точка останется без пары. Вам придется использовать хеш-таблицу вместо set чтобы учесть такой кейс.

Готовиться в ШАД стало ещё проще: специально для вас подготовили разбор экзамена 2024 года! Смотрим, решаем и голосуем за публикацию на Хабре, если хотите больше таких статей!

https://habr.com/ru/articles/841858/

Т-банк открыл контест на стажировку осень-зима. Задания уже лежат тут, там же их можно обсудить вместе с админом. И конечно разбор нового контеста будет на наших курсах, так что присмотритесь к ним.

Стажировка в Т-банке - самая крупная стажировка после Яндекса по количеству мест. В целом решает не сколько баллы за экзамены, сколько "ваш социальный рейтинг", анкета — подробней смотрим здесь. После контестов зовут на собес: он дикая халява, если хоть немного пробовали вкатиться в специальность.

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

Назовем число хорошим, если число является составным, а количество делителей простое число.
Найти количество хороших чисел на диапазоне [l, r] 1<=l<=r<=10^14.

Решение:
Заметим, что число n называется хорошим, если n=p^a
Где p-простое число и a>1.

Для тех кто не знают тут надо смотреть формулу количество делителей, и подумать в каких ситуациях это выражение простое.

Стоит обратить внимания, что a+1 должно быть простым числом.

Отсюда следует что p<=10^7. Так как a>1.
С помощью решето Эратосфена найдем все простые числа на отрезке [1, 1е7]
Переберем каждое простое число - так мы зафиксируем ‘p’. Осталось найти все такие ‘a’, что

l<=p^a<=r
a>1
a+1=простое число

Если вы будете перебирать ‘a’ в цикле (или раз за разом умножать переменную на p) то у вас будет переполнение типа и получите WA. Например возьмем p=1e7 когда будете возводить в третью степень произойдет переполнение. Да вы могли остановиться заранее и не возводить в степень, но как это понять ?

Нужно поступить иначе, давайте найдем максимальную степень b, что
p^b<=r, для этого мы просто будем делить r на p пока не станет равным нулю, от количество делений мы можем найти b.

Аналогично найдем максимальную степень d, что
p^d<=l-1.

Получаем, что нас интересует в качестве степень ‘a’ все простые числа на [d+1, b]. Благо этот отрезок очень маленький и можно честно перебрать там, проверяю что число простое используя посчитанную решето.

ШОК! Админ надел платье, туфельки и пошел в офис Т-банка записывать свой тикток...

Распространяем: https://youtube.com/shorts/99VxC8WiaCo

Вот и разбор программирования на стажировку в Тинькофф! Обязательно делимся с друзьями. Очень понравилась ваша активность по прошлому видосу, товарищи, поэтому ждём 9 тыс просмотров на ютуб ролике и выкладываем разбор контеста на стажировку в Яндекс.

Смотрим! Смотрим! https://youtu.be/xwc1gLcCras

Задача Яндекса.
За последние два месяца эта задача попадалась много раз.

Дается массив из 0 и 1.
Гарантируется что есть хотя бы один ноль и одна единица. Найти такую позицию нуля, что ближайшее расстояние до единицы максимальная.

Решение:

Во первых поймем, что между двумя единицами нужно выбрать позицию посередине.
…1,0,0,0,0,0,1,…..
Значит мы можем идти слева направо, хранить в переменной last последнюю позицию единицы. Если мы сейчас стоим в позиции i и в этой позиции единица, тогда мы пытаемся поставить единицу в позицию (i+last)/2, расстояния до ближайшей единицы равно min( (i+last)/2-last, i- (i+last)/2)
обновляем ответ если это расстояние больше чем нынешний ответ.

Остается случай, когда последовательность начинается с нуля или заканчивается нулем.

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