В конкурсе было 4 задачи. Мне удалось решить 3 задачи полностью и 4-ю - частично. Набор задач был намного лучше, чем последний конкурс Code Jam to I / O для женщин. У него была одна специальная проблема, проблема динамического программирования, проблема случайного блуждания и довольно интересная интерактивная задача (моя любимая).
Начнем с обсуждения 4 задач! Уже существует официальный анализ набора проблем, но здесь я пытаюсь дать представление о том, как я подошел к проблемам. Я удалил надуманную историю из всех вопросов, и мы сосредоточимся только на основной задаче.
1. Выход из сетки
Описание проблемы -
Есть сетка размером R x C, в которой каждый игрок находится в одной из ячеек. Игрок может выбрать только одно из четырех направлений (север, юг, восток, запад), чтобы перейти от текущей ячейки к следующей. Каждый игрок продолжает движение, пока не найдет выход из сетки или не сделает R x C ходов, не убегая.
Нам нужно найти направление, выбранное в каждой ячейке, так, чтобы ровно K игроков могли убежать или сказать, невозможно ли это.
Решение -
Мой общий подход к проблемам с сеткой состоит в том, чтобы уменьшить ее до одного измерения (массива). Обычно решение для сетки является расширением решения для массива. То же самое и здесь!
Мы будем рассматривать только 2 направления (восток и запад). Рассмотрим сетку размером 1 x 1 с одним игроком, тогда игрок может выбрать любое из двух направлений, чтобы выйти из сетки. Следовательно, для K = 1 это возможно, но для K = 0 ответ невозможен.
Предположительно, у нас есть сетка размером 1 x 2, тогда игрок, проживающий в (1, 1), может двигаться на восток, чтобы достичь (1, 2), в то время как игрок в (1, 2) имеет 2 направления на выбор. Если игрок 2 попытается двинуться на запад, оба игрока никогда не смогут выбраться из сетки.
Следовательно, при K = 1 это невозможно.
Если мы примем сетку размером 1 x n, то все игроки могут выйти из сетки, пока у нас не появится один игрок, который попытается заблокировать других, предшествующих ему. Следовательно, если мы предположим, что все игроки от (1,1) до (1, nk-1) движутся слева направо, то если игрок в (n - k) -й ячейке пытается двигаться справа налево, тогда все игроки до него никогда не смогут вырваться из сетки. Следовательно, мы можем сделать вывод, что ровно для K = n - 1 игроков «невозможно» выбрать путь так, чтобы все они могли сбежать.
Вышеупомянутый подход может быть обобщен и для двухмерной сетки (с 4 направлениями).
Представьте себе, что вы следуете зигзагообразным путем, чтобы добраться от (1, 1) до (r, c), так что мы начинаем с (1,1) и движемся на восток, чтобы достичь (1, n), затем идем на юг, чтобы достичь (2, n) и двигайтесь дальше влево, чтобы добраться до (2, 1). Таким образом, если игрок перейдет от (1, 1) к (r, c), любой игрок, следующий по его пути, сможет выйти из сетки.
2. Почтовые посылки
Описание проблемы -
Нам дан массив размера N. Нам нужно разделить массив на максимальное количество смежных желаемых сегментов, чтобы никакие 2 сегмента не имели общих элементов, кроме концов сегмента. Каждый желаемый сегмент должен обладать одним из двух следующих свойств:
- Существует 3 различных индекса, таких что i ‹j‹ k, A [i] ›A [j] и A [k]› A [j]
- Существует 3 различных индекса, таких что i ‹j‹ k, A [i] ‹A [j] и A [k]‹ A [j]
Данный исходный массив следует одному из свойств.
Решение -
Разделение массива на сегменты, обладающие определенным свойством, - довольно популярные проблемы. Основная проблема обычно заключается в свойствах каждого сегмента. Так что давайте сначала сосредоточимся на нем.
Мы можем заметить, что если желателен подмассив A [i… j], то также желателен подмассив, содержащий его. Используя вышеприведенное наблюдение, мы можем сделать вывод, что для того, чтобы сделать A [i… j] желательным, необходимо, чтобы выполнялось любое из следующих двух условий:
- Желателен собственный подмассив A [i ... j].
- У нас есть индекс p такой, что: i ‹p‹ j, A [i] ‹A [p] и A [p]› A [j],
A [i] › A [p] и A [p] ‹A [j].
Используя это, мы можем вычислить, желателен ли каждый сегмент от i до j в O (N * N).
Затем мы можем применить динамическое программирование для вычисления максимального количества сегментов, на которые мы можем разделить исходный массив. Пусть dp [i] обозначает максимальное количество желаемых сегментов, которые мы можем разделить на A [1… i]. Мы можем вычислить dp [i] в O (N), если у нас есть dp [j] для всех j ‹i. См. Фрагмент кода ниже для получения дополнительных сведений.
Бонус: вы можете придумать что-нибудь лучше, чем O (N * N)? (Подумайте о каком-нибудь жадном подходе)
3. Ходьба во сне
Описание проблемы -
У нас есть двумерная сетка с бесконечным числом элементарных ячеек. Человек P в настоящее время находится в элементарной ячейке с координатами (X, Y), то есть в ячейке X столбцов к востоку от и Y строк к северу от (0, 0). P может заставить случайный отряд двигаться в любом из направлений - север, юг, запад, восток. Для каждого хода мы можем заблокировать 2 ячейки в 2D-сетке, где P не может двигаться. Мы должны найти минимальное ожидаемое количество ходов, сделанных P, чтобы достичь (0, 0).
Решение -
Считая X и Y неотрицательными (без ограничения общности) и F (X, Y) ожидаемым количеством ходов, сделанных P.
Есть два возможных случая для положений (X, Y) -
- X! = 0 и Y! = 0
- X = 0 or Y = 0
Случай 1: мы можем разместить блоки на (X, Y + 1) и (X + 1, Y) так, чтобы P был вынужден двигаться в направлении к исходной точке (запад или юг). Следовательно, P может выбрать два из четырех направлений с равной вероятностью.
1. F(X, Y) = ½ F(X-1, Y) + ½ F(X, Y-1) + 1
Случай 2: Если (X, Y) лежит на оси Y, тогда блоки должны быть размещены на (0, Y + 1) и (-1, Y) так, чтобы P мог перемещаться либо на восток, либо на юг с равной вероятностью.
2. F(0, Y) = ½ F(0, Y-1) + ½ F(1, Y) + 1
Точно так же мы можем вывести функцию для оси x.
Повторение для случая 1 выглядит нормально, но для случая 2 - неправильно. Я имею в виду, что это правильно, но кажется, что F (0, Y) зависит от F (1, Y). Но F (1, Y) зависит от F (0, Y). Итак, из-за этой круговой зависимости нам нужно изменить повторение для F (0, Y).
Мы знаем это -
3. F(1, Y) = ½ F(0, Y) + ½ F(1, Y-1) + 1
Подставим уравнение 3 в уравнение 2.
4. F(0, Y) = ⅔ F(0, Y-1) + ⅓ F(1, Y-1) + 2
Теперь мы можем использовать уравнения 1 и 4, чтобы найти ожидаемые ходы для каждого X и Y.
4. Война слов
Описание проблемы -
Вы играете с роботом, состоящим из 10⁵ слов: набора всех пятибуквенных строк, состоящих из прописных английских букв от A до J включительно. Все слова имеют уникальный ранг, связанный с ними, и слово с более высоким рангом побеждает слово с более низким рангом, за тем исключением, что слово с наименьшим рангом превосходит слово с наивысшим рангом. Порядок рангов известен только роботу.
В игре действуют следующие правила:
- Ход 0: вы начинаете с названия слова W (0).
- Ход 1: Робот называет слово W (1). Если W (1) превосходит W (0), робот получает очко. Это продолжается; на ходу i активным игроком является вы, если i четное, или робот, если i нечетное. Активный игрок называет слово Wi и получает очко, если W (i) превосходит W (i-1). (Если два слова совпадают, балл не засчитывается.) Оценка не объявляется - в частности, вы не узнаете, набрано ли каждое из ваших слов балл! Это продолжается в общей сложности 201 ход.
На каждом ходу робот будет выбирать слово равномерно случайным образом из всех возможных слов, которые принесут очко на этом ходу, и независимо от всех его предыдущих вариантов слов.
Цель заключалась в том, чтобы набрать не менее 50 баллов (для более крупного случая).
Решение -
Во-первых, давайте проигнорируем исключение, когда слово с самым низким рейтингом (L) превосходит слово с самым высоким рейтингом (H).
Поскольку у нас нет порядка ранжирования, единственное, что мы можем сделать для W (0), - это выбрать его случайным образом. После этого робот называет W (1). Теперь единственная информация о W1, которую мы можем вывести, - это rank (W (0)) ‹rank (W (1)). Мы не можем точно сказать о ранге (W (1)), но мы можем кое-что сказать о его ожидаемом значении. Мы знаем, что робот выбирает слово равномерно наугад. Это означает, что E (rank (W (1))) = (100000 + rank (W (0))) / 2.
В качестве W (1) выберем W (2), которому робот назовет W (3). Теперь мы видим, что в конечном итоге мы получим H, но за сколько шагов? Очевидно, что в худшем случае примерно 100000, но мы хотим знать его ожидаемое значение. Потребуется 0 ходов, если нам посчастливится начать с H, 1 ход, если мы начнем на 1 ранг, ожидаемый 1 + ((0 + 1) / 2) = 1,5 хода, если мы начнем на 2 ранга, ожидаемый 1 ход. + ((0 + 1 + 1,5) / 3) = 1,8333… хода, если мы начинаем на 3 ранга, и так далее. Это гармонические числа. Так что, если бы мы начали случайным образом, нам потребуется примерно 12 шагов, чтобы достичь H.
Теперь, возвращаясь к исходной задаче (за исключением H и L), как мы узнаем, достигли ли мы H? Для этого нам нужно посмотреть на пару последовательных струн, на которых мы с роботом сыграли. Переход H-L будет происходить каждый цикл. Итак, если мы получим несколько экземпляров двух слов подряд, мы можем подумать, что это имеет переход H-L. Чтобы убедиться, что мы принимаем H и L правильно с высокой вероятностью, мы знаем, что если мы сыграем L, то робот выберет любое из 99999 слов случайным образом. Таким образом, мы можем с вероятностью сказать, что если мы получим повторяющийся экземпляр из 2 слов, за которым следует уникальный экземпляр в другом ходу, то мы можем сказать, что мы нашли H и L.
Найдя H и L, мы можем выиграть каждый второй ход. Поскольку у нас будет слово с более высоким рейтингом, чем то, что играет робот.
