Я думал принять участие в Google Hash Code 2020, и это будет мой первый раз, я буду участвовать в чем-то подобном. Поэтому, чтобы чувствовать себя уверенно перед соревнованием, я попробовал тренировочную задачу, предоставленную Google, до того, как соревнование действительно началось.

Я предполагаю, что читатели этой статьи уже знакомы с постановкой задачи. Вот ссылка на практическое задание-https://hashcodejudge.withgoogle.com/#/rounds/4684107510448128/

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

Вот ограничения входных данных: -

● целое число M(1 ≤ M ≤ 10^9) — максимальное количество кусочков пиццы для заказа

● целое число N(1 ≤ N ≤ 10^5) — количество разных видов пиццы

Вторая строка содержит N целых чисел: количество кусочков в каждом виде пиццы в порядке неубывания:

● 1≤S(0) ≤S(1) ≤…≤S(N-1)<=M

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

Подход 1

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

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

Вы можете повторять либо от начала до конца, либо от конца к началу.

Это результат, который я получил от этого представления.

Общая временная сложность этого подхода составит O(N).

Подход 2

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

1. Временная сложность около O(N*M), что невозможно с заданными ограничениями.

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

Но этот подход истек для последних двух больших входов.

Подход 3

Это был мой лучший и последний подход на сегодняшний день. Вот алгоритм, описанный ниже: -

  1. Перебирайте элементы один за другим.
  2. Для каждого элемента давайте рассмотрим ту часть, которую мы собираемся рассмотреть.
  3. Теперь мы знаем, выбрали ли мы элемент на предыдущем шаге, left_over_weight = M-slice_count[i] для i-го элемента.
  4. Теперь мы также храним двоичное дерево поиска, состоящее из пары значений каждого значения элемента и его индекса.
  5. Итак, теперь мы ищем наименьшее возможное значение, чем left_over_weight, которое мы можем найти в нашем двоичном дереве поиска, что занимает O(logn)сложность по времени.
  6. Мы продолжаем делать это внутри цикла while, пока не достигнем значения left_over_weight равным нулю.
  7. Продолжаем делать это для каждого i-го предмета, учитывая, что i-й предмет точно считается присутствующим в нашей сумке.
  8. Теперь мы берем наилучшую возможную комбинацию, которая дает нам суммарный вес, ближайший к значению M.

Давайте посмотрим на результаты, достигнутые с помощью этого подхода.

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

17 + 100 + 4500 + 1000000000 + 505000000, что равно = 1505004617.

Таким образом, разница между максимально достижимым значением и результатом нашего подхода составляет = 1505004617–1505004544 = 73.

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

Спасибо за прочтение статьи!