Ученик 2022D

  • Фернандо Пенья
  • Давид Карденас
  • Регина Эспиноса
  • Мануэль Кота
  • Сантьяго Перейра
  • Эдуардо Мартинес
  • Хесус Мургия

Луны и зонтики

ОБЗОР

Проблема заключается в том, чтобы получить строку Cs и Js. Для каждого встречающегося «CJ» есть значение, которое необходимо заплатить, а также другое значение для каждого «JC» в строке. Кроме того, строка содержит вопросительные знаки (?), где наша программа должна решить, какую букву, C или J, нужно поставить, чтобы окончательная цена строки была наименьшей.

Входные данные содержат количество строк, которые должны быть оценены в первой строке. Все последующие строки имеют вид «X Y ‹string›», где X — цена «CJ», а Y — цена «JC». Алгоритм анализирует каждый символ в строке, сравнивая его с предыдущим символом, если только текущий символ не является вопросительным знаком (?). В этом случае он начинается со сравнения предыдущего и следующего символа.

Решение также учитывает случаи для набора тестов №3, в которых цены X и/или Y могут быть меньше нуля. В этом случае «CJ» и/или «JC» можно было бы предпочесть, а не избегать.

КОНТЕКСТ

Ситуация связана с художником Коди-Джамалом, чье абстрактное искусство имеет полумесяцы и зонтики, которые можно спутать с буквами C и J соответственно. Таким образом, любое произведение Коди-Джамала может быть выражено в виде цепочки C и J. Например, «CJCCJJC». В случае, если в последовательности появляется «CJ», необходимо выплатить авторские отчисления в размере X денежной суммы. Когда появляется «JC», цена роялти равна Y. Кроме того, некоторые строки являются неполными и содержат вопросительные знаки (?), которые символизируют пробелы, например, «CJ?CC?».

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

РЕШЕНИЕ

В общем, решение должно считывать каждую строку ввода и отправлять ее функции, которая проверяет каждый символ. Сравнивая каждый символ с его предыдущим, можно заметить, меняется ли последовательность с C на J или с J на ​​C. В случае, если анализируемый символ является вопросительным знаком (?), программа должна принять решение о какой символ лучше всего подходит для этого места и отправить его в цикл как «предыдущий символ». Результат этого жадного алгоритма записывается в выходной файл как «Case ##: ‹price›».

  • Решение жадного алгоритма

Когда программа впервые получает ввод, она вызывает итерирующую функцию. Для первого символа нет эффекта, так как нет предыдущего символа, с которым его можно было бы сравнить. Когда он доходит до второго символа, он сравнивается со своим предыдущим. Если они совпадают, то все в порядке, и цикл продолжается. Если они разные, то он проверяет, является ли предыдущий символом C. Если это так, то мы знаем, что имеем дело с «CJ», поэтому он добавляет единицу к счетчику для этого шаблона. В другом случае, если это J, к счетчику для шаблона JC добавляется единица.

Этого было бы достаточно, если бы не было пропущенных пробелов. Если программа встречает вопросительный знак (?), она сначала сравнивает предыдущий символ со следующим. Если тот, что сзади, и тот, что впереди, точно такие же, и ни одна из цен шаблона не ниже нуля, то он избегает любого изменения последовательности и размещает тот же самый символ. Например, если есть «C?C», а паттерн «CJ» или «JC» на самом деле стоит художнику денег, то наиболее удобным решением будет, если эти символы будут «CCC». Однако, если хотя бы одна из цен шаблона отрицательна (художнику платят), то последовательность может быть нарушена. Тем не менее, это было бы хорошо, только если сумма цен ниже нуля.

Каким бы ни был шаблон («C?C» или «J?J»), нарушение последовательности приведет к получению последовательности «CJ» и «JC». Следовательно, этим ходом он поднимет оба счетчика на один. Таким образом, если цена X плюс цена Y дают число меньше нуля, это означает, что мы действительно хотим, чтобы это произошло. Однако, даже если одна из цен, X или Y, ниже нуля, сумма не обязательно будет такой. Вот почему решение должно проверять, является ли эта сумма отрицательной или нет, прежде чем принимать решение.

С другой возможностью встретить вопросительный знак (?) в середине последовательности гораздо проще: когда предыдущий и последующий символы различны. В этом случае изменение последовательности произойдет независимо от того, что произойдет. Возьмем, к примеру, последовательность «C?J». Если он поместит C, у него будет шаблон CJ. Но это также произойдет, если он поместит J. Это повлияет только на то, как скоро в последовательности появится шаблон, но счетчик все равно будет расти. Таким образом, он может просто сделать это и перейти к следующему символу.

Исключения происходят в начале и в конце строки ввода. В конце проще, так что давайте начнем с этого (иронично). В этом случае нет «следующего символа», а значит программа будет иметь контроль над решением создавать шаблон или нет. Проверив предыдущий символ, он узнает, является ли потенциальный шаблон «CJ» или «JC». Если этот паттерн имеет отрицательную цену, то он предпочитает изменение, так как это означает зарабатывание денег. Однако, если цена является положительной величиной, она избегает размещения того же символа, что и предыдущий.

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

Если ввод начинается с одного или нескольких вопросительных знаков (?), то программа переходит к специальной функции, которая сначала подсчитывает, сколько пробелов осталось перед следующей C или J. Если обе цены шаблона являются положительными величинами, программа избегает создавая любые шаблоны, и просто считает эти пробелы заполненными тем же символом, который он впервые встречает после вопросительных знаков (?). Однако, если одна из цен отрицательна и их сумма также отрицательна, то можно использовать чередование через пробелы, лишь бы общая сумма в итоге оказалась отрицательной. В зависимости от того, является ли число пробелов четным или нечетным, от того, какая из цен является отрицательной и какой символ встречается первым, можно рассчитать адекватное количество паттернов, как видно из Таблицы 1.

Другой частный случай — когда одна цена отрицательна, а сумма по-прежнему положительна. В этом случае может быть возможность поместить один шаблон в эту начальную строку пробелов, но только если первый встреченный символ является подходящим. Например, предположим, что ввод «???C…» и что X = 3 и Y = -2. В этом случае мы могли бы сделать так, чтобы был один паттерн «JC». Но если бы вместо этого цены были X = -2 и Y = 3, то единственным способом размещения паттерна JC было бы также создание паттерна CJ. Суммарная стоимость обоих шаблонов оказывается положительной, поэтому программа должна ее избегать.

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

Последняя возможность состоит в том, что вся входная строка представляет собой только вопросительные знаки (?). Если и X, и Y больше нуля, то программа может избежать любой последовательности, поместив один и тот же символ во все пробелы. Если хотя бы одна цена ниже нуля, а сумма обеих цен также отрицательна, то предпочтительно создавать как можно больше паттернов в парах, чтобы получить прибыль. В зависимости от того, является ли количество пробелов четным или нечетным, соответствующие счетчики для шаблонов CJ и JC будут увеличиваться, и они будут напечатаны в выходном файле.

  • Решение для динамического программирования

Для второго тестового набора мы считаем, что «CJ» или «JC» также могут быть отрицательными числами, и поэтому для решения проблемы требуется совершенно другой подход, динамический подход.

Динамический алгоритм для этой задачи использует восходящий подход для ее решения. Он начинается с инициализации стоимости использования убывающей луны или закрытого зонтика в каждой позиции строки до бесконечности (в зависимости от языка программирования это может быть просто «очень большое» число). Если первым символом в строке является «J», стоимость использования закрытого зонта в этой позиции устанавливается равной 0, а если это «C», стоимость использования убывающей луны в этой позиции устанавливается равной 0.

Далее алгоритм перебирает строку, начиная со второго символа. В каждой позиции он обновляет стоимость использования убывающей луны или закрытого зонта в зависимости от персонажа в этой позиции, а также стоимость использования убывающей луны или закрытого зонта в предыдущей позиции. Если символ «C», стоимость использования убывающей луны в этой позиции устанавливается равной минимуму стоимости использования убывающей луны в предыдущей позиции и стоимости использования закрытого зонта в предыдущей позиции плюс стоимость использования закрытого зонта.

Если символ «J», стоимость использования закрытого зонта в этой позиции устанавливается равной минимуму стоимости использования закрытого зонта в предыдущей позиции и стоимости использования убывающей луны в предыдущей позиции плюс стоимость использования убывающей луны. Если символ «?», стоимость использования убывающей луны и стоимость использования закрытого зонта в этой позиции устанавливаются равными минимуму стоимости использования убывающей луны или закрытого зонта в предыдущей позиции.

После перебора всей строки алгоритм возвращает минимум стоимости использования убывающей луны или закрытого зонта в последней позиции строки.

АЛЬТЕРНАТИВНЫЕ РЕШЕНИЯ

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

Другой способ реализации решения динамического программирования, который использовался для третьего теста, — это подход «сверху вниз», который решает проблему более рекурсивным образом. Между тем, используемый здесь подход «снизу вверх» больше напоминает решение жадного алгоритма. Рассматривались оба варианта, но для простоты решили использовать второй.

Reversort Engineering

ОБЗОР

Проблема заключается в получении длины строки последовательных целых чисел (начиная с 1) и заданной стоимости. На выходе должна быть запутанная строка, стоимость сортировки которой с помощью функции «обратная сортировка» равна стоимости, заданной в качестве параметра.

Входные данные сначала содержат количество случаев для анализа (или количество запутанных строк, которые мы должны вывести), за которыми следуют длина 𝑁 и стоимость 𝐶 в каждой строке, по одной строке для каждого случая. Алгоритм анализирует, возможна ли вообще строка, стоимость которой указана, путем вычисления диапазона возможных затрат. Если строка возможна, она начинается со строки минимальной стоимости и видоизменяет ее, создавая строку, стоимость которой на единицу больше, чем раньше. Этот процесс повторяется столько раз, сколько необходимо для того, чтобы измененная строка имела желаемую стоимость.

КОНТЕКСТ

Существует уже работающая функция под названием «reversort», целью которой является сортировка запутанной строки, переворачивая части указанного списка символов. Он проверяет значение по первому индексу, а затем ищет наименьшее значение. При его нахождении он берет весь подраздел от текущего индекса до индекса этого наименьшего значения и переворачивает всю подпоследовательность. Затем он переходит к следующему элементу и повторяет процесс. Если он когда-нибудь обнаружит, что впереди нет меньшего значения, это означает, что текущее значение уже находится на своем месте и переходит к следующему.

Однако для этой задачи оказывается, что реверсирование подраздела строки имеет стоимость, равную количеству реверсированных элементов. Например, если мы были в индексе 𝑖, а наименьшее значение впереди было найдено в индексе 𝑗, это означает, что количество перевернутых элементов было 𝑗−𝑖+1. Дополнительный добавляется, потому что мы включаем оба конца того подраздела, который мы перевернули.

Когда элемент уже находится на своем месте и реверсирования нет, стоимость на самом деле равна 1. Мы можем считать, что он перевернул подраздел одного элемента (что в основном означает, что ничего не произошло, но все еще имеет стоимость).

РЕШЕНИЕ

Учитывая этот последний бит информации, в лучшем случае для строки будет то, что она уже отсортирована. Например, если у нас есть [1 2 3 4] с 𝑁=4, его стоимость будет 𝐶=3, так как последний элемент не анализируется. В этом нет необходимости, так как к моменту, когда функция доберется до нее, она уже будет разобрана. Итак, взглянув на это, мы видим, что наименьшая возможная стоимость строки из 𝑁 символов на самом деле составляет:

Теперь максимально возможная стоимость — это когда на каждой итерации мы должны перевернуть как можно больше элементов. В предыдущем примере для 𝑁=4 это было бы [2 4 3 1], поскольку на каждой итерации все элементы слева от текущего индекса меняются местами.

Анализируя это, мы видим, что мы добавляем 2+3+…+𝑁. Следовательно, максимально возможная стоимость определяется выражением Гаусса для суммы всех целых чисел до заданного числа N, но с вычитанием 1, поскольку мы фактически останавливаемся, когда стоимость равна 2:

Теперь мы можем сказать, возможна ли данная стоимость для данной длины строки или нет. Если это не так, мы даже не тратим время на расчет чего-либо. Однако, если стоимость находится в диапазоне [𝐶𝑚𝑖𝑛, 𝐶𝑚𝑎𝑥], нам нужно найти одно из множества возможных решений. Для этого мы можем просто начать со списка с наименьшей стоимостью и начать изменять его, добавляя 1 к его стоимости. Нам просто нужно будет повторить процесс 𝐶 − 𝐶𝑚𝑖𝑛 раз.

Способ сделать это состоит в том, чтобы начать с того, что взять предпоследний элемент с правой стороны строки и сдвинуть его полностью вправо, сделав его последним элементом. Затем третья предпоследняя, ​​затем четвертая предпоследняя и так далее. Например, скажем, у нас 𝑁=4. Самая низкая возможная строка стоимости будет [1 2 3 4]. Отправив эти элементы вправо и проанализировав стоимость в каждом случае, мы увидим, что это правильная мутация:

Однако что происходит сейчас? Согласно нашему уравнению, максимальная стоимость для 𝑁=4 будет 𝐶𝑚𝑎𝑥= 9. Мы видим, что происходит то, что мы хотим медленно изменять список, пока он не станет списком максимально возможной стоимости: [2 4 3 1].

Если мы на минутку проанализируем эту строку, то увидим, что она начинается с восходящего списка четных чисел (2, 4,...), а затем заканчивается убывающим списком нечетных чисел (..., 3, 1). Итак, в нашей предыдущей итерации, когда мы оказались на 𝐶=6, наш последний элемент уже был 1. У нас уже был один элемент, поскольку мы хотели бы, чтобы в конечном итоге получить список максимальной стоимости (даже если наша цель состоит в том, чтобы получить строку намного раньше). В этом случае мы можем сэкономить этот элемент и снова запустить наш алгоритм, но применяя его только к левому подсписку. Следуя тому, что у нас было раньше, мы теперь будем иметь:

Теперь мы можем видеть, что слева у нас есть 2 в правильном положении, чтобы в конечном итоге стать списком 𝐶𝑚𝑎𝑥. Итак, теперь мы можем сэкономить этот элемент и начать снова с оставшейся подстроки. В этом случае мы закончили, потому что следующим измененным списком будет [2 4 3 1], который является нашим списком максимальной стоимости 𝐶𝑚𝑎𝑥=9.

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

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

АЛЬТЕРНАТИВНЫЕ РЕШЕНИЯ

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

В частности, Haskell может быть проблематичным, учитывая, насколько он должен зависеть от рекурсии и как он не допускает изменения каких-либо переменных.

Медианная сортировка

ОБЗОР

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

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

КОНТЕКСТ

Программа-судья генерирует список из 𝑁 целых чисел, всех значений от 1 до 𝑁, в случайном порядке. Программа медианного сортировщика должна взаимодействовать с программой-оценкой, отправляя три из этих значений и получая, какое из них является средним значением среди двух других. Например, предположим, что программа судьи сгенерировала строку [2 4 3 1]. Медианный сортировщик знал бы, что 𝑁=4, но это все.

Чтобы сортировщик попытался вычислить строку, он должен начать запрашивать медиану различных наборов из трех чисел. Следуя предыдущему примеру, он может отправить [1 2 4] судье, на что судья ответит 4, поскольку в этой последовательности 4 стоит между 1 и 2.

Это означало бы, что список может быть [1 4 2] или [2 4 1]. Поскольку невозможно определить, какая ориентация является правильной, программа оценки примет любое решение как правильное.

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

РЕШЕНИЕ

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

Мы можем начать с собственного списка или последовательности, в которую мы можем вставлять каждое значение по мере того, как мы находим, где оно должно быть размещено. Изначально у нас может быть этот список как [1,2]. При этом мы можем начать с индекса 3, так как это следующее целое число, которое нужно вставить в наш список. Поэтому мы отправляем эти три числа судье, спрашивая его [1 2 3]. Предположим, что у нас есть [3 6 1 5 2 4] в качестве скрытого списка 𝑁=6. В этом случае судья ответит 1.

Поскольку наш текущий список был [1,2], и нам просто сказали, что 1 находится в середине, мы можем просто поместить 3 в самое начало, что приведет к [3,1,2]. Затем мы отправляем два целых числа из этого списка вместе со следующим номером индекса, который будет равен 4. Однако какие числа мы должны отправлять из нашего списка. В этом заключается основная идея этого алгоритма.

Предположим, у нас есть список из 𝑁 элементов. Это означало бы, что у нас есть индексы от 0 до (𝑁−1). Мы можем вычислить, какие индексы составляют примерно одну треть и две трети длины списка:

Мы можем назвать эти индексы 𝑖 для одной трети длины и 𝑗 для двух третей длины. Мы можем рассчитать их следующим образом:

Здесь 𝑐𝑒𝑖𝑙() означает «округлить» деление. Таким образом, даже для списка 𝑁=2 мы получим 𝑖=0, 𝑗=1. С помощью этих двух элементов мы можем задать правильный вопрос судье. Отправленный вопрос будет (𝑖−𝑡ℎ, 𝑗−𝑡ℎ, 𝑖𝑛𝑑𝑒𝑥), а индекс будет следующим числом для вставки. Таким образом, есть три основных возможности.

Во-первых, предположим, что программа отвечает, что 𝑖𝑛𝑑𝑒𝑥 — это среднее число. В этом случае мы теперь знаем, что мы должны вставить это новое число между индексами 𝑖−𝑡ℎ и 𝑗−𝑡ℎ.

Здесь только два случая. Во-первых, если 𝑗−𝑖=1, это означает, что элементы 𝑖−𝑡ℎ и 𝑗−𝑡ℎ находятся рядом друг с другом. Это означает, что наше значение 𝑖𝑛𝑑𝑒𝑥 можно просто вставить прямо между этими двумя индексами.

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

Что, если в любой из этих итераций среднее значение окажется элементом 𝑖−𝑡ℎ? Тогда это будет означать, что новое значение должно быть вставлено где-то между началом списка и элементом 𝑖−𝑡ℎ.

Опять же, могут иметь место два случая. Во-первых, если 𝑖 = 0, то 𝑖 было в самом начале последовательности. Это означает, что наше новое значение просто нужно поместить перед всеми элементами, и все.

Однако, если 𝑖 не является первым индексом, то слева от него есть один или несколько элементов, и позиция нашего числа может быть где угодно в этой последовательности. В этом случае мы просто берем подраздел, который идет от индекса 0 до элемента 𝑖−𝑡ℎ (включительно), и повторяем процесс.

Наконец, но аналогично, если приходит ответ, что элемент 𝑗−𝑡ℎ является средним, то это означает, что наше число должно располагаться где-то от элемента 𝑗−𝑡ℎ до конца строки.

Простой случай здесь, если 𝑗 = 𝑁−1. Это означает, что 𝑗 является последним элементом в последовательности, а это значит, что наш номер можно просто добавить в конец списка.

Если это не так, то справа от элемента 𝑗−𝑡ℎ есть один или несколько элементов, и мы должны повторить процесс отправки подраздела из индекса 𝑗−𝑡ℎ до конца списка (включительно).

Весь этот процесс необходимо повторять до тех пор, пока последним числом, вставленным в список, не будет 𝑁. Это означает, что решение готово со всеми числами от 1 до 𝑁 в правильном порядке в списке.

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

Подход, который следует использовать для этой задачи, должен быть «тройным поиском», если количество взаимодействий с программой-судьей должно быть 𝑂(log3𝑁). При этом все три представленных теста работают в определенных пределах и остаются в пределах желаемого количества взаимодействий 𝑄.

АЛЬТЕРНАТИВНЫЕ РЕШЕНИЯ

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

Отдача от родительского партнерства

ОБЗОР

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

КОНТЕКСТ

Сначала программе присваивается параметр 𝑇, который указывает, сколько раз программа должна запускаться, анализируя список действий и проверяя, можно ли их успешно делегировать двум партнерам, 𝐶 и 𝐽. Каждый раз, когда он запускается, на выходе будет строка из символов «C» и «J», которые указывают порядок, в котором каждый партнер начал выполнять задачу. Также существует вероятность того, что три действия перекрываются, поэтому результат будет «НЕВОЗМОЖНЫМ», так как они не смогли выполнить все действия.

Для каждого случая программа сначала получит параметр 𝑁, указывающий количество действий, которые следует попытаться делегировать. После этого следуют 𝑁 строк, каждая из которых содержит два элемента: время начала 𝑆𝑖 и время окончания 𝐸𝑖, обозначающие начало и конец действия.

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

РЕШЕНИЕ

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

После того, как все будет отсортировано, мы можем приступить к делегированию. Если возникает ситуация, в которой мы не можем делегировать действие ни одной из двух сторон, то мы прерываем цикл и выводим, что это «НЕВОЗМОЖНО». Чтобы начать делегирование, мы можем установить одного из партнеров в качестве приоритетного. В этом случае давайте поставим партнера 𝐶 в качестве приоритета.

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

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

Однако, если 𝑆 ‹ 𝐸𝐶, то 𝐶 все еще будет занят, когда начнется это следующее действие. И вот когда мы переходим к 𝐽. Тем не менее, мы не можем просто делегировать его 𝐽, потому что нам все равно нужно посмотреть, доступен ли он.

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

Опять же, если 𝐸𝐽 ‹ 𝑆, то 𝐽 не занято, мы можем делегировать его, и мы можем перейти к следующей активности в списке. Однако, если 𝑆 ‹ 𝐸𝐽, то это означает, что 𝐽 все еще занят предыдущей задачей к моменту начала этой задачи. Если такая ситуация наступит, мы уже видели, что и 𝐶, и 𝐽 заняты. Таким образом, эта деятельность не может быть делегирована ни одному из двух. Затем программа прекращает анализ действий и выводит «НЕВОЗМОЖНО».

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

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

АЛЬТЕРНАТИВНЫЕ РЕШЕНИЯ

Если действия были даны по порядку с самого начала, некоторое время выполнения можно сэкономить, делегировав задачу сразу после ее получения (или увидев, что ее нельзя делегировать). Таким образом, строка символов «C» и «J» обновляется только тогда, когда в качестве входных данных подается следующее действие.

Решение на разных языках:

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

Groovy, имеющий синтаксис, аналогичный Java, упростил реализацию алгоритмов с помощью списков. Учитывая все уже имеющиеся в нем функции, такие как sort, манипулирование ими было проще, чем в других языках, хотя это был не единственный язык из тех, что мы использовали, с такими функциями. Однако особой характеристикой этого языка было использование переменной типа double для представления положительной бесконечности. Это упростило программирование алгоритмов, подобных тем, которые используются в Median Sort или Reversort Engineering.

В Ruby, в отличие от Groovy, целочисленное деление определяется автоматически. Другие важные отличия включают в себя то, что все рассматривается как объект, даже числа. Мы можем воспользоваться этим фактом, создавая циклы, используя метод самого числа. Это также разрешено делать с массивами, которые были крайне важны для реализованных нами алгоритмов. Этот язык может быть строгим в отношении формата именования переменных и функций, поскольку переменная не может начинаться с заглавной буквы. Это используется, чтобы различать переменные и имена классов.

Typescript требовал небольшой корректировки нашего менталитета из-за его сходства с Javascript и другими структурными языками. Основным отличием была его строгость с типами переменных и тот факт, что его нужно было перевести в Javascript, прежде чем программу можно было скомпилировать и запустить. Вот почему этот язык также требует использования локального сервера, использования Node и т. д. Подобно Groovy, Typescript также имеет переменную, которую можно использовать для представления положительной бесконечности. Основные трудности, с которыми мы столкнулись при использовании этого языка, заключались в управлении вводом, будь то обычный текст или вообще. Ситуация ухудшилась при работе с интерактивными программами, такими как решение Median Sort.

Наконец, Haskell представлял наибольшую проблему, будучи полностью функциональным языком. Переменные нельзя было изменять, в синтаксисе не существует циклических структур (разрешается только рекурсия), и он был самым строгим в отношении типов переменных, чем любой из трех других языков. Он представляет стандартный ввод и вывод с «оболочкой» (монадами) вокруг значения, которое возвращает функция. Главный урок, который мы усвоили, используя этот язык, связан с постоянной практикой рекурсии, которая позволила нам реализовать алгоритмы как можно лучше.

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