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 < posis visible if and only if they choose'L'. - A person
i > posis 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 ofpos = 1. - To see
k = 0people, 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 = 1person, 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 is2 + 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 = 0people, no additional condition is required. - The person at index 0 can choose
'L'or'R'. Thus, the answer is 2.
Constraints:
1 <= n <= 1050 <= 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 | |
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 | |
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 | |
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 | |
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 | |