Мы Competitive Programming London, мы встречаемся раз в неделю, чтобы попрактиковаться в некоторых алгоритмических задачах из Codeforces, Hackerrank, Leetcode и других задачах. Каждый раз, когда мы встречаемся, мы работаем над несколькими проблемами в парах, а затем обсуждаем решения друг друга в целом ближе к концу. Для этого мероприятия мы решили три задачи:

Этот пост подытожит наши темы для обсуждения и то, как мы подошли к решению каждой проблемы.

Отличительные цифры

ссылка на проблему: https://codeforces.com/contest/1228/problem/A

В этой задаче нам нужно найти любое число с различиями между диапазоном a и b. Ограничения задачи заключаются в том, что и a, и b находятся в диапазоне от 0 до 10⁵. Кроме того, b всегда больше, чем a. Как и в большинстве конкурентных проблем, обычно разумно посмотреть, будет ли достаточно решения грубой силы для этой проблемы. Максимальный размер нашего диапазона равен 10⁵, но если бы нам нужно было проверить любой диапазон между a и b, какое наибольшее количество проверок нам нужно сделать? Хорошо, давайте выясним это с помощью быстрого скрипта:

Приведенная выше программа сообщит нам, сколько вычислений мы можем ожидать в *наихудшем случае* для диапазона от 0 до 10⁵. После того, как мы запустим его, мы получим следующий вывод:

1047 10987 12034

Это означает, что большинство вычислений, которые мы будем выполнять, составляют 1047, и это для a=10987 и b=12034. Таким образом, это говорит нам о том, что мы можем без труда написать решение грубой силы для ее решения:

Есть ли более «эффективный» способ? Оказывается, есть, и это само собой разумеется, если мы сможем сгенерировать минимальное число, большее или равное x, которое имеет различные цифры. Я вставил код ниже, который выполняет этот тип генерации. Это займет слишком много времени, чтобы объяснить, что он делает, поэтому, если у вас есть какие-либо вопросы по этому поводу, свяжитесь со мной в социальных сетях (ссылки ниже).

Действительная скобка

Ссылка на проблему: https://leetcode.com/problems/valid-parentheses/

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

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

Книга для рисования

Ссылка на проблему: https://www.hackerrank.com/challenges/drawing-book/problem

В этой задаче нам просто нужно найти, в каком номере листа мы находимся для данного номера страницы. Для этого деление на 2 (пол) даст нам это значение. например для страницы 1, 1/2 = 0, для страницы 2, 2/2 = 1, для страницы 3, 3/2 = 1, для страницы 4, 2/2 = 2 и так далее. Таким образом, это дает нам, в каком индексе перелистывания мы находимся. Ключевым моментом является вычисление индекса перелистывания последней страницы, и тогда нашим ответом будет минимальное расстояние перелистывания от начала (индекс 0) до индекса перелистывания p. , и расстояние от конца до флип-индекса p :

def pageCount(n, p):
    fromStart = p // 2
    fromEnd = n // 2 - p // 2
    return (min(fromStart, fromEnd))

Если вы находитесь в Лондоне, я надеюсь увидеть вас на следующем мероприятии :). Хотите присоединиться к нашей слабой группе, чтобы обсудить подобные проблемы? Напишите мне в twitter или linkedin, чтобы присоединиться