Задачи для курса "Алгоритмы и структуры данных" 2019 года курса в Технополис.
Форкните проект, склонируйте и добавьте upstream:
$ git clone [email protected]:<username>/2019-ads.git
Cloning into '2019-ads'...
...
$ git remote add upstream [email protected]:polis-mail-ru/2019-ads.git
$ git fetch upstream
From github.com:polis-mail-ru/2019-ads
* [new branch] master -> upstream/master
В общем случае часть задач будет с e-olymp, и проверяться будет средствами этой системы. Но также возможны и задачи, тесты на которые будут оформлены в нашем репозитории.
Первым делом регистрируемся на e-olymp.
Для каждого нового домашнего задания заводим новую ветку в своем репозитории.
Например, домашнему заданию после первой лекции будет соответствовать ветка part1.
Создаем ее в локальном репозитории
$ git checkout -b part1
Исходники решений добавляются в java-пакет ru.mail.polis.ads.<partX>.<username>, где username - логин на Github.
Решение каждой задачи - отдельный Java-класс в этом пакете.
Можно воспользоваться классом ru.mail.polis.ads.SolveTemplate, в котором остается реализовать лишь метод solve.
После того, как решения будут доведены до рабочего состояния (все тесты будут проходить),
можно коммитить, пушить и создавать pull request в polis-mail-ru/2019-ads.
В самом PR либо в его описании, либо в комментариях к каждому классу-решению
нужно добавить ссылку на submission в e-olymp, где видно, что все решение прошло все тесты.
Эти ссылки имеют вид "https://www.e-olymp.com/ru/submissions/5707028".
Все обсуждения решения происходят в рамках комментариев к PR (в противном случае мы зафлудим общий чатик и запутаемся окончательно :))
Прогон тестов будет осуществляться системами continuous integration, например, TravisCI и/или CircleCI. Тесты в этих системах будут исполняться при созданни PR и при добавлении новых коммитов. В итоге у PR должна появиться зеленая галочка, говорящая об успешном прохождении тестов.
Задачи с e-olymp.com
- https://www.e-olymp.com/ru/problems/1 - проверим систему
- https://www.e-olymp.com/ru/problems/1087 - динамика
- https://www.e-olymp.com/ru/problems/1090 - динамика
- https://www.e-olymp.com/ru/problems/1618 - динамика
- https://www.e-olymp.com/ru/problems/6125 - очередь
За каждое полностью рабочее решение дается 2 балла (да, даже за первую задачу).
Задачи с e-olymp.com
- https://www.e-olymp.com/ru/problems/15 - динамика
- https://www.e-olymp.com/ru/problems/262 - динамику
- https://www.e-olymp.com/ru/problems/3837 - стек/очередь
- https://www.e-olymp.com/ru/problems/5327 - скобочки со стеком
- https://www.e-olymp.com/ru/problems/6124 - стек
За каждое полностью рабочее решение дается 2 балла.
Задачи с e-olymp.com
Дэдлайн - 22.10
- https://www.e-olymp.com/ru/problems/3738 - Простая сортировка
- https://www.e-olymp.com/ru/problems/1462 - Хитрая сортировка
- https://www.e-olymp.com/ru/problems/4741 - Сортировка пузырьком
- https://www.e-olymp.com/ru/problems/4827 - k-тая порядковая статистика
- https://www.e-olymp.com/ru/problems/4037 - Сортировка слиянием
В задачах нельзя использовать Arrays.sort()/Collections.sort().
На то они и задачи на сортировку, чтобы мы сами пописали эти сортировки.
Задачи с e-olymp.com
Дэдлайн - 29.10
- https://www.e-olymp.com/ru/problems/3737 - Куча ли?
- https://www.e-olymp.com/ru/problems/4039 - Хипуй
- https://www.e-olymp.com/ru/problems/4074 - Найти медиану 2
- https://www.e-olymp.com/ru/problems/4261 - Количество инверсий
- https://www.e-olymp.com/ru/problems/1457 - Станция "Сортировочная"
- https://www.e-olymp.com/ru/problems/9016 - Бинарный поиск
- https://www.e-olymp.com/ru/problems/5149 - Коровы - в стойла
Дэдлайн - 5.11
- https://www.e-olymp.com/ru/problems/3968 - Квадратный корень
- https://www.e-olymp.com/ru/problems/3969 - Дипломы
- https://www.e-olymp.com/ru/problems/264 - Наибольшая последовательнократная подпоследовательность
- https://www.e-olymp.com/ru/problems/991 - Шаблон и слово
- https://www.e-olymp.com/ru/problems/2169 - Перестановки
Дэдлайн - 12.11
Реализация АВЛ-дерева.
Дан интерфейс двоичного дерева поиска с поддержкой упорядоченных операций ru.mail.polis.ads.bst.Bst.
Решения с использованием библиотечных структур данных
(TreeMap, которая на самом деле не на АВЛ работает) не принимаются.
Основные методы:
Value get(Key key)- возвращает значение по заданному ключу илиnull, если такого ключа нетvoid put(Key key, Value value)- сохраняет заданное значение по указанному ключуValue remove(Key key)- удаляет заданный ключ (и связанное с ним значение, возвращая его)
Методы, основанные на порядке ключей:
Key min()- возвращает минимальный ключ илиnull, если структура пустаяValue minValue()- возвращает значение, ассоцирированное с минимальным ключом, илиnull, если структура пустаяKey max()- возвращает максимальный ключ илиnull, если структура пустаяValue maxValue()- возвращает значение, ассоцирированное с максимальным ключом, илиnull, если структура пустаяKey floor(Key key)- возвращает максимальный ключ, меньший либо равный заданному, илиnull, если такого нетKey ceil(Key key)- вовзращает минимальный ключ, больший либо равный заданному, илиnull, если такого нет
Служебные методы:
int size()- вовзращает количество узлов в деревеint height()- возвращает высоту дерева (максимальная длина пути от корня до листа)
Дэдлайн - 25.11
N.B. Pull-реквесты нужно делать в ветку red-black.
Реализация Left-Leaning Red-Black Tree.
Дан интерфейс двоичного дерева поиска с поддержкой упорядоченных операций ru.mail.polis.ads.bst.Bst.
Решения с использованием библиотечных структур данных
(TreeMap, которая на самом деле работает на красно-черных деревьях из Кормена) не принимаются.
Основные методы:
Value get(Key key)- возвращает значение по заданному ключу илиnull, если такого ключа нетvoid put(Key key, Value value)- сохраняет заданное значение по указанному ключуValue remove(Key key)- удаляет заданный ключ (и связанное с ним значение, возвращая его) (делается во втором этапе, после лекции)
Методы, основанные на порядке ключей:
Key min()- возвращает минимальный ключ илиnull, если структура пустаяValue minValue()- возвращает значение, ассоцирированное с минимальным ключом, илиnull, если структура пустаяKey max()- возвращает максимальный ключ илиnull, если структура пустаяValue maxValue()- возвращает значение, ассоцирированное с максимальным ключом, илиnull, если структура пустаяKey floor(Key key)- возвращает максимальный ключ, меньший либо равный заданному, илиnull, если такого нетKey ceil(Key key)- вовзращает минимальный ключ, больший либо равный заданному, илиnull, если такого нет
Служебные методы:
int size()- вовзращает количество узлов в дереве
Ко всему прочему добавляется
Value remove(Key key)- удаляет заданный ключ (и связанное с ним значение, возвращая его)
Дэдлайн - 4.12
N.B. Pull-реквесты нужно делать в ветку hash.
Реализация HashTable с разрешением коллизий методом цепочек.
Дан интерфейс хеш-таблицы ru.mail.polis.ads.hash.HashTable.
Решения с использованием библиотечных структур данных (java.util.HashMap/Hashtable) не принимаются.
Основные методы:
Value get(Key key)- возвращает значение по заданному ключу илиnull, если такого ключа нетvoid put(Key key, Value value)- сохраняет заданное значение по указанному ключуValue remove(Key key)- удаляет заданный ключ (и связанное с ним значение, возвращая его)
Служебные методы:
int size()- вовзращает количество ключей
Дэдлайн - 12.12
- https://www.e-olymp.com/ru/problems/1948 - Топологическая сортировка
- https://www.e-olymp.com/ru/problems/2022 - Циклы в графе
- https://www.e-olymp.com/ru/problems/1453 - Форд-Беллман
- https://www.e-olymp.com/ru/problems/4856 - Кратчайший путь
- https://www.e-olymp.com/ru/problems/4853 - Кратчайший путь
Дэдлайн - 27.12
- https://www.e-olymp.com/ru/problems/1943 - Мосты
- https://www.e-olymp.com/ru/problems/3835 - Минимальный каркас
- https://www.e-olymp.com/ru/problems/325 - Опасный маршрут
- https://www.e-olymp.com/ru/problems/1947 - Конденсация графа
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent