Count Number of Special Subsequences (LeetCode 1955)
Đề bài
1955. Count Number of Special Subsequences – Đếm số dãy con đặc biệt (LeetCode, độ khó Hard)
Một dãy được gọi là đặc biệt nếu nó gồm một số dương các số $0$, tiếp theo là một số dương các số $1$, rồi đến một số dương các số $2$.
- Ví dụ,
[0,1,2]và[0,0,1,1,1,2]là các dãy đặc biệt. - Ngược lại,
[2,1,0],[1]và[0,1,2,0]không phải dãy đặc biệt.
Cho mảng nums (chỉ gồm các số nguyên $0$, $1$ và $2$), hãy trả về số lượng dãy con khác nhau là dãy đặc biệt. Vì đáp án có thể rất lớn, hãy trả về nó theo modulo $10^9 + 7$.
Một dãy con của mảng là dãy thu được từ mảng bằng cách xoá đi một số (hoặc không xoá) phần tử mà không làm thay đổi thứ tự các phần tử còn lại. Hai dãy con được coi là khác nhau nếu tập chỉ số được chọn của chúng khác nhau.
Ràng buộc:
- $1 \le$
nums.length$\le 10^5$ - $0 \le$
nums[i]$\le 2$
Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm countSpecialSubsequences trong class Solution. Để chạy được như một chương trình bình thường (và dùng được khung chạy tay bên dưới), mình đặt thêm định dạng:
- Dữ liệu vào: dòng đầu là số nguyên $n$ (độ dài mảng), dòng thứ hai gồm $n$ số nguyên
nums[0], nums[1], ..., nums[n-1]. - Kết quả: một số nguyên là số dãy con đặc biệt, lấy modulo $10^9 + 7$.
Input: nums = [0,1,2,2]
Output: 34
0 1 2 2
---
3Input: nums = [2,2,0,0]
Output: 04
2 2 0 0
---
0Input: nums = [0,1,2,0,1,2]
Output: 76
0 1 2 0 1 2
---
7Giải thích ví dụ của đề:
- Ví dụ 1: các dãy con đặc biệt (in đậm là phần được chọn) là [0,1,2,2], [0,1,2,2] và [0,1,2,2].
- Ví dụ 2: không có dãy con đặc biệt nào trong [2,2,0,0].
- Ví dụ 3: các dãy con đặc biệt là [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2], [0,1,2,0,1,2].
1955. Count Number of Special Subsequences (LeetCode, Hard)
A sequence is special if it consists of a positive number of 0s, followed by a positive number of 1s, then a positive number of 2s.
- For example,
[0,1,2]and[0,0,1,1,1,2]are special. - In contrast,
[2,1,0],[1], and[0,1,2,0]are not special.
Given an array nums (consisting of only integers 0, 1, and 2), return the number of different subsequences that are special. Since the answer may be very large, return it modulo $10^9 + 7$.
A subsequence of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Two subsequences are different if the set of indices chosen are different.
Example 1:
Input: nums = [0,1,2,2]
Output: 3Explanation: The special subsequences are bolded [0,1,2,2], [0,1,2,2], and [0,1,2,2].
Example 2:
Input: nums = [2,2,0,0]
Output: 0
Explanation: There are no special subsequences in [2,2,0,0].Example 3:
Input: nums = [0,1,2,0,1,2]
Output: 7Explanation: The special subsequences are bolded:
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
Constraints:
- $1 \le$
nums.length$\le 10^5$ - $0 \le$
nums[i]$\le 2$
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.
Mình giải thích thêm ví dụ 1 cho bạn nào chưa hiểu đề: mảng là [0,1,2,2] với các vị trí 0, 1, 2, 3. Dãy con đặc biệt phải có ít nhất một số 0, rồi ít nhất một số 1, rồi ít nhất một số 2, đúng thứ tự đó. Số 0 và số 1 thì chỉ có một cách chọn (vị trí 0 và 1), còn phần số 2 ta có thể chọn {2}, {3} hoặc {2, 3} – tức là 3 cách, nên đáp án là 3. Chú ý là hai dãy [0,1,2,2] và [0,1,2,2] tuy giá trị giống nhau (đều là 0,1,2) nhưng chọn ở các vị trí khác nhau nên vẫn được tính là 2 dãy khác nhau.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Duyệt tất cả dãy con – O(2^N · N)
Trước khi vào lời giải chính, mình làm nhanh cách "làm theo đề" để các bạn thấy rõ bài đang đếm cái gì. Mỗi dãy con ứng với một tập chỉ số, ta biểu diễn bằng một số nhị phân mask $n$ bit: bit thứ $i$ bằng 1 nghĩa là chọn nums[i]. Với mỗi mask từ $1$ tới $2^n - 1$, ta lấy ra dãy con b rồi kiểm tra xem b có dạng 0..0 1..1 2..2 hay không:
- Đi một con trỏ
ptừ đầu dãyb, lần lượt "ăn" hết các số 0 liên tiếp, rồi các số 1 liên tiếp, rồi các số 2 liên tiếp. - Nếu có loại nào ăn được 0 phần tử thì dãy không đặc biệt (đề yêu cầu mỗi loại phải có số lượng dương).
- Ăn xong 3 loại mà
pchưa tới cuối dãy (ví dụ[0,1,2,0]) thì cũng không đặc biệt.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// b có dạng 0..0 1..1 2..2 (mỗi loại ít nhất 1 số) hay không
bool isSpecial(vector<int>& b) {
int k = (int) b.size(), p = 0;
for (int v = 0; v <= 2; v++) {
int cnt = 0;
while (p < k && b[p] == v) {
p++;
cnt++;
}
if (cnt == 0) return false;
}
return p == k;
}
int countSpecialSubsequences(vector<int>& nums) {
int n = (int) nums.size();
long long ans = 0;
for (int mask = 1; mask < (1 << n); mask++) {
vector<int> b;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) b.push_back(nums[i]);
}
if (isSpecial(b)) ans++;
}
return ans % 1000000007;
}
};
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
Solution sol;
cout << sol.countSpecialSubsequences(nums);
return 0;
}import sys
from typing import List
class Solution:
# b có dạng 0..0 1..1 2..2 (mỗi loại ít nhất 1 số) hay không
def isSpecial(self, b: List[int]) -> bool:
k, p = len(b), 0
for v in range(3):
cnt = 0
while p < k and b[p] == v:
p += 1
cnt += 1
if cnt == 0:
return False
return p == k
def countSpecialSubsequences(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for mask in range(1, 1 << n):
b = [nums[i] for i in range(n) if mask >> i & 1]
if self.isSpecial(b):
ans += 1
return ans % 1000000007
def main():
data = sys.stdin.read().split()
n = int(data[0])
nums = list(map(int, data[1:1 + n]))
print(Solution().countSpecialSubsequences(nums))
if __name__ == "__main__":
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng
btối đa $n$ phần tử nên là $O(N)$. - Thời gian: có $2^n$ dãy con, mỗi dãy mất $O(n)$ để lấy ra và kiểm tra, tổng cộng $O(2^N \cdot N)$.
Cách 2Quy hoạch động theo "số cuối cùng đã chọn" – O(N)
Bài này giải quyết theo Quy Hoạch Động với độ phức tạp $O(N)$. Ý tưởng là đi lần lượt từng phần tử của mảng, với mỗi phần tử ta chỉ có 2 lựa chọn: không chọn hoặc chọn nó vào dãy con. Để biết chọn vào có hợp lệ hay không, ta chỉ cần nhớ số cuối cùng của dãy con đang xây dựng.
0..0, 0..0 1..1 hoặc 0..0 1..1 2..2 (mỗi khúc có ít nhất 1 số).Vì dãy thỏa mãn phải bắt đầu bằng số 0, mà ta cần gán một bài toán cơ sở, nên tạm thời ta coi như trước khi chọn gì thì "số cuối" là $-1$: $f[0][-1] = 1$ (có đúng 1 cách là dãy rỗng). Tuy nhiên mảng không chấp nhận chỉ số âm, nên ta dùng cột số 3 để thay cho $-1$:
Với mỗi $f[i][j] \gt 0$ hiện tại, ta có những tình huống sau:
- Không chọn phần tử thứ $i + 1$ (tức
nums[i]trong code, đánh số từ 0): số cuối không đổi, $f[i + 1][j] \mathrel{+}= f[i][j]$. - Chọn phần tử thứ $i + 1$, có những tình huống sau:
- Nếu $j = 3$ (chưa chọn gì), đồng thời
nums[i]$= 0$ thì ta mở đầu dãy bằng số 0 này: $f[i + 1][0] \mathrel{+}= f[i][3]$. - Nếu $j \ne 3$, xét
nums[i]$= j$ (nối thêm một số cùng loại) hoặcnums[i]$= j + 1$ (chuyển sang khúc tiếp theo), khi đó cập nhật $f[i + 1][\text{nums}[i]] \mathrel{+}= f[i][j]$.
- Nếu $j = 3$ (chưa chọn gì), đồng thời
Các bạn để ý: nếu nums[i] $= 1$ mà $j = 2$ thì không được chọn (vì 1 không được đứng sau 2), nếu nums[i] $= 2$ mà $j = 0$ cũng không được (thiếu khúc số 1), và $j = 3$ chỉ được nối với số 0. Gom lại, mỗi bước chỉ thay đổi đúng một ô:
nums[i]$= 0$: $f[i+1][0] = 2 \cdot f[i][0] + f[i][3]$.nums[i]$= 1$: $f[i+1][1] = 2 \cdot f[i][1] + f[i][0]$.nums[i]$= 2$: $f[i+1][2] = 2 \cdot f[i][2] + f[i][1]$.
Minh hoạ bảng quy hoạch động
Em nhập mảng nums (tối đa 12 số) rồi bấm Tiếp. Mỗi bước xét thêm một phần tử, bảng $f$ có thêm một hàng; bên dưới liệt kê luôn các dãy con đang thuộc từng trạng thái (ghi bằng các vị trí đã chọn), dãy mới sinh ra ở bước này tô vàng:
Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên. Bảng dp có $n + 1$ hàng, 4 cột (cột 3 thay cho "$-1$"), mỗi lần cộng xong lấy modulo luôn. Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int dp[100005][4];
class Solution {
public:
int countSpecialSubsequences(vector<int>& nums) {
int n = (int) nums.size();
memset(dp, 0, sizeof(dp));
dp[0][3] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= 3; j++) {
(dp[i + 1][j] += dp[i][j]) %= MOD;
if (j == 3) {
if (nums[i] == 0) {
(dp[i + 1][0] += dp[i][j]) %= MOD;
}
}
else {
if (nums[i] == j || nums[i] == j + 1) {
(dp[i + 1][nums[i]] += dp[i][j]) %= MOD;
}
}
}
}
return dp[n][2];
}
};
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
Solution sol;
cout << sol.countSpecialSubsequences(nums);
return 0;
}import sys
from typing import List
MOD = 1000000007
class Solution:
def countSpecialSubsequences(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * 4 for _ in range(n + 1)]
dp[0][3] = 1
for i in range(n):
for j in range(4):
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
if j == 3:
if nums[i] == 0:
dp[i + 1][0] = (dp[i + 1][0] + dp[i][j]) % MOD
else:
if nums[i] == j or nums[i] == j + 1:
dp[i + 1][nums[i]] = (dp[i + 1][nums[i]] + dp[i][j]) % MOD
return dp[n][2]
def main():
data = sys.stdin.read().split()
n = int(data[0])
nums = list(map(int, data[1:1 + n]))
print(Solution().countSpecialSubsequences(nums))
if __name__ == "__main__":
main()Khung chạy tay bên dưới chạy đúng từng dòng của code C++ ở trên (cả hàm main lẫn hàm trong class Solution). Ô vàng trong bảng là $dp[i][j]$ đang được dùng, ô viền vàng là ô vừa được cộng thêm:
Đánh giá độ phức tạp của cách làm này:
- Không gian: bảng
dpcó $(n + 1) \times 4$ ô nên là $O(N)$. (Nếu muốn, các bạn có thể chỉ giữ 4 biến cho hàng hiện tại theo công thức gọn ở trên để còn $O(1)$, nhưng với $n \le 10^5$ thì không cần.) - Thời gian: hai vòng lặp, vòng ngoài $n$ lần, vòng trong 4 lần, nên là $O(4 \cdot N) = O(N)$ nha các bạn.
% MOD ngay. Hai số đều nhỏ hơn $10^9 + 7$ nên tổng nhỏ hơn $2 \cdot (10^9 + 7) \approx 2 \cdot 10^9$, vẫn vừa kiểu int (tối đa khoảng $2.147 \cdot 10^9$). Nếu các bạn cộng dồn nhiều lần rồi mới lấy modulo thì phải dùng long long để khỏi tràn số.dp[100005][4] khai báo toàn cục cho khỏi tràn stack. Trên LeetCode hàm countSpecialSubsequences được gọi nhiều lần với nhiều test trong cùng một lần chạy, nên đầu hàm phải memset lại về 0, nếu không thì dữ liệu test trước sẽ "dính" sang test sau.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét