0880MediumArraySimulation

Restless Deckhands on Paired Shifts

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 crew of n deckhands is split into shift duos. preferences[i] lists every other deckhand in the order deckhand i would rather work with them, best first, so it holds n - 1 names and never names i. pairs gives the duos, and every deckhand appears in exactly one duo.

Deckhand a, paired with b, is restless when some deckhand c, paired with d, satisfies both of these at once:

a would rather work with c than with b
c would rather work with a than with d

Return how many deckhands are restless.

Examples

Example 1

Input: n = 6, preferences = [[2, 1, 3, 4, 5], [3, 0, 2, 4, 5], [0, 3, 1, 4, 5], [1, 2, 0, 4, 5], [5, 0, 1, 2, 3], [4, 0, 1, 2, 3]], pairs = [[0, 1], [2, 3], [4, 5]]
Output: 4

Deckhands 0 and 2 top each other's lists yet are paired elsewhere, and so do 1 and 3, which leaves all four of them restless. Deckhands 4 and 5 are each other's first choice and are already paired, so neither is.

Example 2

Input: n = 4, preferences = [[2, 1, 3], [0, 2, 3], [0, 3, 1], [2, 0, 1]], pairs = [[0, 1], [2, 3]]
Output: 2

Deckhand 0 would rather work with 2 than with 1, and 2 would rather work with 0 than with 3, so both are restless. Deckhands 1 and 3 already have their first choice.

Example 3

Input: n = 6, preferences = [[1, 2, 3, 4, 5], [0, 2, 3, 4, 5], [3, 0, 1, 4, 5], [2, 0, 1, 4, 5], [5, 0, 1, 2, 3], [4, 0, 1, 2, 3]], pairs = [[0, 1], [2, 3], [4, 5]]
Output: 0

Every deckhand is paired with the one at the top of their own list, so no swap could suit both sides.

Constraints

2 <= n <= 500
n is even
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] never names i
The entries of preferences[i] are all different
pairs.length == n / 2
pairs[i].length == 2
The two deckhands in a duo are different
0 <= pairs[i][0] <= n - 1
0 <= pairs[i][1] <= n - 1
Every deckhand appears in exactly one duo

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 unhappy_friends(n: int, preferences: list[list[int]], pairs: list[list[int]]) -> int:

Java

public int unhappyFriends(int n, int[][] preferences, int[][] pairs)

The intended approach

Time O(n^2) for the rank tables and the scan, which is the size of the input itself.Space O(n^2) for the rank tables.

The test asks, for each deckhand, whether anyone they prefer to their own partner prefers them back over theirs. Both halves are questions about position in a preference list, so turn each list inside out once: `rank[i][j]` records where `j` sits in `i`'s order, which makes any single comparison a lookup. Record each deckhand's partner in the same sweep. Then for every deckhand, walk their own preference list from the front and stop at their partner, since anyone further down is not preferred; for each name reached before that, one rank lookup settles whether the feeling runs both ways, and the first such name makes the deckhand restless.

Pythonentry point: unhappy_friends

def unhappy_friends(n, preferences, pairs):
    rank = [[0] * n for _ in range(n)]
    for i in range(n):
        for pos, j in enumerate(preferences[i]):
            rank[i][j] = pos
    partner = [0] * n
    for a, b in pairs:
        partner[a] = b
        partner[b] = a
    restless = 0
    for a in range(n):
        b = partner[a]
        # anyone sitting past the partner is less preferred, so stop there
        for c in preferences[a]:
            if c == b:
                break
            if rank[c][a] < rank[c][partner[c]]:
                restless += 1
                break
    return restless

The obvious version

Work from the duos rather than from the deckhands: take every two duos and test all four cross-duo couplings by reading positions straight out of the preference lists with a search each time. A coupling where both sides prefer each other to their partners marks both of them restless. No rank tables and no early stopping.

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_unhappy_friends(n, preferences, pairs):
    def prefers(who, over_this, than_this):
        # position in the preference list, found by searching it each time
        first = -1
        second = -1
        for pos in range(len(preferences[who])):
            if preferences[who][pos] == over_this:
                first = pos
            if preferences[who][pos] == than_this:
                second = pos
        return first < second

    partner = {}
    for a, b in pairs:
        partner[a] = b
        partner[b] = a
    restless = set()
    m = len(pairs)
    for i in range(m):
        for j in range(i + 1, m):
            for a in pairs[i]:
                for c in pairs[j]:
                    if prefers(a, c, partner[a]) and prefers(c, a, partner[c]):
                        restless.add(a)
                        restless.add(c)
    return len(restless)

How this problem was checked

Reference solution executed against 10 test cases — 10 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