Считаем, сколько заплатить в магазине и проверяем поле морского боя: разбор задач для разработчиков C#, iOS и Android

Привет, Хабр! Я Ани, отвечаю в Ozon Tech за обучение.

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

Для справки: Route 256 — бесплатные курсы для мидл разработчиков от опытных инженеров Ozon Tech. В мае этого года мы запустили пять направлений: Go, QA, C#, iOS, Android. Это наш второй набор, сам проект стартовал осенью прошлого года.

Контест нам заменяет скрининг — мы проверяем технические навыки и опыт работы будущих участников, так как курсы рассчитаны на мидлов.

Ранее мы публиковали разбор задач по направлениям Go и QA (раз, два), пришло время поделиться задачами для C#, iOS (Swift) и Android (Kotlin, Java).

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

Задача «Сумма к оплате»

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

Требуется посчитать, сколько потребуется заплатить суммарно за весь поход в магазин при условии, что в магазине проводится акция — «купи три одинаковых товара и заплати только за два».

Решение

План решения данной задачи можно сформулировать следующим образом:

Первым делом требуется посчитать количество товаров, имеющих одинаковую цену — обозначим эту величину для некоторой стоимости за $am_{cost}$ . Сделать это можно несколькими способами, самым простым из них является складывание всех цен товаров в структуру данных, предоставляющую быстрое изменение элемента и последующий проход по полученному контейнеру.

Примеры такого контейнера в разных языках программирования

Map в Kotlin, Dictionary в Swift, Dictionary в C#.

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

Затем нам просто требуется посчитать $\sum\limits_{cost = 1}^{max_{cost}} \left(am_{cost} - \cfrac{am_{cost}}{3}\right) \cdot cost$ , это и есть ответ.

Время работы и память

Асимптотика такого решения — $O(n_{sum} \cdot \log{n_{sum}})$ где $n_{sum}$ — сумма количество купленных товаров по всем тестам, дополнительной памяти требуется линейное или константное количество в зависимости от реализации.

Разбор задачи «Электронная таблица»

Задана прямоугольная таблица $n \times m$ из чисел. Требуется обработать запросов: примените стабильную сортировку по неубыванию к столбцу .

Требуется вывести таблицу после обработки всех запросов.

Решение

В данной задаче можно было сдать решение в лоб:

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

Примеры стабильной сортировки в языках программирования

OrderBy в C#, sort() (начиная с Swift 5), sortedWith в Kotlin.

Время работы и память

В данной задаче проходили решения с любой разумной асимптотикой, но например решение описанное выше работает за $O(t \cdot k \cdot m \cdot n \cdot \log{n})$ .

Дополнительной памяти требуется константное количество.

Разбор задачи «Подсистема регистрации»

На вход подаются логинов, для каждого логина вам нужно сказать, можно ли его зарегистрировать. Логин должен соответствовать следующим правилам:

Логин — это последовательность из латинских букв в любом регистре, цифр и символов «_» или «-» (подчеркивание и дефис).
Логин не должен начинаться с дефиса.
Логин должен иметь длину от до символов.
Логины, которые отличаются только регистром, считаются одинаковыми.

Решение

Решение данной задачи состоит из двух основных идей:

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

Регулярное выражение, рещающее задачу:

[0-9a-zA-Z_][0-9a-zA-Z_-]{1, 23}

Вторая часть решения — проверка логина, на то что раньше его еще не было. Для этого нам нужно привести логин в общий вид (например в нижний регистр), а затем использовать структуру, которая умеет быстро добавлять элемент и проверять элемент на наличие в множестве.

Подходящие структуры в разных языках

Set в C#, Set в Kotlin, Set в Swift.

Время работы и память

Асимптотика такого решения $O(logins_{sum} \cdot \log{(logins_{sum})})$ , дополнительной памяти требуется линейное количество.

Разбор задачи «Адресная книга»

Дается журнал звонков — набор записей (имя звонившего, телефон звонившего). Записи даны в хронологическом порядке от наиболее ранней к самой последней. Требуется восстановить для каждого звонившего 5 последних его номеров телефона.

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

Решение

Заведем словарь из звонившего в очередь его номеров телефонов. Затем проходимся по набору всех записей. Для каждой записи проверяем, верно ли, что у звонившего в очереди уже есть этот номер телефона. Если это так, то просто удаляем его из очереди и кладем заново в конец очереди. Если же этого номера в очереди нет, то просто добавляем номер в очередь и в случае необходимости (число элементов в очереди больше 5) удаляем элемент из очереди.

В конце просто проходимся по словарю в лексикографическом порядке и выводим ответ.

Время работы и память

Время работы — $O(n_{sum} \cdot \log{n_{sum}})$ , где $n_{sum}$ — сумма количеств записей по всем тестам, такое время работы обуславливается тем, что очередь у нас всегда размера не более 5, а следовательно все операции с ней работают за константное время.

Дополнительная память в данном случае будет линейной.

Разбор задачи «Система продажи билетов на поезда»

Есть купе, пронумерованных от до , в каждом купе два места, поступают запросы трех видов:

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

Если в купе освободили все места — то оно также считается свободным.

Решение

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

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

Пример подходящей структуры

SortedSet в C#, sortedSetOf в Kotlin.

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

Время работы и памяти

Для каждого запроса мы требуем $O(\log(places))$ времени (поиск/удаление/вставка в выбранную нами структуру или словарь), итого суммарное время работы — $O(q_{sum} \cdot \log(places))$ , где $q_{sum}$ — суммарное количество запросов.

Также нам требуется дополнительной памяти для хранения всех мест и всех купе.

Разбор задачи «Многомодульный проект»

Есть модулей, для каждого известны зависимости, которые нужны для его установки. Есть запросов — на каждой запрос нужно установить какой-то модуль, предварительно поставив все его зависимости, игнорируя уже установленные модули.

Решение

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

Рисунок связей для первого теста из условия:

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

Например, когда на рисунке выше вызывается установка модуля web, то наша функция сначала попытается установить model, установит для нее database и utils, а затем точно также попробует установить commons и получит нужный порядок установки.

Пример работы функции в рисунках

На первом шаге наша функция начнет рассматривать модуль web

На втором шаге мы пометим, что мы пока не можем установить модуль step, так как он зависит от других модулей, и пойдем в модуль model.

На третьем шаге мы пометим, что мы пока не можем установить модуль model, так как он зависит от других модулей, и пойдем в модуль database.

На четвертом шаге мы установим модуль database. Поймем что мы все равно не можем установить модуль model, так как он зависит от других модулей, и пойдем в модуль utils.

На шестом шаге мы установим модуль model, так как все его зависимости установлены

На седьмом шаге мы попробуем установить common

На восьмом шаге мы попробуем установить json

На девятом шаге мы установим модуль json

На десятом шаге мы установим модуль common

В итоге мы установим все нужные нам модули

Пояснение к рисункам выше:

Красным будет выделен элемент, который мы уже установили.
Синим — элемент который мы пытались установить, но перешли в его зависимости.
Зеленым — элемент который мы пытаемся установить сейчас.
Не выделены цветом — элементы, которые мы вообще не трогали.

На самом деле такое решение называется топологической сортировкой.

Время работы и памяти

Каждый модуль мы не можем установить более 1 раза, а также каждую зависимость мы не можем посмотреть более 1 раза на каждый запрос. А следовательно наше решение работает за $O(m \cdot dependecies)$ .

Дополнительная память требуется только для рекурсии, которая в худшем случае просто обойдет все модули, а следовательно нам требуется не более $O(n_{sum})$ дополнительной памяти.

Разбор задачи «Г-образный морской бой»

Есть поле $n \times m$ , некоторые клетки свободны, они обозначаются символом «.», а некоторые заняты — «*». Корабль — Г-образная фигура размера 1, 3, 5 или 7 точек.
Ниже можно видеть все примеры кораблей:

 ...    ....    .....    ......  .*.    .**.    .***.    .****.  ...    .*..    .*...    .*....         ....    .*...    .*....                 .....    .*....                          ......

Корабли можно вращать

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

Решение

Данная задача — задача в основном на реализацию, так как требуется просто реализовать, то что спрашивается в условии — то есть просто проходить по полю и явно убирать корабли, если они размещены правильно. Но есть несколько способов упростить себе решение:

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

 ...    ....    .....    ......  .*.    .**.    .***.    .****.  ...    .*..    .*...    .*....         ...X    .*.XX    .*.XXX                 ...XX    .*.XXX                          ...XXX X — любой символ.

2. Так как корабли можно вращать, то нужно было сделать не 4 шаблона, а целых 16, но так как в шаблонах было бы легко запутаться, то можно просто написать функцию rotate, которая будет вращать шаблон на 90 градусов и таким образом получить все нужные нам шаблоны.

Время работы и памяти

Так как в каждую клеточку поля мы пытаемся подставить корабль, напрямую проверяя кусок поля с шаблоном, то данное решение будет требовать $O(templates \cdot n \cdot m \cdot template_{size})$ , где $template_{size}$ — размер шаблона, — количество шаблонов. Так как $size_{template}$ и — константы, то в итоге мы получили решение за $O(n \cdot m)$ .