Thêm Dãy Con
Đề bài
Ban đầu, mảng $a$ chỉ chứa duy nhất số 1. Bạn có thể thực hiện một số thao tác để thay đổi mảng. Trong mỗi thao tác, bạn có thể chọn một dãy con của $a$ và thêm vào $a$ một phần tử mới có giá trị bằng tổng tất cả các phần tử của dãy con đó.
Cho một mảng $c$ là mảng kết quả cuối cùng. Hãy kiểm tra xem liệu có thể thu được mảng $c$ từ mảng ban đầu $a$ bằng cách thực hiện một số (có thể là 0) thao tác như trên hay không.
Một dãy $b$ được gọi là dãy con của dãy $a$ nếu $b$ có thể nhận được từ $a$ bằng cách xóa đi một số (có thể là 0, nhưng không phải tất cả) phần tử. Nói cách khác, bạn chọn $k$ ($1 \le k \le |a|$) chỉ số phân biệt $i_1, i_2, \ldots, i_k$ và chèn vào bất kỳ vị trí nào trong $a$ một phần tử mới có giá trị bằng $a[i_1] + a[i_2] + \ldots + a[i_k]$.
Input
- Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 1000$) — số lượng bộ test.
- Mỗi bộ test: dòng thứ nhất chứa một số nguyên $n$ ($1 \le n \le 2 \cdot 10^5$) — số lượng phần tử của mảng kết quả $c$; dòng thứ hai chứa $n$ số nguyên $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 2 \cdot 10^5$) — các phần tử của mảng $c$.
Lưu ý quan trọng: tổng giá trị $n$ trên tất cả các bộ test không vượt quá $2 \cdot 10^5$.
Output: với mỗi bộ test, in ra "YES" (không có dấu ngoặc kép) nếu tồn tại một dãy thao tác như vậy, ngược lại in ra "NO".
6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1YES
NO
YES
NO
YES
YESGiải thích ví dụ:
- Test 1: mảng $a$ ban đầu đã là [1], nên đáp án là "YES".
- Test 2: thực hiện bất kỳ thao tác nào cũng sẽ làm mảng $a$ có ít nhất 2 phần tử, không thể chỉ có mỗi phần tử 2. Đáp án là "NO".
- Test 3: các thao tác có thể thực hiện để thu được [5, 1, 3, 2, 1]: ban đầu $a$ = [1]; chọn dãy con [1], thêm 1 vào → $a$ = [1, 1]; chọn dãy con [1, 1], thêm 1 + 1 = 2 vào giữa → $a$ = [1, 2, 1]; chọn dãy con [1, 2], thêm 1 + 2 = 3 vào sau số 1 đầu tiên → $a$ = [1, 3, 2, 1]; chọn dãy con [1, 3, 1], thêm 1 + 3 + 1 = 5 vào đầu → $a$ = [5, 1, 3, 2, 1] (đúng mảng cần có).
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm lời giải để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên Codeforces100%Ý tưởng: thêm các số từ nhỏ đến lớn
Bởi vì có thể thêm số mới vào bất kỳ vị trí nào, nên thứ tự các số trong mảng không quan trọng, và ta có thể thêm các số theo giá trị từ nhỏ đến lớn. Sắp xếp dãy tăng dần theo giá trị, thì thực tế một số a[i] có thể thêm vào được nếu như tổng các số đằng trước nó $\ge$ a[i]. Ngoài ra số nhỏ nhất bắt buộc phải là 1 (chính là số 1 ban đầu, vì mọi số thêm vào đều là tổng của các số đã có nên không thể nhỏ hơn số nhỏ nhất đang có).
Ví dụ dãy [5, 1, 3, 2, 1], sau khi sắp xếp được [1, 1, 2, 3, 5]: số đầu tiên là 1; số tiếp theo là 1 $\le$ tổng các số trước đó (1); số tiếp theo là 2 $\le$ 1 + 1; số tiếp theo là 3 $\le$ 1 + 1 + 2; số tiếp theo là 5 $\le$ 1 + 1 + 2 + 3. Vậy đáp án là YES. Còn với test 4 (đáp án NO) và test 6 (đáp án YES) thì:
c = [7, 1, 5, 2, 1], sắp xếp được [1, 1, 2, 5, 7]:
| Số đang xét | Tổng các số trước đó | Kiểm tra |
|---|---|---|
| 1 | — | phải là 1 ✔ |
| 1 | 1 = 1 | 1 ≤ 1 ✔ |
| 2 | 1 + 1 = 2 | 2 ≤ 2 ✔ |
| 5 | 1 + 1 + 2 = 4 | 5 > 4 ✘ ⇒ NO |
c = [1, 1, 4, 2, 1], sắp xếp được [1, 1, 1, 2, 4]:
| Số đang xét | Tổng các số trước đó | Kiểm tra |
|---|---|---|
| 1 | — | phải là 1 ✔ |
| 1 | 1 = 1 | 1 ≤ 1 ✔ |
| 1 | 1 + 1 = 2 | 1 ≤ 2 ✔ |
| 2 | 1 + 1 + 1 = 3 | 2 ≤ 3 ✔ |
| 4 | 1 + 1 + 1 + 2 = 5 | 4 ≤ 5 ✔ |
Thuật toán nghe có vẻ vô lý, nhưng thực tế đây là thuật toán luôn đúng, bởi ta có nhận xét sau:
Chứng minh bằng quy nạp. Khẳng định: khi $sum = a[1] + \ldots + a[i]$, tất cả các số từ 1 đến $sum$ đều biểu diễn được bằng tổng một vài số trong $\{a[1], \ldots, a[i]\}$.
- Với $i = 1$: chắc chắn đúng, vì 1 biểu diễn bởi $a[1] = 1$.
- Giả sử khẳng định đúng với $i$, tức mọi số từ 1 đến $S = a[1] + \ldots + a[i]$ đều biểu diễn được. Xét thêm $a[i + 1] \le S$, đặt $S' = S + a[i + 1]$.
- Các số từ 1 đến $S$: đã biểu diễn được (không dùng $a[i + 1]$).
- Các số $t$ từ $S + 1$ đến $S'$: viết $t = a[i + 1] + (t - a[i + 1])$. Vì $a[i + 1] \le S$ nên $t - a[i + 1] \ge S + 1 - S = 1$, và $t - a[i + 1] \le S' - a[i + 1] = S$, nên phần $t - a[i + 1]$ biểu diễn được bằng các số trong $\{a[1], \ldots, a[i]\}$; thêm $a[i + 1]$ vào là được $t$.
- Do đó khẳng định đúng với $i + 1$.
Ngược lại, nếu có $a[i + 1] \gt sum$ thì chắc chắn không làm được. Xét nhóm các số $\ge a[i + 1]$ (gồm $a[i + 1]$ và các số sau nó trong mảng đã sắp xếp), và lấy số được thêm vào sớm nhất trong nhóm này: lúc thêm nó, mảng chỉ chứa các số thuộc $\{a[1], \ldots, a[i]\}$, nên tổng của bất kỳ dãy con nào cũng không vượt quá $sum \lt a[i + 1] \le$ số đó – mâu thuẫn. Vậy đáp án là NO.
Mô phỏng: em nhập mảng $c$ rồi bấm Tiếp để xem từng bước: vùng xanh trên trục số là mọi tổng tạo được từ các số đã có; số tiếp theo rơi vào vùng xanh thì thêm được và vùng xanh dài ra, rơi ra ngoài là NO:
Đánh giá độ phức tạp: $O(N \log N)$ cho việc sắp xếp mỗi bộ test.
Source code đã nộp thành công:
#include <iostream>
#include <algorithm>
using namespace std;
int numTest;
int n;
int a[200005];
int main(){
cin >> numTest;
for(int testCase = 1; testCase <= numTest; testCase++){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
if(a[1] != 1){
cout << "NO" << endl;
continue;
}
long long sum = 0LL;
bool found = true;
for(int i = 2; i <= n; i++){
sum += a[i - 1];
if(sum < a[i]){
found = false;
break;
}
}
cout << (found == true ? "YES" : "NO") << endl;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
numTest = int(data[0])
pos = 1
out = []
for _ in range(numTest):
n = int(data[pos]); pos += 1
a = sorted(map(int, data[pos:pos + n])); pos += n
if a[0] != 1:
out.append("NO")
continue
total = 0
found = True
for i in range(1, n):
total += a[i - 1]
if total < a[i]:
found = False
break
out.append("YES" if found else "NO")
print("\n".join(out))
main()sum có thể lên tới $2 \cdot 10^5 \cdot 2 \cdot 10^5 = 4 \cdot 10^{10}$, vượt int, nên code để kiểu long long. Trong bài gốc, phần chứng minh quy nạp được viết hơi tắt nên mình viết lại chi tiết hơn một chút cho dễ theo dõi.Mình đã kiểm tra code với 300 bộ test ngẫu nhiên, so với cách thử trực tiếp mọi chuỗi thao tác (với mảng nhỏ), đều cho cùng kết quả; với $n = 2 \cdot 10^5$ bản C++ chạy khoảng 0.06 giây, bản Python mình viết thêm khoảng 0.1 giây.