Skip to content

3881. Direction Assignments with Exactly K Visible People

SourceBiweekly Contest 179 Q2DifficultyMediumRating1760

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

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)\), and the space complexity is \(O(n)\), where \(n\) is the input integer \(n\).

 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
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