Решаем задания от Google. Часть 1
Всем привет! ? Думаю, многим известно, что такое Google (если не известно можете загуглить). Помимо того, чтобы обрабатывать миллионы поисковых запросов, Google ещё и устраивает конкурсы. Даже больше, если вы не житель Крыма, Сирии, Северной Кореи (не думаю) и стран эмбарго США, то у вас есть уникальная возможность поучаствовать в этих конкурсах лично. Наверно, стоит сразу предупредить, что эта статья для тех, кто уже примерно разбирается в алгоритмах и тому подобном, так как конкурс и статья будут о программировании.
Один из таких конкурсов под названием Kick start проходит в несколько раундов. Один из них прошёл совсем недавно, и мне удалось принять участие в нём. В этой серии статей я буду поочерёдно разбирать все задачи из этого этапа, а также методы их оптимизации (это важнее, чем некоторые думают).
Обратный отсчёт
Сразу пометка: все названия и задания будут в моём переводе. В оригинале конкурс на английском.
Вот смысл первой задачи:
Нам на вход даётся массив, состоящий из N натуральных чисел.
Непрерывный подмассив представляет из себя отсчёт m, если он имеет длину m и содержит целые числа m, m-1, m-2 .... 2, 1 в таком порядке. Например, [3, 2, 1] - это 3-отсчёт.
Наша задача найти, сколько в заданном массиве отсчётов длины M.
Пример входа:
Так как это программа, а не человек, то и данные подаются строго определённым образом.
В первой строке идут 2 числа: длина массива (N) и длина отсчётов для поиска (M). Во второй строке идёт сам массив. Пример входа:
12 3
3 5 7 1 4 2 7 123 5 4 6 4
Давайте решать!
Итак, я надеюсь, что все поняли смысл задачи. Если вы чего-то не поняли, пишите в комментарии или перечитайте предыдущий раздел.
Начнём с самого простого. Нам нужно считать данные и как-то обработать их. Для программирования я буду использовать язык Python, но всю суть буду объяснять.
data = list(map(int, input().split(' ')))
nums = list(map(int, input().split(' ')))
Это кусок кода для считывания данных. Здесь нет ничего сложного. Функцией input(), я считываю то, что ввёл пользователь, то есть получаю в нашем первом примере 12 3. Теперь, нужно как-то разбить эти числа. Для этого я использую функцию.split(' ') она позволит разбить наш текст на 2 части. Между скобками я указываю символ, с помощью которого выполняю разбиение. Эта функция вернёт нам ["12", "3"]. Вроде бы то, что нужно!.. Но нет, есть проблема. Это вовсе не числа, а строки, так как функция .split(' ') разбивает на строки. Поэтому я использую функцию map(), которая берёт этот массив (в Python это называют список) и каждый элемент обрабатывает функцией, указанной первым аргументом. В нашем случае, это функция int. Она превращает строки в числа. Но, к нашему сожалению, у нас получится что-то такое: . Не к добру это... Поэтому мы используем функцию list, которая превращает эти несколько символов в то, что нам нужно: [12, 3].
** Звуки всеобщего ликования. Звук надписи "Конец", а потом звук надписи "Нет! Это только начало" **
Аналогично мы обрабатываем вторую строку и получаем массив: [3, 5, 7, 1, 4, 2, 7, 123, 5, 4, 6, 4].
Теперь можно с этим работать.
Давайте сделаем цикл, который будет перебирать все числа по порядку.
for num in range(data[0]):
Если переводить с языка Python на русский получится:
На самом деле, получится цикл, который переберёт все числа от 0 до N - 1, записывая каждое число в переменную num.
Чем же нам поможет такой цикл? Он поможет тем, что в нём мы можем сделать ещё один цикл! Он будет перебирать следующие за этим числа и проверять, являются ли эти несколько чисел отсчётом. Выглядит этот цикл так:
for w in range(data[1]):
Такой цикл переберёт все числа от 0 до M - 1, записывая их в переменную W.
Это нам позволит проверить являются ли M чисел, следующих за числом, перебором. Для этого мы добавим одно условие и переменную flag. Весь кусок будет выглядеть вот так:
flag = True
for w in range(data[1]):
if not (w + num < data[0] and nums[num + w] == (data[1] - w)):
flag = False
break
Сначала мы записываем в переменную flag значение true. Это пригодится позже. Затем мы перебираем циклом все числа от 0 до N - 1. Затем идёт условие: если число в массиве под номером num + w не равно M - w, то мы делаем пометку, что в этом массиве нет отсчёта, начинающегося с числа под номером num. Небольшое объяснение условия: перебирая числа с помощью первого цикла, мы как бы перебираем возможное место начала отсчёта, а при переборе вторым циклом мы проверяем есть ли отсчёт, начинающийся с этого места в массиве (в любом отсчёте элемент под номером N (нумерация идёт с нуля) является числом L - N, где L - длина отсчёта). Если мы понимаем, что нет отсчёта, начинающегося с этого числа, мы выходим из цикла с помощью команды break. Затем идёт вот такое условие:
if flag:
num += (data[1] - 1)
answer += 1
Здесь нам и нужна переменная flag. С помощью неё мы понимаем, найден ли отсчёт в этом месте массива. Если в переменную записано значение True, значит в этом месте отсчёт. В таком случае я прибавляю к ответу 1. Также я увеличиваю num (номер текущего начального элемента для проверки) на длину найденного отсчёта - 1, так как все эти элементы входят в найденный отсчёт и нам незачем их проверять.
Если вы не запутались до этого места, это очень хорошо, ведь после того, как вся программа отработает на выходе, в переменной answer, мы получим верный ответ!
Оптимизация
Это одна из важнейших частей решения, ведь в большинстве задач на этом конкурсе важно не само решение, а его скорость. Поэтому в этой части я расскажу, как можно ускорить эту программу. Вот две вещи, которые пришли мне в голову:
1. Так как отсчёт имеет определённую длину, то он не может начинаться с элемента, находящегося к концу массива ближе, чем длина отсчёта. Например, если отсчёт длины 3, то второй элемент с конца проверять нет смысла, так как отсчёт начинаться с него не может. Значит цикл первый цикл:
for num in range(data[0]):
мы можем превратить в:
for num in range(data[0] - data[1] + 1):
2. Также, отсчёт всегда начинается с числа равного его длине. Например, отчёт длины 3 всегда начинается с 3. Поэтому, нам даже не нужно начинать перебор вторым циклом, если число не равно длине отсчёта. При этом добавится простое условие:
if nums[num] == data[1]:
Вот это изменение уже сильнее ускорит программу по сравнению с предыдущим, так как для большинства цифр проверка даже не будет нужна.
Решение, предложенное Google
После соревнования Google выкладывает своё решение задачи. В этом случае оно отличается от моего варианта. Сейчас я кратко разберу их решение.
answer_counter = 0
decreasing_counter = 0
for (i = 1 to N) { ** N - количество чисел в массиве
if (A[i] == A[i - 1] - 1) { ** A - массив
decreasing_counter = decreasing_counter + 1
} else {
decreasing_counter = 0
}
if (A[i] == 1 and decreasing_counter >= K - 1) { ** K - длина отсчёта для поиска
answer_counter = answer_counter + 1
}
}
print answer_counter
Это решение написано на псевдокоде и переведено с английского. Его смысл в том, что мы перебираем все числа в массиве подряд и, если текущее число равно (предыдущему - 1), то мы увеличиваем значение переменной decreasing_counter на 1 (фактически в этой переменной хранится количество подряд идущих чисел в массиве, начиная с текущего числа), иначе - в decreasing_counter записываем 0.
Так как отсчёт любой длины заканчивается числом 1, то если текущий элемент массива равен 1, то, чтобы это был отсчёт длины K, за нашим числом должно идти K - 1 подряд идущих чисел. Именно это количество хранится в переменной decreasing_counter, значит, если значение этой переменной равно K - 1, то перед нами отсчёт. Мы увеличиваем ответ на 1 и следуем дальше по массиву.
Заключение
Если вы дочитали до сюда, то пишите в комментариях, что улучшить в следующих частях этой статьи. Также можете предлагать свои алгоритмы решения и оптимизации.
Также я хочу опробовать опросы, которые только недавно добавил, поэтому голосуйте!