Skip to content

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 109 + 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 <= 105
  • 0 <= pos, k <= n - 1

Solutions

Solution 1: Combinatorics + Enumeration

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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);
}

Comments