Разбор задачи «Тропа через платформы»

Идея задачи

Есть N платформ с высотами S[i]. Путешественник стартует на платформе 0 и хочет добраться до точки N, которая находится сразу за последней платформой.

С платформы i можно прыгнуть вперёд на любую позицию от i + A[i] до i + B[i] включительно.

Если новая позиция меньше N, то это очередная платформа. Если позиция равна N, значит путешественник дошёл до финиша.

Нужно минимизировать максимальную высоту платформы, на которой путешественник побывал по пути.

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

max(S[p0], S[p1], ..., S[pk])

минимально.

Что хочется хранить

Пусть

dp[i] — минимально возможная максимальная высота на маршруте, если мы смогли попасть на платформу i.

Тогда если мы уже стоим на платформе i, и можем прыгнуть на платформу j, то новый путь будет иметь цену

max(dp[i], S[j]).

Значит переход выглядит так:

dp[j] = min(dp[j], max(dp[i], S[j]))

при всех j из диапазона [i + A[i], i + B[i]].

Наивная реализация сразу слишком медленная: у каждой вершины может быть длинный диапазон переходов, и тогда получится до O(N^2) операций.

При N до 10^6 это не подходит.

Ключевое наблюдение

Если некоторая платформа i достижима, то она порождает один диапазон переходов:

[i + A[i], i + B[i]].

Для всех позиций внутри этого диапазона платформа i предлагает один и тот же базовый кандидат dp[i].

То есть для текущей позиции pos нам важно знать:

• какие ранее достигнутые платформы могут прыгнуть в pos;
• среди них взять минимальное dp.

Обозначим

best(pos) = min(dp[i]) по всем i, для которых pos лежит в диапазоне прыжка из i.

Тогда

• если pos < N, то dp[pos] = max(best(pos), S[pos]);
• если pos = N, то ответ просто best(N), потому что в точке N уже нет новой платформы, высоту добавлять не нужно.

Значит задача сводится к тому, чтобы при проходе слева направо поддерживать множество активных отрезков, покрывающих текущую позицию, и быстро находить минимум dp[i] среди них.

Как организовать быстрый проход

Будем идти по позициям pos = 1, 2, ..., N.

Для каждой достижимой платформы i добавим событие:

• отрезок начинает действовать в L = i + A[i];
• отрезок заканчивается в R = i + B[i];
• вместе с ним хранится значение dp[i].

Что нужно уметь

Для каждой позиции pos:

1. добавить все события, которые начинаются в pos;
2. удалить из рассмотрения все события, у которых правая граница уже меньше pos;
3. среди оставшихся взять минимальное значение dp.

Это удобно делать с помощью:

• массива списков событий по левому концу;

• min-heap (приоритетной очереди), где лежат пары:

  • (dp, right_border).

Почему heap подходит

В куче сверху всегда лежит событие с минимальным dp.

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

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

Пошаговый алгоритм

1. Старт

Начинаем на платформе 0, значит

dp[0] = S[0].

Из неё можно прыгать на позиции из диапазона:

[A[0], B[0]].

Поэтому сразу добавляем первое событие с ценой S[0].

2. Обход позиций слева направо

Для каждой позиции pos от 1 до N:

• добавляем в кучу все события, которые начинаются в pos;
• удаляем из кучи события, у которых R < pos;
• если куча пуста, то позиция недостижима;
• иначе лучший кандидат — это минимальное dp в вершине кучи.

Если pos == N, то это и есть ответ.

Если pos < N, то вычисляем:

dp[pos] = max(best, S[pos])

и создаём из этой платформы новое событие на диапазон её прыжка.

Почему решение корректно

Докажем по индукции по позиции.

База

Для платформы 0 значение

dp[0] = S[0]

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

Переход

Предположим, что для всех платформ левее текущей позиции их значения dp уже посчитаны правильно.

Рассмотрим позицию pos.

В куче после удаления устаревших событий остаются ровно те платформы i, для которых:

• платформа i достижима;
• pos лежит в диапазоне прыжка из i.

То есть каждая такая платформа действительно позволяет попасть в pos.

Среди них выбирается минимальное значение dp[i], обозначим его best.

Любой маршрут в pos обязан прийти из одной из этих платформ, поэтому лучше best быть не может.

С другой стороны, маршрут из платформы с этим значением best реально существует, и после приземления на pos максимальная высота станет

max(best, S[pos]).

Следовательно,

dp[pos] = max(best, S[pos])

вычисляется корректно.

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

Таким образом, алгоритм корректен.

Оценка сложности

Каждая платформа порождает не более одного события.

Каждое событие:

• один раз добавляется в кучу;
• один раз удаляется из кучи.

Каждая операция с кучей стоит O(log N).

Итого:

• время: O(N log N);
• память: O(N).

Это укладывается в ограничения.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> S(N), A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i] >> A[i] >> B[i];
    }

    // head[x] — начало списка событий, которые активируются в позиции x
    vector<int> head(N + 1, -1);
    vector<int> nxt(N, -1);
    vector<int> ev_r(N, -1);
    vector<int> ev_dp(N, -1);

    // min-heap из пар (dp, right_border)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    auto add_event = [&](int idx, int l, int r, int val) {
        if (l > N) return;
        r = min(r, N);
        if (l > r) return;

        ev_r[idx] = r;
        ev_dp[idx] = val;
        nxt[idx] = head[l];
        head[l] = idx;
    };

    // Стартуем на платформе 0
    add_event(0, A[0], B[0], S[0]);

    for (int pos = 1; pos <= N; ++pos) {
        // Добавляем события, которые начинаются в pos
        for (int id = head[pos]; id != -1; id = nxt[id]) {
            pq.push({ev_dp[id], ev_r[id]});
        }

        // Удаляем просроченные события
        while (!pq.empty() && pq.top().second < pos) {
            pq.pop();
        }

        // Если дошли до точки N, ответ найден
        if (pos == N) {
            if (pq.empty()) cout << -1 << '\n';
            else cout << pq.top().first << '\n';
            return 0;
        }

        // Текущая платформа недостижима
        if (pq.empty()) continue;

        int best = pq.top().first;
        int cur_dp = max(best, S[pos]);

        add_event(pos, pos + A[pos], pos + B[pos], cur_dp);
    }

    cout << -1 << '\n';
    return 0;
}

Реализация на Python

import sys
import heapq


def solve():
    input = sys.stdin.readline

    n = int(input())
    s = [0] * n
    a = [0] * n
    b = [0] * n

    for i in range(n):
        s[i], a[i], b[i] = map(int, input().split())

    head = [-1] * (n + 1)
    nxt = [-1] * n
    ev_r = [-1] * n
    ev_dp = [-1] * n

    pq = []

    def add_event(idx, l, r, val):
        if l > n:
            return
        if r > n:
            r = n
        if l > r:
            return
        ev_r[idx] = r
        ev_dp[idx] = val
        nxt[idx] = head[l]
        head[l] = idx

    # Стартовое событие от платформы 0
    add_event(0, a[0], b[0], s[0])

    for pos in range(1, n + 1):
        cur = head[pos]
        while cur != -1:
            heapq.heappush(pq, (ev_dp[cur], ev_r[cur]))
            cur = nxt[cur]

        while pq and pq[0][1] < pos:
            heapq.heappop(pq)

        if pos == n:
            if not pq:
                print(-1)
            else:
                print(pq[0][0])
            return

        if not pq:
            continue

        best = pq[0][0]
        cur_dp = max(best, s[pos])

        add_event(pos, pos + a[pos], pos + b[pos], cur_dp)

    print(-1)


if __name__ == "__main__":
    solve()

Частые ошибки

1. Неправильно обработана точка N

Это не платформа, а финиш. Поэтому при попадании в N не нужно брать максимум с какой-либо высотой.

Ответ в позиции N — просто лучший dp среди активных событий.

2. Попытка хранить dp для всех позиций и делать явные переходы

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

3. Неправильное удаление событий из heap

Нужно удалять события, у которых

right_border < current_position.

Если забыть это сделать, куча будет давать устаревшие переходы.

4. Ошибка в стартовой инициализации

Путешественник стартует на платформе 0, значит начальная цена маршрута уже равна S[0], а не 0.

Что полезно вынести из задачи

Эта задача — хороший пример техники:

• есть динамика по позициям;
• переходы задаются диапазонами;
• для текущей позиции нужен лучший кандидат среди всех активных диапазонов.

Во многих похожих задачах помогает одинаковый шаблон:

1. представить переход как событие на отрезке;
2. идти слева направо;
3. поддерживать активные события структурой данных;
4. быстро получать лучший кандидат.

Здесь для этого достаточно min-heap, потому что события только добавляются и постепенно устаревают по правой границе.

Итого

Мы свели задачу минимизации максимума по маршруту к динамике:

• dp[i] — минимальная возможная максимальная высота до платформы i;
• каждая достижимая платформа создаёт диапазон будущих переходов;
• на каждой позиции нужно взять минимум среди активных диапазонов.

Это даёт эффективное решение за O(N log N) с линейной памятью.

Такой подход проходит большие ограничения и при этом остаётся достаточно компактным в реализации.