Collecting Numbers (CSES 2216)

Nguồn: CSES Problem Set Độ khó: Dễ Sắp xếp Vét cạn Nhận xét

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

Collecting Numbers – Gom các số (CSES 2216)

Giới hạn thời gian: 1.00 giây. Giới hạn bộ nhớ: 512 MB.

Cho một mảng chứa mỗi số trong khoảng $1 \ldots n$ đúng một lần. Nhiệm vụ của bạn là gom các số từ $1$ đến $n$ theo thứ tự tăng dần.

Ở mỗi vòng, bạn đi qua mảng từ trái sang phải và gom được càng nhiều số càng tốt. Hỏi tổng cộng cần bao nhiêu vòng?

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên $n$: kích thước mảng.
• Dòng tiếp theo chứa $n$ số nguyên $x_1, x_2, \ldots, x_n$: các số trong mảng.

Kết quả: In ra một số nguyên: số vòng cần đi.

Ràng buộc: $1 \le n \le 2 \cdot 10^5$.

CSES 2216 – Collecting Numbers

Time limit: 1.00 s. Memory limit: 512 MB.

You are given an array that contains each number between $1 \ldots n$ exactly once. Your task is to collect the numbers from $1$ to $n$ in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible. What will be the total number of rounds?

Input:

The first line has an integer $n$: the array size.

The next line has $n$ integers $x_1,x_2,\ldots,x_n$: the numbers in the array.

Output: Print one integer: the number of rounds.

Constraints: $1 \le n \le 2 \cdot 10^5$

Ví dụ – input

5
4 2 1 5 3

Ví dụ – output

3

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

Trước khi vào bài, các bạn nhớ giúp mình chuyện giới hạn thời gian nhé: với các hệ thống chấm cho 1 giây thì toàn bài chỉ nên lặp cỡ $(3 \text{ đến } 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (hên xui), vượt nữa là khả năng TLE (Time Limit Exceeded – chạy quá thời gian) rất cao. Ngưỡng này là cho C/C++; Python, Java, C#… chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 100 ms thì chia 10, cứ thế thôi.

Bài này $n \le 2 \cdot 10^5$ và giới hạn 1 giây: nếu làm $O(n^2)$ thì $n^2 = 4 \cdot 10^{10}$, quá xa ngưỡng ⇒ chắc chắn TLE. Còn $O(n \log n) \approx 18 \cdot 2 \cdot 10^5 = 3.6 \cdot 10^6$ thì thoải mái. Nên nhìn giới hạn là mình đã biết phải nhắm tới độ phức tạp $O(n \log n)$ trở xuống rồi.

Giải thích lại đề cho bạn nào chưa hiểu: ta có các số từ $1$ đến $n$ nằm lộn xộn, không số nào trùng nhau. Mỗi lần đi từ trái sang phải, ta cố lấy các số theo đúng thứ tự $1, 2, 3, \ldots$: phải lấy được số $1$ rồi mới được lấy số $2$, lấy số $2$ rồi mới được lấy số $3$… Hỏi cần đi bao nhiêu lần để lấy đủ $n$ số.

Với ví dụ $4, 2, 1, 5, 3$: lần đi thứ nhất lấy được số $1$, nhưng sau số $1$ chỉ còn $5, 3$, không có số $2$ ⇒ phải đi lần thứ hai từ đầu, lấy được số $2$ rồi đi tiếp lấy luôn số $3$. Lần thứ ba quay lại đầu lấy số $4$ và cũng trong lần đó lấy luôn số $5$. Vậy đáp án là $3$:

• Lần đi 1: $1$
• Lần đi 2: $2, 3$
• Lần đi 3: $4, 5$

Link nộp bài

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Làm đúng theo đề · O(n²) · TLECách 2Sắp xếp cặp (giá trị, vị trí) · O(n log n)

Cách 1Làm đúng theo đề – O(n²)

Cách đơn giản nhất là làm y như đề nói: bắt đầu tìm số $1$, tìm được số $1$ rồi thì tìm tiếp số $2$, rồi số $3$… cho tới số $n$. Mỗi vòng ta duyệt mảng từ đầu đến cuối, hết mảng mà chưa gom đủ thì quay lại từ đầu, tăng số vòng lên.

• Biến x là số đang cần tìm, ban đầu x = 1. Mỗi khi gặp a[i] == x thì x++ để tìm số tiếp theo.
• Khi tìm được số $n$, x++ làm x thành $n + 1$ ⇒ đã gom xong, in kết quả và return 0 kết thúc luôn.
• res đếm số vòng, ban đầu bằng $0$, mỗi lần bắt đầu duyệt lại từ đầu mảng thì res++. while(1) là vòng lặp vô tận, chỉ dừng khi gặp x == n + 1.

3 dòng tăng tốc nhập xuất

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); giúp cin/cout chạy nhanh hơn hẳn. Bài này cần đọc tới $2 \cdot 10^5$ số nên các bạn code C++ nhớ thêm 3 dòng này vào đầu hàm main nhé.

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;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int res = 0, x = 1;
    while (1) {
        res++;
        for (int i = 0; i < n; ++i) {
            if (a[i] == x) {
                x++;
                if (x == n + 1) {
                    cout << res;
                    return 0;
                }
            }
        }
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:n + 1]))
    res, x = 0, 1
    while True:
        res += 1
        for v in a:
            if v == x:
                x += 1
                if x == n + 1:
                    print(res)
                    return

main()

C++▶ Chạy tay từng dòng codeCách 1: mỗi vòng duyệt cả mảng, gặp đúng số x cần tìm thì gom và tìm x + 1.

Dữ liệu vào (stdin) – sửa thoải mái5 4 2 1 5 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main() {

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 int n;

9 cin >> n;

10 int a[n];

11 for (int i = 0; i < n; ++i) {

12 cin >> a[i];

13 }

14 int res = 0, x = 1;

15 while (1) {

16 res++;

17 for (int i = 0; i < n; ++i) {

18 if (a[i] == x) {

19 x++;

20 if (x == n + 1) {

21 cout << res;

22 return 0;

23 }

24 }

25 }

26 }

27 return 0;

28}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(n)$ do cần mảng a lưu các số.
• Thời gian: đọc dữ liệu $O(n)$. Ở bước chính, mỗi vòng duyệt cả mảng ít nhất gom được $1$ số, nhiều nhất gom được cả $n$ số. Tốt nhất là mảng đã tăng dần $1, 2, \ldots, n$: chỉ cần $1$ vòng ⇒ $O(n)$. Nhưng xấu nhất là mảng giảm dần $n, n - 1, \ldots, 1$: mỗi vòng chỉ gom được đúng $1$ số ⇒ while lặp $n$ lần, mỗi lần for lặp $n$ lần ⇒ $O(n^2)$.

Không gian$O(n)$

Thời gian$O(n^2)$

Sẽ bị TLE

Như phân tích đầu bài, $O(n^2)$ với $n = 2 \cdot 10^5$ là khoảng $4 \cdot 10^{10}$ phép lặp, chắc chắn TLE. Mình chạy thử code C++ với mảng giảm dần $n = 2 \cdot 10^5$ thì mất khoảng 16 giây.

Cách 2Sắp xếp cặp (giá trị, vị trí) – O(n log n)

Ta cần một cách làm tốt hơn. Trước tiên, mình đánh số thứ tự vị trí cho từng số từ trái qua phải. Với ví dụ mẫu ta có (số trong ngoặc là vị trí, số bên ngoài là giá trị): $4(1), 2(2), 1(3), 5(4), 3(5)$.

Thứ tự mà ta muốn gom là giá trị tăng dần: $1(3), 2(2), 3(5), 4(1), 5(4)$. Lúc này các vị trí trong ngoặc bị đảo lộn so với ban đầu, chuyện đương nhiên. Các bạn thử nhìn dãy vị trí $3, 2, 5, 1, 4$ này và đối chiếu với đáp án $3$ xem có quy luật gì không? 🤔

Viết dưới dạng mảng cặp a[i] = {first, second} với first là giá trị, second là vị trí (đã sắp tăng dần theo first):

a[0] = {1, 3}
a[1] = {2, 2}
a[2] = {3, 5}
a[3] = {4, 1}
a[4] = {5, 4}

Với a[0] ta không cần xét: chắc chắn phải có ít nhất $1$ vòng để gom được nó, nên khởi tạo res = 1 và bắt đầu xét từ a[1].

Nhận thấy nếu a[i].second < a[i - 1].second thì chắc chắn phải res++. Vì sao? Trong cùng một vòng đi từ trái sang phải, các số gom sau phải nằm bên phải số gom trước, tức là có vị trí lớn hơn. Nếu số $i + 1$ lại nằm bên trái số $i$ (vị trí nhỏ hơn) thì ở vòng hiện tại ta đã đi qua nó mất rồi, chỉ có thể đi hết vòng này rồi quay lại từ đầu mới lấy được ⇒ thêm một vòng. Ngược lại, nếu nó nằm bên phải thì gom luôn trong vòng đang đi.

Ý chính

Sắp xếp các cặp (giá trị, vị trí) tăng dần theo giá trị. Khởi tạo res = 1, duyệt $i$ từ $1$ đến $n - 1$: nếu a[i].second < a[i - 1].second thì res++. Cuối cùng res là đáp án.

Với ví dụ trên, ban đầu res = 1:

• Xét a[1]: vị trí $2 < 3$ ⇒ res = 2.
• Xét a[2]: vị trí $5 > 2$ ⇒ res giữ nguyên $2$.
• Xét a[3]: vị trí $1 < 5$ ⇒ res = 3.
• Xét a[4]: vị trí $4 > 1$ ⇒ res giữ nguyên $3$.

Vậy đáp án là $3$ 🎉.

Minh hoạ: gom số theo vị trí

Em nhập một hoán vị của $1..n$ rồi bấm Tiếp. Mỗi bước ta xét số $x$ tiếp theo, nhìn vị trí của nó: nếu nằm bên trái số $x - 1$ (mũi tên đỏ "quay lại") thì phải mở vòng mới. Mỗi vòng được tô một màu.

Dãy số

Ví dụ nhanh:

Lỗi hay gặp

Một số bạn làm đúng hướng này nhưng khởi tạo res = 0 và cho for chạy từ i = 0. Khi đó so sánh a[i] với a[i - 1] ở i = 0 sẽ đụng a[-1] – truy cập ngoài mảng, sai nha các bạn. Vì vậy code của mình duyệt từ i = 1 và mặc định res = 1 cho phần tử đầu tiên.

Một vài ghi chú về code:

• pair là cấu trúc có sẵn gồm 2 thành phần first và second, rất tiện thay vì phải tự tạo struct. vector là mảng động có sẵn.
• sort(a.begin(), a.end()) sắp tăng dần từ đầu tới cuối vector. Với phần tử kiểu pair, nó so sánh theo first trước (ở đây các giá trị khác nhau nên chỉ cần first). Hàm sort đảm bảo $O(n \log n)$; nếu tự cài các thuật sắp xếp $O(n^2)$ như Selection Sort, Interchange Sort, Bubble Sort thì lại TLE. sort nằm trong thư viện <algorithm>, mình dùng bits/stdc++.h đã bao gồm hết.
• Bên Python, a.sort() trên list các tuple cũng so sánh theo phần tử đầu trước, y hệt pair.

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;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    int res = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i].second < a[i - 1].second) {
            res++;
        }
    }
    cout << res;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [(int(data[i + 1]), i) for i in range(n)]
    a.sort()
    res = 1
    for i in range(1, n):
        if a[i][1] < a[i - 1][1]:
            res += 1
    print(res)

main()

C++▶ Chạy tay từng dòng codeCách 2: sắp cặp (giá trị, vị trí), đếm số lần vị trí bị giảm.

Dữ liệu vào (stdin) – sửa thoải mái5 4 2 1 5 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main() {

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 int n;

9 cin >> n;

10 vector<pair<int, int>> a(n);

11 for (int i = 0; i < n; ++i) {

12 cin >> a[i].first;

13 a[i].second = i;

14 }

15 sort(a.begin(), a.end());

16 int res = 1;

17 for (int i = 1; i < n; ++i) {

18 if (a[i].second < a[i - 1].second) {

19 res++;

20 }

21 }

22 cout << res;

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(n)$ cho mảng cặp.
• Thời gian: đọc dữ liệu $O(n)$ + sắp xếp $O(n \log n)$ + duyệt tính kết quả $O(n)$. Theo quy tắc cộng Big-O lấy thành phần lớn nhất ⇒ $O(n \log n)$, yên tâm không bị TLE như đã phân tích đầu bài.

Không gian$O(n)$

Thời gian$O(n \log n)$

Nếu không dùng vector và pair

Nếu chỉ dùng mảng thường thì ta phải tự khai báo struct Data có 2 thành phần và viết hàm cmp để chỉ định so sánh 2 Data theo thành phần nào. Code sẽ như sau (cùng ý tưởng với cách 2):

#include <bits/stdc++.h>
using namespace std;

struct Data {
    int first, second;
};

bool cmp(const Data &a, const Data &b) {
    return a.first < b.first;
}

Data a[200000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a, a + n, cmp);
    int res = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i].second < a[i - 1].second) {
            res++;
        }
    }
    cout << res;
    return 0;
}

• return a.first < b.first; là viết gọn của if (a.first < b.first) return true; return false;: nếu first của A nhỏ hơn của B thì A đã đứng đúng chỗ, tức là ta muốn danh sách tăng dần theo first.
• Tham số để const Data &a thay vì Data a: truyền tham trị thì trình biên dịch phải tạo biến tạm và sao chép từng thành phần của cấu trúc sang, tốn thời gian. Truyền tham chiếu (&) thì xử lý trực tiếp trên vùng nhớ, không phải sao chép. Còn const ràng buộc chỉ đọc để so sánh, lỡ tay gán thay đổi giá trị là báo lỗi ngay.
• Mảng Data a[200000] mình khai báo ngoài main (biến toàn cục). Mảng này chứa tới $4 \cdot 10^5$ số nguyên; theo kinh nghiệm của mình mảng tĩnh cỡ trên $3 \cdot 10^5$ phần tử thì không nên khai báo trong hàm vì bộ nhớ stack có thể không chứa nổi. Biến toàn cục nằm ở vùng nhớ khác nên chứa được lớn hơn. Hoặc trong main thì dùng cấp phát động Data *a = new Data[n];, hoặc dùng luôn vector.
• sort(a, a + n, cmp): sắp $n$ phần tử đầu của mảng a theo cách so sánh của hàm cmp.

Mở rộng: chỉ cần 1 vòng O(n)

Vì các giá trị chính là $1..n$, ta không cần sắp xếp: lưu luôn pos[a[i]] = i khi đọc, rồi đếm số $x$ từ $2$ đến $n$ có pos[x] < pos[x - 1], cộng thêm $1$. Đây chính là mảng cặp đã sắp ở trên mà không cần gọi sort, độ phức tạp $O(n)$. Ý tưởng mảng pos này sẽ rất có ích cho bài nâng cấp Collecting Numbers II.

Ghi chú của mình: code C++ và Python của cả 2 cách (và bản dùng struct) đã được kiểm tra với 400 hoán vị ngẫu nhiên ($n \le 9$), so với code vét cạn – khớp hết. Với $n = 2 \cdot 10^5$: cách 2 bản C++ chạy khoảng 0.08 giây, bản Python khoảng 0.4 giây; còn cách 1 bản C++ mất khoảng 9 giây với hoán vị ngẫu nhiên và 16 giây với dãy giảm dần ⇒ TLE đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇