3881. Direction Assignments with Exactly K Visible People

Description

You are given three integers n, pos, and k.

There are n people standing in a line indexed from 0 to n - 1. Each person independently chooses a direction:

'L': visible only to people on their right
'R': visible only to people on their left

A person at index pos sees others as follows:

A person i < pos is visible if and only if they choose 'L'.
A person i > pos is visible if and only if they choose 'R'.

Return the number of possible direction assignments such that the person at index pos sees exactly k people.

Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, pos = 1, k = 0

Output: 2

Explanation:

Index 0 is to the left of pos = 1, and index 2 is to the right of pos = 1.
To see k = 0 people, index 0 must choose 'R' and index 2 must choose 'L', keeping both invisible.
The person at index 1 can choose 'L' or 'R' since it does not affect the count. Thus, the answer is 2.

Example 2:

Input: n = 3, pos = 2, k = 1

Output: 4

Explanation:

Index 0 and index 1 are left of pos = 2, and there is no index to the right.
To see k = 1 person, exactly one of index 0 or index 1 must choose 'L', and the other must choose 'R'.
There are 2 ways to choose which index is visible from the left.
The person at index 2 can choose 'L' or 'R' since it does not affect the count. Thus, the answer is 2 + 2 = 4.

Example 3:

Input: n = 1, pos = 0, k = 0

Output: 2

Explanation:

There are no indices to the left or right of pos = 0.
To see k = 0 people, no additional condition is required.
The person at index 0 can choose 'L' or 'R'. Thus, the answer is 2.

Constraints:

1 <= n <= 10⁵
0 <= pos, k <= n - 1

Solutions

Solution 1: Combinatorics + Enumeration

Thinking

Each person chooses L or R so that index \(\textit{pos}\) sees exactly \(k\) people. \(n \le 10^5\) forbids \(2^n\) assignments.

A left person is visible iff they chose L, a right person iff they chose R, independent of \(\textit{pos}\)'s own facing; \(\textit{pos}\) still has two choices.

Enumerate \(a\) visible people on the left; the right then needs \(k-a\), contributing \(2\binom{\textit{pos}}{a}\binom{n-\textit{pos}-1}{k-a}\).

Factorials and inverses make each binomial \(O(1)\).

There are \(\textit{pos}\) people to the left of position \(\textit{pos}\), and \(n - \textit{pos} - 1\) people to the right.

We enumerate the number of visible people on the left, \(a\), so the number of visible people on the right is \(b = k - a\). If both \(a\) and \(b\) are valid, the answer increases by \(2 \cdot \binom{\textit{pos}}{a} \cdot \binom{n - \textit{pos} - 1}{b}\). The factor of \(2\) comes from the fact that the person at index \(\textit{pos}\) can face either 'L' or 'R'.

For the binomial coefficient \(\binom{n}{k}\), we can precompute factorials and modular inverses for fast calculation.

The time complexity is \(O(n)\), where \(n\) is the input integer \(n\). The space complexity is \(O(n)\) for storing factorials and modular inverses.

Python3JavaC++GoTypeScript

N = 100001
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
for i in range(1, N):
    f[i] = f[i - 1] * i % MOD
    g[i] = pow(f[i], MOD - 2, MOD)


def comb(n, k):
    return f[n] * g[k] * g[n - k] % MOD


class Solution:
    def countVisiblePeople(self, n: int, pos: int, k: int) -> int:
        l, r = pos, n - pos - 1
        ans = 0
        for a in range(min(k, l) + 1):
            b = k - a
            if b <= r:
                ans += 2 * comb(l, a) * comb(r, b)
                ans %= MOD
        return ans

class Solution {
    private static final int N = 100001;
    private static final int MOD = (int) 1e9 + 7;
    private static final long[] F = new long[N];
    private static final long[] G = new long[N];

    static {
        F[0] = 1;
        G[0] = 1;
        for (int i = 1; i < N; ++i) {
            F[i] = F[i - 1] * i % MOD;
            G[i] = qmi(F[i], MOD - 2, MOD);
        }
    }

    public static long qmi(long a, long k, long p) {
        long res = 1;
        while (k != 0) {
            if ((k & 1) == 1) {
                res = res * a % p;
            }
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }

    public static long comb(int n, int k) {
        return (F[n] * G[k] % MOD) * G[n - k] % MOD;
    }

    public int countVisiblePeople(int n, int pos, int k) {
        int l = pos, r = n - pos - 1;
        long ans = 0;

        for (int a = 0; a <= Math.min(k, l); ++a) {
            int b = k - a;
            if (b <= r) {
                ans = (ans + 2 * comb(l, a) % MOD * comb(r, b) % MOD) % MOD;
            }
        }
        return (int) ans;
    }
}

int N = 100001;
int MOD = 1e9 + 7;
long long f[100001];
long long g[100001];

long long qmi(long long a, long long k, long long p) {
    long long res = 1;
    while (k != 0) {
        if ((k & 1) == 1) {
            res = res * a % p;
        }
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

int init = []() {
    f[0] = 1;
    g[0] = 1;
    for (int i = 1; i < N; ++i) {
        f[i] = f[i - 1] * i % MOD;
        g[i] = qmi(f[i], MOD - 2, MOD);
    }
    return 0;
}();

long long comb(int n, int k) {
    return f[n] * g[k] % MOD * g[n - k] % MOD;
}

class Solution {
public:
    int countVisiblePeople(int n, int pos, int k) {
        int l = pos, r = n - pos - 1;
        long long ans = 0;

        for (int a = 0; a <= min(k, l); ++a) {
            int b = k - a;
            if (b <= r) {
                ans = (ans + 2 * comb(l, a) % MOD * comb(r, b) % MOD) % MOD;
            }
        }
        return ans;
    }
};

package main

const N = 100001
const MOD = 1e9 + 7

var f = make([]int, N)
var g = make([]int, N)

func qmi(a, k, p int) int {
    res := 1
    for k != 0 {
        if k&1 == 1 {
            res = res * a % p
        }
        k >>= 1
        a = a * a % p
    }
    return res
}

func init() {
    f[0], g[0] = 1, 1
    for i := 1; i < N; i++ {
        f[i] = f[i-1] * i % MOD
        g[i] = qmi(f[i], MOD-2, MOD)
    }
}

func comb(n, k int) int {
    return f[n] * g[k] % MOD * g[n-k] % MOD
}

func countVisiblePeople(n int, pos int, k int) int {
    l, r := pos, n-pos-1
    ans := 0

    for a := 0; a <= min(k, l); a++ {
        b := k - a
        if b <= r {
            ans = (ans + 2*comb(l, a)%MOD*comb(r, b)%MOD) % MOD
        }
    }
    return ans
}

const N = 100001;
const MOD = 1000000007n;

const f: bigint[] = Array(N).fill(0n);
const g: bigint[] = Array(N).fill(0n);

function qmi(a: bigint, k: bigint, p: bigint): bigint {
    let res = 1n;
    while (k > 0n) {
        if (k & 1n) res = (res * a) % p;
        k >>= 1n;
        a = (a * a) % p;
    }
    return res;
}

f[0] = 1n;
g[0] = 1n;
for (let i = 1; i < N; i++) {
    f[i] = (f[i - 1] * BigInt(i)) % MOD;
    g[i] = qmi(f[i], MOD - 2n, MOD);
}

function comb(n: number, k: number): bigint {
    return (((f[n] * g[k]) % MOD) * g[n - k]) % MOD;
}

function countVisiblePeople(n: number, pos: number, k: number): number {
    const l = pos,
        r = n - pos - 1;
    let ans = 0n;

    for (let a = 0; a <= Math.min(k, l); a++) {
        const b = k - a;
        if (b <= r) {
            ans = (ans + ((((2n * comb(l, a)) % MOD) * comb(r, b)) % MOD)) % MOD;
        }
    }

    return Number(ans);
}

3881. Direction Assignments with Exactly K Visible People

Description

Solutions

Solution 1: Combinatorics + Enumeration

Comments