1359. Count All Valid Pickup and Delivery Options

LeetCode задача 1359

Задача

Дано n заказов, каждый заказ состоит из услуг по приему и доставке.

Необходимо подсчитать все возможные последовательности приема/доставки так, чтобы доставка(i) всегда шла после приема(i).

Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.

Подсказки

Использовать комбинаторный подход.

Для каждого нового заказа у нас есть 2 * (2n-1) способов добавить его в текущую последовательность.

Мы используем данную формулу, так как:

Новый заказ может быть вставлен на любое место среди существующих заказов (2n-1 мест). У нас 2 операции (прием и доставка) для каждого заказа.

Подход

Начнем с самого начала,

1. Мы получили 1-й заказ n=1

   Мы можем расставить только в одном порядке: P1 D1

2. Теперь мы получили 2-й заказ n=2, и нужно добавить к предыдущему и расставить P2, D2.

   Куда мы можем поставить P2?

   На первое место, второе или третье. И не можем поставить на последнее, т.к. последнее место всегда будет части доставки(D).

   Попробуем расставить:

   1. Всего 3 возможных позиции куда поставить 2-й (P2) заказ. (Обозначим перестановки от предыдущего заказа как X):
   2. Если P2 X X, то у P2 и D2 из расстановок - 3 возможных варианта: P2 D2 X X или P2 X D2 X или P2 X X D2
   3. Если X P2 X, - 2 возможных варианта: X P2 D2 X или X P2 X D2
   4. Если X X P2, - 1 возможный вариант: X X P2 D2
   5. Отсюда мы получаем формулу, что для n заказа - n*2 операций, и n*2 -1 возможных комбинаций.
   6. Итого получаем, что для второго заказа возможных выборов перестановок 3+2+1 - 6
   7. Также мы видим, что X - расстановки с предыдущего заказа тоже меняли позиции, поэтому общее количество комбинаций будет равно произведению количества комбинаций текущего заказа и предыдущего - 6*1=6

3. Теперь мы получили 3-й заказ n=3,

   1. По аналогии с предыдущим, перестановок получается n*2=6
   2. Комбинаций получается 5+4+3+2+1 = 15
   3. Перемножаем с комбинациями из предыдущего заказа 15*6=90

Алгоритм

1. Для каждого заказа от 1 до n:

2. Рассчитываем количество способов добавления заказа в текущую последовательность.

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

       2*n * (2*n-1) // 2
       # для n:3 2*3=6, 2*3-1=5, 6*5//2=15
   

3. Умножаем текущее количество комбинаций на количество способов добавления заказа.

Решение

def countOrders(n: int) -> int:
    MOD = 10**9 + 7
    res = 1

    for x in range(2, n + 1):
        prev_order_combinations = res
        order_combinations = (2 * x) * (2 * x - 1) // 2
        res = prev_order_combinations * order_combinations % MOD

    return res