0516HardArrayBinary SearchDynamic ProgrammingGraph TheoryTopological SortHeap (Priority Queue)Shortest Path

Fibre Restoration Grade

Tracked in this browser only

Trains the technique from

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 carrier is bringing a backbone back up. Stations are numbered from 0 to n - 1, where n is the length of online, and online[i] says whether station i is powered up. Traffic may pass through a station only when that station is powered up, and that includes the two ends of the run.

links[t] = [u, v, w] is a one-way fibre from station u to station v with u < v. The number w is that fibre's grade, and splicing better fibre costs more, so restoring that link also draws w credits. Two stations may be joined by more than one fibre.

A run is a sequence of links leading from station 0 to station n - 1. Restoring a run draws the total of the grades of its links, and the carrier has budget credits to spend, so a run is affordable when that total is at most budget. The rating of a run is the smallest grade among its links, because the run is only as good as its worst fibre.

Return the largest rating over all affordable runs whose stations are all powered up. Every grade is at least 1, so return -1 when no such run exists.

Examples

Example 1

Input: links = [[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 3]], online = [true, true, true, true], budget = 10
Output: 3

The run through station 2 restores two links of grade 3 for 6 credits and rates 3, which is within the budget of 10 credits.

Example 2

Input: links = [[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 3]], online = [true, true, true, true], budget = 20
Output: 10

The run through station 1 restores two links of grade 10 for 20 credits and rates 10, which is exactly the budget.

Example 3

Input: links = [[0, 2, 6]], online = [true, true, true], budget = 0
Output: -1

The only run needs 6 credits and no credits are available, so nothing can be restored.

Constraints

2 <= n == online.length <= 10^4
1 <= links.length <= 5 * 10^4
links[t].length == 3
0 <= u < v < n
1 <= w <= 10^6
0 <= budget <= 10^9

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 best_link_grade(links: list[list[int]], online: list[bool], budget: int) -> int:

Java

public int bestLinkGrade(int[][] links, boolean[] online, long budget)

The intended approach

Time O(e log e): sorting the links once, then O(log e) feasibility sweeps of O(e) each.Space O(v + e): the usable link list and the cost table.

Fix a target rating and ask only whether some affordable run avoids every link below it. Raising the target can only take links away, so the cheapest qualifying run never gets cheaper as the target rises, which makes the answer the largest target that still passes, found by binary search over the distinct grades. One test sweeps the links sorted by their lower station, relaxing a running cheapest-cost-per-station table; since every link runs from a lower station to a higher one, a station's cost is final before any link leaving it is read.

Pythonentry point: best_link_grade

def best_link_grade(links, online, budget):
    # Raising the target grade only ever removes links, so the cheapest chain that
    # uses nothing below the target gets no cheaper as the target rises. That makes
    # the affordability test monotone and the target itself binary searchable. Each
    # test is one sweep of the links in station order, which is a valid order
    # because every link runs from a lower station to a higher one.
    # O(e log e) time, O(v + e) space.
    stations = len(online)
    if not online[0] or not online[stations - 1]:
        return -1
    usable = [link for link in links if online[link[0]] and online[link[1]]]
    if not usable:
        return -1
    usable.sort(key=lambda link: link[0])
    grades = sorted({link[2] for link in usable})
    INF = float("inf")

    def cheapest(target):
        cost = [INF] * stations
        cost[0] = 0
        for u, v, w in usable:
            if w < target or cost[u] == INF:
                continue
            if cost[u] + w < cost[v]:
                cost[v] = cost[u] + w
        return cost[stations - 1]

    if cheapest(grades[0]) > budget:
        return -1
    lo, hi = 0, len(grades) - 1
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if cheapest(grades[mid]) <= budget:
            lo = mid
        else:
            hi = mid - 1
    return grades[lo]

The obvious version

Walk every run out of station 0 with an explicit stack, carrying the credits spent so far and the weakest grade used so far, abandoning a partial run as soon as it passes the budget or reaches an unpowered station, and keep the best rating among the runs that arrive at the last station. Exponential in the number of links.

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_best_link_grade(links, online, budget):
    stations = len(online)
    if not online[0]:
        return -1
    outgoing = {}
    for u, v, w in links:
        outgoing.setdefault(u, []).append((v, w))
    best = -1
    stack = [(0, 0, None)]
    while stack:
        node, spent, weakest = stack.pop()
        if node == stations - 1:
            if weakest is not None and spent <= budget and weakest > best:
                best = weakest
            continue
        for v, w in outgoing.get(node, []):
            if not online[v]:
                continue
            if spent + w > budget:
                continue
            stack.append((v, spent + w, w if weakest is None else min(weakest, w)))
    return best

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