0701MediumDynamic ProgrammingQueueSimulation

Couriers Still Holding the Shortcut

Tracked in this browser only

Trains the technique from

LeetCode 2327Number of People Aware of a Secret

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A depot's couriers pass a routing shortcut along by word of mouth. On day 1 exactly one courier knows it.

A courier who learns the shortcut on day d behaves as follows:

on each of the days d + quiet, d + quiet + 1, ..., d + stale - 1 that courier explains it to exactly one courier who has never heard it;
at the start of day d + stale the courier's notes go stale: from that day on the courier no longer knows the shortcut and never explains it again.

The depot employs far more couriers than the shortcut can ever reach, so every explanation lands on someone who has never heard it. Since quiet is smaller than stale, every courier gets at least one day of explaining.

Return how many couriers know the shortcut at the end of day n. The count grows quickly, so return it modulo 1000000007.

Examples

Example 1

Input: n = 9, quiet = 3, stale = 5
Output: 5

The first courier learns it on day 1 and explains it on days 4 and 5, so one courier learns on day 4 and one on day 5. The day-4 courier explains on days 7 and 8, and the day-5 courier explains on days 8 and 9. Learning days are therefore 1, 4, 5, 7, 8, 8 and 9, seven couriers in all. Notes from day 1 go stale at the start of day 6 and notes from day 4 at the start of day 9, leaving five couriers at the end of day 9.

Example 2

Input: n = 5, quiet = 1, stale = 4
Output: 14

Each courier explains the shortcut on the three days after learning it. Counting the couriers who learn on each day gives 1 on day 1, 1 on day 2, 2 on day 3, 4 on day 4 and 7 on day 5, fifteen couriers in all. Only the first courier's notes have gone stale by the end of day 5, so fourteen couriers still know the shortcut.

Example 3

Input: n = 7, quiet = 6, stale = 7
Output: 2

The first courier's only explaining day is day 7, so one more courier learns the shortcut that day. Neither courier's notes have gone stale by the end of day 7.

Constraints

2 <= n <= 1000
1 <= quiet <= 1000
2 <= stale <= 1000
quiet is strictly smaller than stale, and stale is at most n.
Return the count modulo 1000000007.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def couriers_knowing_shortcut(n: int, quiet: int, stale: int) -> int:

Java

public int couriersKnowingShortcut(int n, int quiet, int stale)

The intended approach

Time O(n) for n days: one pass building the daily group sizes and one pass over the surviving groups.Space O(n) for the per-day group sizes.

Group couriers by the day they learned the shortcut and count each group instead of each courier. A group that learned on day `d` explains the shortcut on `stale - quiet` consecutive days, so the number of couriers learning on any given day is the total size of the groups whose explaining window covers that day. That window slides forward one day at a time, so a single running total is kept: the group starting to explain today is added and the group that explained for the last time yesterday is subtracted. At the end the groups still holding the shortcut are exactly those from the last `stale` days.

Pythonentry point: couriers_knowing_shortcut

MOD = 1000000007


def couriers_knowing_shortcut(n, quiet, stale):
    # O(n): learned[d] is how many couriers first hear the shortcut on day d.
    # `sharing` is kept as a running window total of the cohorts that explain
    # the shortcut on the current day, so each day costs O(1).
    learned = [0] * (n + 1)
    learned[1] = 1
    sharing = 0
    for day in range(2, n + 1):
        opens = day - quiet          # cohort whose first explaining day is today
        if opens >= 1:
            sharing += learned[opens]
        closes = day - stale         # cohort that explained for the last time yesterday
        if closes >= 1:
            sharing -= learned[closes]
        sharing %= MOD
        learned[day] = sharing
    total = 0
    for day in range(max(1, n - stale + 1), n + 1):
        total += learned[day]
    return total % MOD

The obvious version

For each day, scan every earlier day and add that day's group whenever its explaining window covers the current day, then add up the groups whose notes have not yet gone stale. Quadratic in the number of days, with no running window at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_couriers_knowing_shortcut(n, quiet, stale):
    learned = [0] * (n + 1)
    learned[1] = 1
    for day in range(2, n + 1):
        arrivals = 0
        for src in range(1, day):
            if src + quiet <= day <= src + stale - 1:
                arrivals += learned[src]
        learned[day] = arrivals % 1000000007
    alive = 0
    for day in range(1, n + 1):
        if day + stale > n:
            alive += learned[day]
    return alive % 1000000007

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in