Авраам Рамирес, Альдо Сантьяго, Алехандро Мендоса, Алондра Гальван, Гонсало Мартинес, Густаво Игера, Хуан Санчес, Оскар Гарсон.
Упущено
Обзор:
Задача требует от нас найти два числа, которые при суммировании равны сумме лотерейного приза (целевое число), но ни одно из сгенерированных чисел не может содержать цифру 4.
Первая строка ввода содержит количество тестовых случаев (или количество целей). Следующая строка содержит целевой номер, по одному для каждого определенного случая. Алгоритм берет целевой номер строки, затем проходит по строке и оценивает каждую цифру. Во время оценки каждая цифра наших чисел A и B генерируется одновременно. Результат алгоритма показывает решение для каждого определенного случая. Этот процесс повторяется для каждого случая.
Контекст:
О, нет! Клавиатура большого чекового принтера сломана, а клавиша 4 не работает. Кто-то только что выиграл в лотерею Code Jam, и этот чек нужно распечатать. По какой-то причине сумма приза всегда включает хотя бы одну «4». Что мы можем сделать? Распечатаем два негабаритных чека, которые в сумме составляют сумму приза и не содержат цифру 4! Перед нами стоит задача найти эту пару чисел, чтобы распечатать чеки.
Итеративное строковое решение:
Чтобы решить эту проблему, мы заметили, что нам нужно сосредоточиться только на цифре «4», все остальные цифры не имеют значения. Мы решили добавлять 2 к каждому чеку, когда находим 4, таким образом мы можем сохранить ценность суммы приза.
Мы решили прочитать ввод как строку и объявить две пустые строки для нашего вывода, a и b. Теперь мы можем прокрутить строку и проверить, является ли цифра 4, если это так, то мы объединяем «2» с каждой строкой, но если это не 4, то мы объединяем эту цифру с a и «0» в строке b. Мы должны добавить 0 к строке b, так как мы должны учитывать разрядность каждой цифры.
Когда мы закончим перебирать строку, у нас будет две строки, представляющие сумму для каждого чека, мы можем затем вернуть их и показать вывод. Мы решили использовать строки для представления чисел, так как в тестовом примере 3 число приза может достигать 10100, а некоторые языки не могут представлять такие большие целые числа.
Это решение, с точки зрения нотации Big-O, равно O(N), поскольку мы перебираем строку только один раз.
Чтобы решить эту проблему в LISP, нам пришлось приспособиться к особенностям языка. В LISP все представляет собой единый связанный список, поэтому лучшей структурой данных для работы является список. Мы считывали входные данные как строку и обрабатывали их как обычно, но вместо определения пустых строк мы определяли пустые списки и использовали функцию cons для добавления цифр в списки. Сделав это, мы получили список в обратном порядке, поэтому мы использовали функцию reverse, чтобы распечатать список в правильном порядке.
Чтобы разработать решение на Java, входную строку нужно было преобразовать в массив строк. Таким образом можно было легко перемещаться по цифрам с помощью цикла for. Числа A и B были определены как строки, поэтому мы использовали функцию concat для добавления каждой цифры, и для вывода не требовалось никакого преобразования.
Чтобы решить эту проблему с помощью Go, необходимо было преобразовать входные данные задачи в строку, а также два выходных числа, потому что использование 64-битного целого числа не могло пройти тестовые примеры из-за длина цифр. Также, используя строки, мы могли бы конкатенировать числа решения и перебирать цифры входного числа.
С другой стороны, для разработки решения на Python входные данные с самого начала принимаются как строка. Затем, учитывая целевое число N, даже если это строка, мы можем использовать методы списка для подсчета числа 4, которые она имеет (с N.count(); чтобы уменьшить количество итераций, которые будут сделаны) и для найти его позицию (используя N.find() внутри цикла, чтобы найти их все).
Альтернативные решения:
Итеративное целочисленное решение:
Мы также рассматриваем чтение ввода как целое число. Следуя описанной методологии, мы рассмотрим циклическое перебор номера с дополнительной помощью оператора мода. Итак, мы делим число на 10, а затем можем взять мод в качестве цифры, которую мы хотим оценить.
Во время оценки мы также должны проверить, равна ли цифра четырем. В этом случае мы можем присвоить значение «2» в строке A и другое «2» в строке B. В случае, если цифра не равна 4, мы можем сгенерировать случайное число от 0 до 9, но также отличное от 4 и 6 в строке A, и используйте уравнение B = d — A для строки B.
После этой оценки мы повторно присваиваем целевое число, и цикл продолжается до тех пор, пока не останется цифр для оценки, то есть цель равна нулю.
Таким образом, мы можем получить пару чисел, которая равна цели, A и B, а также они не всегда следуют одному и тому же шаблону, но могут генерироваться более динамично. Тем не менее, мы считаем, что это может иметь затраты времени выполнения и места во внутренней памяти из-за процессов, описанных выше, и необходимого преобразования из String в Integer и наоборот.
Глубина вложения
Обзор:
Эта задача состоит в том, чтобы вставить минимальное количество скобок в строку цифр, чтобы каждая цифра со значением d находилась внутри ровно d пар совпадающих скобок.
Первая строка ввода содержит количество необходимых тестов (в данном случае количество строк для оценки). Следующая строка содержит строку чисел, по одному для каждого случая. В этом алгоритме в начале и в конце строки добавляется 0, затем она перебирается и сравниваются две цифры. На основе этой оценки к строке добавляются закрывающие и открывающие круглые скобки. Этот процесс повторяется для каждого случая.
Контекст:
Дана строка цифр S, вставьте в нее минимальное количество открывающих и закрывающих скобок так, чтобы результирующая строка была сбалансированной и каждая цифра d находилась внутри ровно d пар совпадающих скобок.
Дана строка цифр S, найдите другую строку S’, состоящую из круглых скобок и цифр, такую, что:
- Все скобки в S’ соответствуют некоторым другим скобкам
- Удаление любых скобок из S’ приводит к S
- Каждая цифра в S’ равна своей глубине вложенности
- S’ имеет минимальную длину
Например, строка «2110330» должна давать строку «((2)11)0(((33)))0».
Разница между цифрами:
Если мы рассмотрим некоторые примеры правильных значений для S' и пройдемся по каждой цифре в S', мы сможем заметить, что каждый раз, когда значение цифры изменяется в S', должно быть определенное количество скобок между цифрами, которые различны последовательно. Кроме того, количество круглых скобок между каждыми двумя последовательными разными цифрами является разницей между значениями этих цифр. Если цифра D меньше, чем следующая за ней D’, между ними должны быть D’ — D открывающие круглые скобки. Если D больше, чем D’, должны быть закрывающие скобки D — D’.
Есть только одна проблема с этим подходом, первая цифра в S не имеет цифры перед сравнением и вставкой необходимых скобок, а последняя цифра не имеет последовательной единицы, поэтому мы можем просто добавить ноль в начале и в конце S, а заканчивая расставлять нужные скобки, убираем 0.
Это решение имеет временную сложность O(N), так как нам нужно только один раз перебрать S и вычислить разницу для каждой цифры.
Чтобы решить эту проблему в Java, входная строка была преобразована в массив строк для простого обхода цифр с помощью цикла for. Мы используем функцию compareTo для сравнения цифр в их строковой форме. Эта функция возвращает значение в зависимости от лексикографической разницы между двумя символами, в данном случае рассматривая их как числа:
- х = 0, если они равны.
- x ‹ 0, если первое число меньше второго.
- x › 0, если первое число больше второго.
Таким образом, мы также получаем точное количество скобок, которые мы должны добавить к строке. Кроме того, функция repeat использовалась для создания строки в скобках без необходимости рекурсивного добавления каждой из них.
Мы также создали две функции, названные addClosingParentheses и addOpeningParenthesis, для лучшей структуры кода. Функция join использовалась для преобразования нового массива, созданного во время работы алгоритма, в строку.
Реализация на Python была довольно простой и включала только итерацию строки.
Альтернативное решение:
Альтернативное решение было практически таким же, как и первое решение, только реализован счетчик открытых скобок вместо добавления нулей в начале и конце строки.
Имея это в виду, мы могли бы сравнить цифры со счетчиком, и если цифры — openParenthesis › 0, мы добавляем нужную скобку (оставшуюся) и увеличиваем счетчик. В противном случае, если цифры — openParenthesis ‹ 0, мы закрываем скобки |digits — openParenthesis|.
Временная сложность этого альтернативного решения была такой же, O(N), потому что нам нужно выполнить итерацию S только один раз.
Для реализации этой задачи в Go мы использовали альтернативное решение для простоты, потому что добавление и удаление символов из строки в Go не так просто, как в Python или Java, и использование счетчика помогает нам в этом без использования слайсов или реализации push/ поп-функции.
Для реализации альтернативного решения на Лиспе мы использовали хвостовую рекурсию. Вместо реализации операций в цикле for они были реализованы в параметрах функции. Таким образом, каждая итерация эквивалентна следующему рекурсивному вызову. Сложность рекурсивной реализации такая же, как и итеративной реализации, потому что мы использовали хвостовую рекурсию.
Вы можете идти своим путем
Обзор:
Эта задача включает в себя прохождение лабиринта, начальная позиция находится в левом верхнем углу, а выход - в правом нижнем углу. Кто-то уже разгадал лабиринт, поэтому мы должны найти путь, который не повторяет сделанные ею шаги.
Учитывая число T, указывающее общее количество тестовых случаев, за которым следуют 2 строки на каждый тестовый пример, первая из которых указывает размер квадратного лабиринта, а вторая указывает путь, который прошел наш соперник из детства, нам нужно найти другой путь, который не использует те же шаги, что и наш соперник. Например, если наш соперник пошел из А в В, мы можем пересечь А или В, но не можем пройти из А в В в том же порядке.
Контекст:
Мы вошли в мир самого простого лабиринта в мире, наша начальная позиция в левом верхнем углу, а выход в правом нижнем углу, но у нас есть только два типа движения, мы можем идти на юг, или направо , но никакое другое направление. У нас есть пожизненная соперница детства по имени Лидия, которая уже разобралась с лабиринтом, поэтому мы не можем пройти тот же путь, что и она, но можем пересечь его в некоторых точках. Перед нами стоит задача найти новый выход из лабиринта.
Итеративное строковое решение:
Мы заметили, что лабиринт всегда представляет собой сетку N на N, зная это, мы знаем, что можем просто изменить путь Лидии, и все готово. Поскольку созданный путь будет иметь N-1 E и N-1 S, он всегда будет заканчиваться на выходе. Для этого сначала мы объявляем пустую строку для вывода, а затем читаем ввод как строку и прокручиваем символы. Если это символ S, мы объединяем E с выходной строкой и наоборот. Когда мы закончим цикл по строке, мы можем вернуть нашу выходную строку.
Это решение, с точки зрения нотации Big-O, равно O(N), поскольку мы перебираем строку только один раз.
Чтобы решить эту проблему в LISP, мы немного скорректировали алгоритм. Как и в решении Foregone, мы читаем ввод как строку, используем список, созданный с помощью функции cons, и обращаем его в конце с помощью функции reverse.
Для решения на Python мы просто объявляем пустую строку и добавляем (используя оператор +) 'E' или 'S' (в виде символов), когда это необходимо. как это описано в первом абзаце этого раздела.
В Java нам просто нужно повторить входную строку, а затем добавить «E» или «S» в качестве символов в новую строку, помогая нам с позицией. Также мы используем функцию Scanner Java.
Чтобы решить его с помощью Go, объявляется пустая строка для сохранения решения. Итерация от нуля до N-1 и проверка, есть ли в пути Лидии «S», сравнивая символ в позиции с 83 (Go использует базовое число 8/16 для символов, поэтому они называются рунами). Если есть «S», мы добавляем «E» к строке решения, в противном случае мы добавляем «S», это почти такая же реализация, как и другие, но мы должны быть осторожны, используя сравнения между рунами и строками. .
Альтернативные решения:
Наборы возможностей:
У вас может быть много возможных решений, но они должны быть одинаковой длины, чем 2N — 2, поэтому вы можете построить множество, содержащее множество строк, отбросить невозможные и выбрать одно из оставшихся, но оно работает слишком медленно, а также использует много памяти.
Дерева поиска в графическом виде:
Другой подход состоит в том, чтобы создать дерево поиска, выполнить некоторый поиск за время NlogN и найти возможные способы выхода из лабиринта. Этот подход немного быстрее предыдущего, но реализованный нами имеет линейную сложность.
ESAb ATAd
Обзор:
Эта проблема связана с извлечением массива битов, хранящихся внутри машины. Чтобы получить информацию, мы можем запросить машину и получить требуемый бит, но эта машина подвержена случайным квантовым флуктуациям, и информация, хранящаяся внутри, меняется каждые 10 запросов.
Эта задача является интерактивной, поэтому судьей будет система, созданная Google. Он отвечает за отправку битов обратно и оценку правильности нашего ответа. Входные данные для нашей программы состоят из одной строки, содержащей T и B, где T представляет количество тестовых случаев, а B представляет размер массива, он постоянен во всех тестовых примерах. Затем мы обработаем каждый тестовый пример, мы можем сделать до 150 запросов, прежде чем распечатать массив. Судья ответит «Д» или «Н», если мы получаем «Д», мы продолжаем следующий тест, если он есть, но, если мы получаем «Н», мы должны закончить программу. .
Контекст:
В прошлом году у исследовательского консорциума возникли проблемы с распределенной базой данных, из-за которой иногда терялись некоторые данные. Они решили хранить данные в машине, где данные хранятся в виде массива, состоящего из битов. Чтобы получить информацию от машины, вы должны сделать запрос и получить массив по крупицам. Однако есть одна проблема: эта машина подвержена случайным квантовым флуктуациям, особенно после отправки каждого 1-го, 11-го, 21-го… запроса. Эти колебания происходят до того, как система отправит бит, и существует четыре типа колебаний, которые имеют одинаковую вероятность возникновения:
- В 25% случаев массив дополняется: каждый 0 становится 1, и наоборот.
- В 25% случаев массив переворачивается: первый бит заменяется последним битом, второй бит заменяется предпоследним битом и так далее.
- В 25% случаев массив дополняется и переворачивается.
- В 25% случаев с массивом ничего не происходит.
Перед нами стоит задача получить данные, в какой бы форме они ни были, не имеет значения, колеблются они или нет, мы просто должны быть точными к тому времени, когда мы их предоставляем. Мы можем сделать до 150 запросов на тестовый пример.
Решение:
Поскольку нам нужно получить весь массив битов данных в его текущем состоянии, для тестовых случаев с массивами данных длиной 10 мы можем просто запросить каждый бит, и как только у нас будут все 10 бит, мы получим ответ, потому что после сохранения не произошло никаких колебаний. первый бит.
Для тестовых случаев с длиной более 10 флуктуации будут происходить после того, как мы уже сохранили некоторые биты, поэтому нам нужно определить, какой тип флуктуации произошел, и обновить нашу локальную копию.
Идентифицировать дополнения легко, если бы мог произойти только этот тип флуктуации, аналогично, если бы мог произойти только реверс, нам нужно идентифицировать известный бит с симметричной парой, которая имеет другое значение, например, если левый бит равен 0, правый бит равно 1, и если после флуктуации эти значения меняются, значит, у нас была обратная операция. В этом сценарии и дополнение, и обращение могут происходить по отдельности или одновременно.
Итак, вернемся к нашему биту с симметричной парой с другим значением, если он меняется после флуктуации, значит, был либо реверс, либо дополнение, чтобы знать, что именно произошло, нам нужно идентифицировать другой бит с симметричной парой, но этот с одинаковое значение, если после флуктуации этот бит не меняется, значит у нас не было дополнения, если да, то у нас было дополнение.
Таким образом, мы запрашиваем неизвестные биты, когда знаем, что колебания не было, и только в 11-м, 21-м, 31-м, … запросах мы должны провести несколько запросов, чтобы запросить известные биты и проверить, как они изменились, как описано выше, чтобы узнать, что именно произошло, и при необходимости обновите нашу локальную копию.
Реализация на Python предполагала использование словарей для хранения информации о значении бита и информации о его симметричной паре (равное или разное значение).
В Java код очень «простой» и читабельный, но потребовались часы анализа, чтобы добраться до этой точки. Поскольку Java очень многословен, довольно сложно добраться до сути, не запутавшись в слишком большом количестве слов. Также было довольно сложно тестировать из-за типа проблемы. Но, в конце концов, это то же самое решение, которое используют многие языки, без необходимости делать что-то еще.
Изначально мы пытались реализовать первое решение на Лиспе, но язык заставил нас кое-что изменить. Работа со словарями в Лиспе сложна, поэтому мы обнаружили, что нет необходимости знать, является ли пара симметричной или асимметричной для каждого бита в числе. Вам нужно знать только одну симметричную пару и одну асимметричную пару. И если есть только асимметричные пары, вам нужно знать только одну пару, случай только с симметричными парами аналогичен. Поэтому вместо словарей мы использовали две переменные для хранения значений индексов симметричных и асимметричных пар и массив для хранения уже известных нам числовых битов. Мы также выяснили, что если у вас есть только асимметричные пары, то возможны только две операции: дополнение или ничего. Остальные операции сводятся к этим двум. Если у вас есть только симметричные пары, это аналогично. Благодаря этим двум наблюдениям мы смогли реализовать решение на Лиспе. Остальная часть нашей реализации очень похожа на исходное решение, после каждых 10 запросов модуля 1 к Google мы проверяем операцию, выполненную с массивом, обновляем наш массив и продолжаем запрашивать новые биты, пока не узнаем значение каждого бита.
Реализация этого алгоритма в Go немного сложнее, он во многом похож на C, поэтому использование указателей, массивов и других структур данных может быть немного сложным. Мы можем попытаться имитировать словари в Go, но в конце лучше использовать массив и переменные, такие как индексы, чтобы отслеживать состояние базы данных, и при каждом взаимодействии мы запрашиваем пару битов, нам нужно найти симметричную пару и асимметричная пара, с ними обоими мы можем отслеживать изменения, которые происходят в базе данных на каждой 11,21,31… итерации. Мы можем использовать это как двойной выстрел, потому что он работает, когда у нас есть только один бит внутри нечетной строки и в любом другом случае, поэтому нам нужно следить за несколькими особыми случаями.
Альтернативное решение:
Набор возможностей:
Другой подход к решению задачи — создание множества возможностей, каждый массив описывает возможное решение, и каждый раз, когда мы проверяем наличие флуктуации, мы можем отсеивать массивы, не вписывающиеся в решение, анализируя этот подход, мы видим, что он использует много памяти, а также медленнее, чем наш, мы можем улучшить это, используя вероятность, но вычислительные усилия почти такие же, и его сложнее реализовать.
