Ежедневная часть (e) C++ # 7, Общие вопросы интервью: прыгающий мяч

Сегодня мы рассмотрим распространенный вопрос на собеседовании — «Прыгающий мяч».

Учитывая список целей, расположенных в линию, определите, может ли отскок мяча достичь конечной цели. Мяч может отскакивать только от целей, и если он достигает цели с горизонтальной скоростью 'i', он отскакивает с горизонтальной скоростью 'i-1', 'i' или 'i+1'.

Мяч никогда полностью не потеряет горизонтальной скорости вперед (или не отскочит назад).

Начальный бросок имеет горизонтальную скорость 1.

Например, для ввода {0,1,3,4,6,9,13} мяч может достичь конечной цели следующим образом:

  • отскок от цели 1 со скоростью 2
  • отскок от цели 3 со скоростью 1
  • отскок от цели 4 со скоростью 2
  • отскок от цели 6 со скоростью 3
  • и, наконец, отскок от цели 9 со скоростью 4 и приземление на последнюю цель

Для ввода {0,1,3,7,10,14} мяч не может достичь конечной цели, так как скачок между 3 и 7 слишком велик.

Прежде чем продолжить чтение решения, попробуйте решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://godbolt.org/z/9x6PsheEW.

Решение

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

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

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

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

bool canReach(const std::vector<int>& targets) {
  // Target -> List of speeds at which it is reachable
  std::unordered_map<int,std::unordered_set<int>> speeds;
  // In the beginning, only the second target is reachable at speed 1.
  for (auto distance : targets | std::views::drop(1))
    speeds[distance] = {};
  speeds[1] = {1};

  // Process each target
  for (auto distance : targets | std::views::drop(1)) {
    // For each speed this target is reachable
    for (auto speed : speeds[distance]) {
      // For each change in speed
      for (auto diff : {-1, 0, 1}) {
        if (speed + diff <= 0)
          continue;
        // If there is a target reachable with this speed,
        // add this speed to its list of speeds.
        if (speeds.contains(distance + speed + diff))
          speeds[distance + speed + diff].insert(speed + diff);
      }
    }
  }
  // Return whether we were able to reach the final target.
  return !speeds[targets.back()].empty();
}

Откройте решение в Compiler Explorer.

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

Это приводит нас к временной сложности O(n*n). Поскольку наши циклы напрямую отображаются на хранилище, мы также получаем сложность пространства O (n * n).