Задачи с отбора на стажировку в Tinkoff (разбор контеста)

В этом видео я разобрал задачи, которые были на отборе на стажировку в Tinkoff в сентябре 2023 года.
Телеграм - t.me/wilcodit_school
00:00 - Вступление
00:23 - О контесте
01:08 - Задача 1
03:22 - Задача 2
05:25 - Задача 3
09:33 - Задача 4
12:58 - Задача 5
22:04 - Задача 6

[@korrex1570]

спасибо, очень полезный материал!!!!!

[@burundukoff8450]

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

[@user-il2rm5ls1r]

А была ли на этом отборе тестирующая система? А то весной вроде бы не проверялись задачи, только когда уже все сдали

[@oldudot6940]

3 задачу можно же решить без сортировки за o(n), используя один проход и словарь. Можно воспользоваться тем, что если числа в последовательности которую нужно получить идут не по порядку, то мы не сможем отсортировать по возрастанию, а с помощью словаря проверять имеются ли нужные цифры в исходной и целевой последовательности.

[@wilcodit]

Кстати да, так тоже можно. Но словарь это n log n, тогда надо хештабличку какую-нибудь

[@skylinerus3181]

Что-то я так и не пон, как сделать без сортировки с одним проходом :(

[@user-il2rm5ls1r]

На пяткю придумал решение через СНМ, по идее работает за почти линейное время от количества рёбер

[@GreatVolcano]

4 задача через мемоизацию проще всего. я вот сейчас глянул - дак мой алгоритм уже виснет при 5 (не говоря про 10 чисел), добавил мемоизацию и вуаля, считает всё норм даже для 10

[@memeger89]

Есть код 5й задачи?

[@wilcodit]

Жду тебя в своей телеге: t.me/wilcodit_school

[@user-zi5vk7zi4d]

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

[@goolkinsnose3936]

4 задача - см. "задача о рюкзаке" методом динамического программирования. о(n*вместимость кошелька)

[@user-il2rm5ls1r]

Не пройдет по времени, n слишком большое

[@whooper2357]

А задачи на фронтенд такие же были?

[@VladislavMalcev-ld8ku]

Да

[@user-mx3qc5ze5j]

Интересная идея в 5 задаче. Я бы решал напрямую. Воспользовался бы тем, что в минимальный остов является остовом с минимальным весом самого тяжелого ребра. Таким образом надо из всех минимальных остовов выбрать самое тяжелое ребро. Алгоритмом Крускала проходимся по ребрам в сортированном порядке и находим длину последнего добавленного для получения минимального остова. Ответ - эта найденная длина минус один.

[@wilcodit]

Да, похоже на правду, только видимо надо искать максимальные остовы и среди них брать минимальное ребро - 1

[@user-mx3qc5ze5j]

@@wilcoditДа, конечно :)

[@tirsky]

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

[@deathbell616]

Получается, нужно учиться в вузе было, а не прогуливать

[@y.saunders7442]

Сколько не смотрел на эти таски, все они походят на стандартные "вузовские" задачи, 80% из них завязаны на теории графов, знании алгоритмов, особенно greedy и т.п. Можно решить и без знания алгоритмов, достаточно понимания, в какую сторону копать, благо есть гугл, он алгоритм подскажет, а вот без мат. базы будет трудно: у человека, не знающего теории графов, мысль в эту сторону и не пойдёт. С чем согласен - с работой они никак не пересекаются. Сдавать экзамен по кодингу для Intern QA, которому на старте придётся проводить обычный мануал по паттерну, и которому даже не всю динамическую документацию писать доверят - маразм. Для грамотного middle+ на высокую вилку - имеет место.