Chia Hết (DPRCDIV)
Đề bài
DPRCDIV – Chia hết
Bạn có một danh sách các con số $a_1, a_2, \ldots, a_n$ và một số nguyên dương $m$. Kiểm tra xem có thể chọn một số phần tử thuộc dãy $a$ sao cho tổng của chúng chia hết cho $m$ hay không.
Dữ liệu vào:
- Dòng đầu tiên chứa hai số $n$ và $m$ – kích thước của dãy ban đầu và số sao cho tổng đó chia hết cho nó.
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$.
Kết quả: Trong dòng đơn in YES (không có dấu ngoặc kép) nếu tồn tại dãy cần tìm hoặc NO (không có dấu ngoặc kép) nếu dãy đó không tồn tại.
Ràng buộc: $1 \le n \le 10^6$; $2 \le m \le 10^3$; $0 \le a_i \le 10^9$.
3 5
1 2 3YES1 6
5NO6 6
5 5 5 5 5 5YESLờ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 😇.
Bên trong bài sẽ sử dụng tới đệ quy và ứng dụng nó để vét cạn. Bài này cũng là một biến thể của bài toán tổng tập hợp con (kiểm tra hoặc đếm xem có bao nhiêu tập con có tổng bằng $sum$), anh em nào chưa nắm rõ 2 phần này thì nên ôn lại trước nha. Đặc biệt ở cuối bài có một "cú lừa" rất đẹp của nguyên lý Dirichlet mà mình rất thích 😁.
Tóm tắt đề bài một cách đơn giản nhất: cho 2 số nguyên dương $n, m$ $(1 \le n \le 10^6;\ 2 \le m \le 10^3)$ và một dãy số nguyên không âm $a_i$ $(0 \le a_i \le 10^9)$. Hãy kiểm tra xem trong dãy có tập con nào (không tính tập rỗng) có tổng chia hết cho $m$ hay không. Có thì in YES, không thì in NO.
- Ví dụ 1: $n = 3$, $m = 5$, $a = \{1, 2, 3\}$. Ta chọn phần tử $2$ và $3$, tổng là $5$ chia hết cho $5$ ⇒ YES.
- Ví dụ 2: $n = 1$, $m = 6$, $a = \{5\}$. Tập con khác rỗng duy nhất là $\{5\}$, tổng $5$ không chia hết cho $6$ ⇒ NO.
- Ví dụ 3: $n = 6$, $m = 6$, sáu số $5$. Chọn cả 6 số được tổng $30$ chia hết cho $6$ ⇒ YES.
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 1Vét cạn mọi tập con bằng đệ quy – O(2^n)
Cách làm đơn giản nhất là vét cạn, tức là thử mọi trường hợp có thể: tạo ra mọi tập con, tính tổng rồi kiểm tra tổng đó có chia hết cho $m$ không. Ta làm như sau:
- Hàm:
bool Try(i, sum)trả về liệu có tập con nào trong khoảng từ $i$ tới $n$ mà (tổng tập con đó + sum) chia hết cho $m$ không. Biến $i$ là vị trí đang xét, $sum$ là tổng của tập con đã lựa trước đó. - Điều kiện dừng 1: khi $i = n + 1$ tức là đã đi hết mảng. Ta kiểm tra $sum \ne 0$ và $sum$ chia hết cho $m$ thì trả về
true, ngược lại trả vềfalse. Tại sao phải khác $0$? Vì ta đang vét cạn nên sẽ có trường hợp không chọn phần tử nào, tức tập rỗng có tổng $0$, mà tập rỗng thì không được chọn:if(sum && sum % m == 0) return true;. - Điều kiện dừng 2: qua được điều kiện 1 thì chắc chắn $i \le n$. Lúc này ta kiểm tra
a[i] == 0. Tại sao? Vì ở trên để loại tập rỗng ta đã đòi $sum \ne 0$, nhỡ mảng có phần tử bằng $0$ thì sao? Chọn riêng phần tử đó thì $m$ bằng bao nhiêu cũng chia hết (số $0$ chia hết cho mọi số khác $0$). Vậy gặpa[i] == 0thìreturn trueluôn. - Xử lý chạy: ở phần tử thứ $i$ ta có thể không chọn – gọi
Try(i + 1, sum), tổng giữ nguyên; hoặc chọn – gọiTry(i + 1, sum + a[i]). Chỉ cần 1 trong 2 cách đúng là đủ, nênreturn Try(i + 1, sum) || Try(i + 1, sum + a[i]);.
true thì kết quả là true, chỉ khi cả 2 vế false mới ra false. Đặc biệt C++ tính vế trái trước, nếu vế trái đã true thì không thèm tính vế phải nữa. Nhờ vậy khi tìm được 1 tập con thoả mãn là đệ quy dừng "vèo" luôn. Các bạn để ý chỗ này trong khung chạy tay nhé.Sau đây là source code về ý tưởng trên của mình cho anh em nào cần tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll n, m;
ll a[(int)1e6 + 5];
bool Try(int i, ll sum) {
if(i == n + 1) {
if(sum && sum % m == 0) {
return true;
}
return false;
}
if(a[i] == 0) {
return true;
}
return Try(i + 1, sum) || Try(i + 1, sum + a[i]);
}
int main() {
// freopen("dprcdiv.inp", "r", stdin);
// freopen("dprcdiv.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
if(Try(1, 0)) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}import sys
sys.setrecursionlimit(10**6 + 10)
def Try(i, s):
if i == n + 1:
if s and s % m == 0:
return True
return False
if a[i] == 0:
return True
return Try(i + 1, s) or Try(i + 1, s + a[i])
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
if Try(1, 0):
print("YES")
else:
print("NO")Trong code gốc mình có 2 dòng freopen("dprcdiv.inp", ...) / freopen("dprcdiv.out", ...) để đọc ghi file. Khi nộp trên CLUE OJ (đọc/ghi chuẩn) thì các bạn để chúng ở dạng chú thích như trên là được nhé.
Giải thích một số chỗ trong cách làm ở trên:
- 2 dòng đầu tiên của hàm main (
ios_base::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn code C++ (để hiểu vì sao thì cứ gõ mấy từ này lên Google là ra rất nhiều bài viết giải thích nhé). Bài này đầu vào có thể lên tới $10^6$ số nên thêm 2 dòng đó vào sẽ cải thiện tốc độ lên rất nhiều. ll a[(int)1e6 + 5];mình khai báo mảng $a$ toàn cục cho tiện; mảng có tối đa $10^6$ phần tử, mình thường cộng thêm 5 cho chắc.if(sum && sum % m == 0)chính làif(sum != 0 && sum % m == 0); viếtsumđứng một mình thì trình biên dịch tự hiểu làsum != 0.Try(1, 0): bắt đầu từ phần tử đầu tiên nên $i = 1$, lúc đầu chưa chọn gì nên $sum = 0$.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$ vì chỉ dùng một mảng $a$ (cộng thêm độ sâu đệ quy tối đa $n$).
- Thời gian: $O(2^n)$. Ở mỗi phần tử ta có 2 lựa chọn là chọn hoặc không chọn, nên $n$ phần tử có tối đa $2^n$ cách chọn.
32 872
27 34 10 29 2 47 31 15 17 35 49 2 43 2 4 18 43 46 43 42 44 8 48 41 21 22 44 42 32 20 7 3NO, nên code trâu phải thử đủ $2^{32} \approx 4.3$ tỉ cách. Mình đo lại trên máy mất khoảng 21 giây mới ra NO. Có thể dùng kỹ thuật meet in the middle để cải tiến, nhưng cũng chỉ "gánh" được $n$ tới tầm 50 thôi. Nếu cho $n = 60$, thậm chí $n = 10^6$ mà kết quả là NO thì code trâu chắc chắn không thể AC nổi.Vậy giờ mình sẽ cùng đến với cách cải tiến hơn nha.
Cách 2Quy hoạch động theo số dư, kiểu "lan toả" – O(n·m)
Thử "nhớ" kết quả Try(i, sum)? Chưa ổn!
Như bài tổng tập con, ta có thể cải tiến code trâu thành quy hoạch động top-down (đệ quy có nhớ) hoặc bottom-up. Đầu vào hàm Try() là 2 biến $i$ và $sum$, vậy tạo mảng 2 chiều lưu kết quả Try(i, sum) đã tính để gặp lại khỏi tính lại. Trường hợp tệ nhất ta phải lấp đầy mảng đó, với $i \le n$ và $sum \le$ tổng tất cả phần tử. Mà tổng có thể lên tới $10^6 \cdot 10^9 = 10^{15}$, nên cần cỡ $10^6 \cdot 10^{15} = 10^{21}$ phép tính – 1 giây chạy được khoảng $10^8$ phép thì cần $10^{13}$ giây, tầm 317 nghìn năm 😱. Mảng to vậy cũng không tạo nổi. Bottom-up cũng là lấp đầy mảng 2 chiều đó nên cũng y vậy.
Cải tiến: chỉ cần giữ phần dư
Quay về cách quay lui, theo đồng dư thức ta có $(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m$. Nghĩa là việc cộng hết các phần tử của tập con rồi cuối cùng mới chia dư, cũng bằng việc mỗi khi thêm một phần tử thì chia dư luôn. Ta sửa hàm Try() một chút:
bool Try(int i, ll sum, int cnt) {
if(i == n + 1) {
if(cnt && sum == 0) {
return true;
}
return false;
}
if(a[i] == 0) {
return true;
}
return Try(i + 1, sum, cnt) || Try(i + 1, (sum + a[i]) % m, cnt + 1);
}Biến cnt đếm số phần tử của tập con đang chọn, chỉ để tránh tập rỗng. Giờ $sum$ lưu phần dư của tổng tập con đã chọn, nên $sum = 0$ là chia hết rồi; nhưng tập rỗng cũng có $sum = 0$, nên phải thêm điều kiện cnt khác $0$: if(cnt && sum == 0). Không chọn phần tử $i$ thì gọi Try(i + 1, sum, cnt); chọn thì gọi Try(i + 1, (sum + a[i]) % m, cnt + 1).
Với vài sửa đổi như vậy thì độ phức tạp vẫn là $O(2^n)$, chả cải thiện được tí nào. Nhưng ta được một thứ rất hay: $sum$ giờ chỉ nằm trong đoạn $0 \le sum \le m - 1$, mà $m \le 10^3$ nên $sum$ tối đa chỉ $999$. So với $10^{15}$ lúc nãy là vô cùng nhỏ!
cnt thì sẽ sai. Ví dụ $Try(n, 0, 0) = Try(n + 1, 0, 0) \;||\; Try(n + 1, a[n] \bmod m, 1)$: vế trái false vì tập rỗng, vế phải cũng false nếu $a[n]$ không chia hết cho $m$, thế là ta lưu ô $[n][0] = $ false. Lần sau đến phần tử $n$ với $sum = 0$ nhưng tập con khác rỗng (đã chọn vài phần tử có tổng chia hết) thì lại lấy ra false – sai rồi. Vậy nên phần này mình khuyên anh em dùng bottom-up, tức là tạo ra công thức truy hồi.4 bước quy hoạch động
Bước 1. Tạo mảng bool $F[n + 1][m]$, dựa theo 2 biến $i$, $sum$ của hàm Try() cải tiến ($i \le n$, $sum \le m - 1$). Ví dụ $F[3][4] = 1$ nghĩa là có tập con nằm trong 3 phần tử đầu tiên có tổng chia $m$ dư $4$; còn $F[3][4] = 0$ nghĩa là không có.
Bước 2. Lúc đầu gán toàn bộ mảng bằng false. Dễ thấy $F[i][a[i] \bmod m] = $ true, vì khi xét tới phần tử $i$ thì bản thân một mình $a[i]$ cũng là một tập con, có phần dư $a[i] \bmod m$. Xét 1 phần tử đầu thì chỉ có đúng tập con $\{a[1]\}$, nên $F[1][a[1] \bmod m] = $ true.
Bước 3. Ta cần biết trong $n$ phần tử có tập con nào có tổng chia $m$ dư $0$ không, chính là $F[n][0]$.
Bước 4 (kiểu lan toả). Cách này dễ hình dung hơn: đứng ở hàng $i$, ô nào true thì "lan" sang hàng $i + 1$:
- Nếu $F[i][j]$ = true thì $F[i + 1][j]$ = true: với $i$ phần tử đầu đã chọn ra được tập con dư $j$, thì với $i + 1$ phần tử đầu ta vẫn chọn đúng tập con đó được mà.
- Nếu $F[i][j]$ = true thì $F[i + 1][(j + a[i + 1]) \bmod m]$ = true: lấy tập con dư $j$ đó thêm $a[i + 1]$ vào là được tập con mới dư $(j + a[i + 1]) \bmod m$, và nó nằm trong $i + 1$ phần tử đầu.
- Và như trường hợp cơ sở: $F[i + 1][a[i + 1] \bmod m]$ = true.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll a[(int)1e6 + 5];
int main() {
// freopen("dprcdiv.inp", "r", stdin);
// freopen("dprcdiv.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
vector<vector<bool>> f(n + 1, vector<bool>(m, false));
f[1][a[1] % m] = true;
for(int i = 1; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(f[i][j]) {
f[i + 1][j] = true;
f[i + 1][(j + a[i + 1]) % m] = true;
}
}
f[i + 1][a[i + 1] % m] = true;
}
if(f[n][0]) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
f = [[False] * m for _ in range(n + 1)]
f[1][a[1] % m] = True
for i in range(1, n):
for j in range(m):
if f[i][j]:
f[i + 1][j] = True
f[i + 1][(j + a[i + 1]) % m] = True
f[i + 1][a[i + 1] % m] = True
if f[n][0]:
print("YES")
else:
print("NO")Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n \cdot m)$ cho bảng $F$ (dùng
vector<bool>nên mỗi ô chỉ tốn 1 bit). - Thời gian: $O(n \cdot m)$ vì tối đa ta chỉ lấp đầy bảng đó. So với $O(2^n)$ là đã nhanh hơn rất nhiều rồi.
Cách 3Quy hoạch động với công thức truy hồi "kéo về" – O(n·m)
Cách này mình tạo ra công thức quy hoạch động đẹp hơn. Thật ra nếu đi thi mà bạn nghĩ ra cách 2 và thấy dễ làm hơn thì cứ làm nha, cách này tham khảo hen.
- Không chọn phần tử $i$: mặc định $F[i][j] = F[i-1][j]$, vì với $i - 1$ phần tử đầu tạo được tập con dư $j$ thì với $i$ phần tử đầu cũng tạo được (chỉ đơn giản là không chọn phần tử $i$).
- Chọn phần tử $i$: tập con có chứa $a[i]$ và dư $j$. Ta phải kiểm tra $i - 1$ phần tử đầu có tập con nào dư $x$ sao cho $(x + a[i] \bmod m) \bmod m = j$ không.
Đến đây nếu bạn nào theo linh cảm "chuyển vế đổi dấu" thành $x = (j - a[i] \bmod m) \bmod m$ thì đúng nhưng chưa đủ, dẫn đến sai nha 😅. Vì $j - (a[i] \bmod m)$ có thể là số âm, và trong C++ phép % với số âm cho ra số âm (ví dụ -3 % 5 = -3), dùng làm chỉ số mảng là toang. Để tránh điều đó, khi làm phép trừ trong các phép toán modulo ta phải cộng thêm $m$ rồi chia dư lần nữa: $(a - b) \bmod m = \big((a - b) \bmod m + m\big) \bmod m$.
$F[i][j] = F[i-1][j] \;\;||\;\; F[i-1][x]$
Tính xong cả hàng $i$ rồi mới gán $F[i][a[i] \bmod m] = $ true.
f[i][j] chưa true mới áp công thức, hoặc như code dưới đây: chạy công thức cho cả hàng xong rồi mới gán $F[i][a[i] \bmod m] = $ true.Minh hoạ: lấp đầy bảng F
Các bạn nhập $m$ và dãy $a$ rồi bấm Tiếp. Ô vàng là ô đang tính, 2 ô tím ở hàng trên là $F[i-1][j]$ và $F[i-1][x]$ mà nó "kéo về". Bước cuối mình lần ngược để chỉ ra một tập con có tổng chia hết cho $m$ (nếu có):
Sau đây là source code cho ý tưởng trên cho anh em tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll a[(int)1e6 + 5];
int main() {
// freopen("dprcdiv.inp", "r", stdin);
// freopen("dprcdiv.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
vector<vector<bool>> f(n + 1, vector<bool>(m, false));
f[1][a[1] % m] = true;
for(int i = 2; i <= n; ++i) {
for(int j = 0; j < m; ++j) {
f[i][j] = f[i - 1][j] || f[i - 1][((j - (a[i] % m)) % m + m) % m];
}
f[i][a[i] % m] = true;
}
if(f[n][0]) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
f = [[False] * m for _ in range(n + 1)]
f[1][a[1] % m] = True
for i in range(2, n + 1):
for j in range(m):
f[i][j] = f[i - 1][j] or f[i - 1][((j - (a[i] % m)) % m + m) % m]
f[i][a[i] % m] = True
if f[n][0]:
print("YES")
else:
print("NO")Đánh giá độ phức tạp của cả 2 cách quy hoạch động (cách 2 và cách 3) là như nhau, vì tối đa ta chỉ cần lấp đầy bảng đó:
Cách 4Nguyên lý Dirichlet + quy hoạch động – O(m²)
Để làm được bài này ta cần biết tới nguyên lý chuồng bồ câu – chính là nguyên lý Dirichlet. Ví dụ: nếu có 20 con chim bồ câu và 19 cái tổ, khi tất cả về tổ thì sẽ có ít nhất 1 tổ có từ 2 con trở lên. Hoặc một năm có 365 ngày thì trong 366 người chắc chắn có ít nhất 2 người trùng ngày sinh nhật (liên quan còn có "nghịch lý ngày sinh nhật" rất hay, các bạn tìm hiểu thêm trên Google nha).
Nghe thì hiển nhiên nhưng nó giúp ta rất nhiều đó. Đặt $P(i) = (a[1] + a[2] + \ldots + a[i]) \bmod m$:
- $P(1) = a[1] \bmod m$
- $P(2) = (a[1] + a[2]) \bmod m$
- …
- $P(n) = (a[1] + a[2] + \ldots + a[n]) \bmod m$
Vì chia dư cho $m$ nên $0 \le P(i) \le m - 1$: có $m$ giá trị tương ứng với $m$ cái chuồng, và $P(1)$ đến $P(n)$ là $n$ vật. Theo nguyên lý Dirichlet, khi $n \gt m$ chắc chắn có ít nhất một cặp $P(i) = P(j)$ với $i \lt j$.
Vậy $P(i) = P(j)$ thì có gì đặc biệt? Bạn nào đã từng làm bài Subarray Sums Divisible by K sẽ biết luôn. Trong đồng dư thức, nếu 2 số có cùng số dư khi chia cho $m$ thì hiệu của chúng chia hết cho $m$. Ví dụ $12 \bmod 5 = 2$, $27 \bmod 5 = 2$ thì $(27 - 12) \bmod 5 = 15 \bmod 5 = 0$. Áp dụng vào đây:
$P(i) = P(j)$ ⇒ $(a[i+1] + a[i+2] + \ldots + a[j]) \bmod m = 0$.
Vậy có hẳn một mảng con liên tiếp từ $i + 1$ tới $j$ có tổng chia hết cho $m$, và nó cũng là một tập con khác rỗng! Mà khi $n \gt m$ thì luôn có cặp như vậy. Kết luận: nếu $n \gt m$ thì chắc chắn đáp án là YES. Còn nếu $n \le m$ thì dùng quy hoạch động như trên, lúc này $n \le m \le 10^3$ nên độ phức tạp chỉ còn $O(m^2) = 10^6$ – chắc chắn AC.
Minh hoạ: thả các P(i) vào chuồng
Các bạn nhập $m$ và dãy $a$ rồi bấm Tiếp: mỗi bước mình tính $P(i)$ và thả chỉ số $i$ vào chuồng số $P(i)$. Ngay khi một chuồng có 2 vật (hoặc có $P(i) = 0$) là tìm được mảng con chia hết cho $m$:
Sau đây là source code của mình về ý tưởng trên cho anh em nào cần tham khảo nha:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll a[(int)1e6 + 5];
int main() {
// freopen("dprcdiv.inp", "r", stdin);
// freopen("dprcdiv.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
if(n > m) {
cout << "YES";
return 0;
}
vector<vector<bool>> f(n + 1, vector<bool>(m, false));
f[1][a[1] % m] = true;
for(int i = 2; i <= n; ++i) {
for(int j = 0; j < m; ++j) {
f[i][j] = f[i - 1][j] || f[i - 1][((j - (a[i] % m)) % m + m) % m];
}
f[i][a[i] % m] = true;
}
if(f[n][0]) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
if n > m:
print("YES")
sys.exit(0)
a = [0] + [int(x) for x in data[2:2 + n]]
f = [[False] * m for _ in range(n + 1)]
f[1][a[1] % m] = True
for i in range(2, n + 1):
for j in range(m):
f[i][j] = f[i - 1][j] or f[i - 1][((j - (a[i] % m)) % m + m) % m]
f[i][a[i] % m] = True
if f[n][0]:
print("YES")
else:
print("NO")Vô cùng đơn giản phải không, ta chỉ thêm vào if(n > m) thì in YES rồi thoát chương trình luôn. Thậm chí anh em kiểm tra ngay lúc đọc $n, m$, không cần đọc mảng $a$ nữa cũng được, càng nhanh (bản Python ở trên mình làm vậy). Anh em cũng hoàn toàn có thể thêm câu if này vào code "lan toả" của cách 2, độ phức tạp cũng về $O(m^2)$ và AC được.
if(n >= m) là đã in YES được rồi. Vì nếu $n = m$ thì có 2 trường hợp: một là có một cặp trùng $P(i) = P(j)$ như đã lý giải; hai là các $P(i)$ đôi một khác nhau, chiếm đủ cả $m$ chuồng, nên có ít nhất một $P(i) = 0$ – tức là mảng con $a[1..i]$ chia hết cho $m$, thoả mãn đề bài. Bấm nút Test đề 3 ($n = m = 6$) ở khung minh hoạ để thấy nha.Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng $a$ là $O(n)$; bảng $F$ chỉ được tạo khi $n \le m$ nên tối đa $O(m^2)$.
- Thời gian: đọc dữ liệu $O(n)$, quy hoạch động chỉ chạy khi $n \le m$ nên tối đa $O(m^2) = 10^6$ phép tính.
- 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