Яндекс.Алгоритм 2017, третий отборочный раунд: разбор (с челленджами и свистелками)

Правка ru1, от Endagorion, 2017-06-06 16:14:50

На этот раз я решил попробовать писать разбор в спойлерах, как уже делал кое-кто из авторов. Буду рад вашим комментариям о том, стало ли лучше.

Задача A. Сдвиги

Темы: динамическое программирование.

Общий комментарий: это первая среди "сложных" задач контеста. В ней можно помочь хорошее знакомство со стандартными задачами на ДП, но довести решение до финального правильного вида все равно непросто.

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

Как решать такую задачу?
Что меняется, если сдвигать можно только вправо?
Challenge (трудный/научная проблема):

Задача B. Число в подарок

Темы: жадность.

Общий комментарий: задача на аккуратность. Требуется учесть много мелких деталей, но в остальном задача вполне решаемая.

Решение: Раз мы максимизируем число, важнее всего понять, насколько большую цифру можно поставить на первое место. Обозначим d первую цифру n.

Есть несколько случаев...
В некоторых из них легко получить сразу весь ответ...
А в остальных надо разбираться подробнее...
Что делать?
Итоговая сложность...
Все еще WA?
Challenge (легкий):

Задача C. Рекуррентный генератор

Темы: хэширование/строковые алгоритмы.

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

Решение: Для начала поймем, почему последовательность Фибоначчи, определенная в условии, не является 1-рекуррентной.

Предположим обратное...
Можно ли сделать из этого критерий для k = 1?
Можно ли обобщить этот критерий для любого k?
Как проверить, есть ли противоречивые участки длины k?
Наконец...
Challenge (легкий/упражнение):

Задача D. Торговля

Темы: жадность, сортировка, реализация.

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

Решение:

Можем ли мы решить задачу, если нам сразу известны стоимости d с точки зрения продавца?
Что делать, если значения d неизвестны?

На этом описание решения по большому счету заканчивается.

Однако, остаются мелкие детали...
Challenge (средний):

Задача E. Прогулка по Манхэттену

Темы: математика, кратчайшие пути в графе.

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

Решение:

Это же стандартная задача?
Это слишком муторно, можно ли проще?
Challenge (вроде несложно):

Задача F. Игра на дереве

Темы: игры, графы, математика.

Общий комментарий: сперва эта задача казалась мне простой, и я ожидал по ней больше правильных решений. Каждая идея по отдельности достаточно несложная, и кода в итоге совсем чуть-чуть. Оказалось, что распутать задачу целиком под силу немногим. Какие у вас впечатления от задачи? =)

Решение:

Шаг 1
Шаг 2
Шаг 3
Финиш?
Challenge (ну такое):

Буду рад услышать любые ваши мнения в комментариях. Спасибо за участие!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Endagorion 2017-06-06 16:14:50 23910 Первая редакция перевода на Русский
en10 Английский Endagorion 2017-06-04 17:07:12 26 (published)
en9 Английский Endagorion 2017-06-04 17:05:38 33
en8 Английский Endagorion 2017-06-04 17:04:45 10870 Tiny change: 'ler>\n\n\n</spoiler>\n\n#### P' -> 'ler>\n\n\n#### P'
en7 Английский Endagorion 2017-06-04 16:18:23 5367 Tiny change: 'iler>\n\n<spoil' -> 'iler>\n\n</spoiler>\n\n\n<spoil'
en6 Английский Endagorion 2017-06-04 13:51:43 1634 Tiny change: '>\n$O(n^2 log n)$ ti' -> '>\n$O(n^2 \log n)$ ti'
en5 Английский Endagorion 2017-06-04 13:15:00 22 Tiny change: '0^9 + 7$) numbers that cons' -> '0^9 + 7$) positive numbers are there that cons'
en4 Английский Endagorion 2017-06-04 13:14:11 506
en3 Английский Endagorion 2017-06-04 13:08:22 2456 Tiny change: '### Proble' -> '#### Proble'
en2 Английский Endagorion 2017-06-04 11:50:31 6467 Tiny change: 'r, to any $X$ we can pr' -> 'r, to any X we can pr'
en1 Английский Endagorion 2017-06-04 10:31:12 960 Initial revision (saved to drafts)