Biểu đồ tiến bộ (Đề tự luyện HSG Tin 9 – Bài 4)

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 4 (đề tự soạn)Độ khó: KhóQuy hoạch độngDãy con tăng dài nhấtTìm nhị phân

Đề bài

Biểu đồ tiến bộ. Có $N$ buổi học theo thứ tự thời gian, buổi $i$ có hai điểm $a_i$ và $b_i$. Chọn một số buổi $i_1 < i_2 < \dots < i_k$, mỗi buổi được chọn lấy đúng một trong hai điểm của nó, sao cho các điểm được lấy tăng ngặt. Tìm $k$ lớn nhất.

Dữ liệu vào: dòng 1 là $N$ $(1 \le N \le 2\cdot 10^5)$; $N$ dòng sau, mỗi dòng $a_i, b_i$ $(1 \le a_i, b_i \le 10^9)$.

Kết quả: giá trị $k$ lớn nhất.

• Subtask 1 (15%): $N \le 12$.
• Subtask 2 (25%): $N \le 3000$.
• Subtask 3 (20%): $a_i = b_i$ với mọi $i$.
• Subtask 4 (40%): không ràng buộc thêm.

Input

8
1 6
5 9
9 6
9 8
4 2
9 9
2 8
7 6

Output

5

Giải thích

Chọn buổi $1, 2, 3, 4, 6$ với các điểm $1$ (bài 1), $5$ (bài 1), $6$ (bài 2), $8$ (bài 2), $9$: dãy $1 < 5 < 6 < 8 < 9$. Không chọn được $6$ buổi.

Dành cho học viênNộp bài trên ClueOJ

Bạ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é. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Biểu đồ tiến bộ

Lời mở đầu

Nếu mỗi buổi chỉ có một điểm, đề bài chính là bài toán kinh điển dãy con tăng (ngặt) dài nhất — LIS (Longest Increasing Subsequence). Ở đây mỗi buổi có hai điểm và ta được chọn một. Có hai cái bẫy:

• Không thể tham lam "luôn lấy điểm nhỏ" (để chừa chỗ cho các buổi sau). Với ba buổi $(3, 9), (1, 4), (2, 5)$: lấy toàn điểm nhỏ được $3, 1, 2$, dài nhất chỉ $2$; nhưng lấy $3, 4, 5$ thì được $3$.
• Không được dùng cả hai điểm của cùng một buổi. Nếu "trải" mỗi buổi thành hai phần tử $a_i, b_i$ rồi làm LIS thì với buổi $(1, 2)$ ta có thể lấy cả $1$ lẫn $2$ — sai luật.

Hình 1. Ví dụ của đề: chấm tròn là hai điểm của mỗi buổi (chiều cao = số điểm), đường hồng là một biểu đồ dài nhất $1 < 5 < 6 < 8 < 9$.

Cách 1Thử mọi cách · 15%Cách 2QHĐ O(N²) · 40%Cách 3a = b: LIS O(N log N) · 20%Cách 4Điểm lớn trước · 100%

Cách 1Thử mọi cách chọn – O(3^N) · 15%

Mỗi buổi có ba lựa chọn: bỏ qua, lấy điểm bài thứ nhất, lấy điểm bài thứ hai. Đệ quy qua từng buổi, nhớ điểm cuối cùng đã lấy (last); chỉ được lấy điểm lớn hơn last. Với $N \le 12$ có không quá $3^{12} \approx 5\cdot10^5$ trường hợp.

#include <bits/stdc++.h>
using namespace std;
int n, best = 0;
vector<int> a, b;
// xet buoi i; diem cuoi cung da chon la last (0 neu chua chon buoi nao), da chon len buoi
void thu(int i, int last, int len) {
    if (i == n) { best = max(best, len); return; }
    thu(i + 1, last, len);                          // bo qua buoi i
    if (a[i] > last) thu(i + 1, a[i], len + 1);     // lay diem lan 1
    if (b[i] > last) thu(i + 1, b[i], len + 1);     // lay diem lan 2
}
int main() {
    cin >> n;
    a.resize(n); b.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    thu(0, 0, 0);                                   // moi diem deu >= 1 > 0
    cout << best << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = [int(data[1 + 2 * i]) for i in range(n)]
    b = [int(data[2 + 2 * i]) for i in range(n)]
    best = [0]

    # xet buoi i; diem cuoi cung da chon la last (0 neu chua chon buoi nao), da chon len buoi
    def thu(i, last, ln):
        if i == n:
            if ln > best[0]:
                best[0] = ln
            return
        thu(i + 1, last, ln)                        # bo qua buoi i
        if a[i] > last: thu(i + 1, a[i], ln + 1)    # lay diem lan 1
        if b[i] > last: thu(i + 1, b[i], ln + 1)    # lay diem lan 2

    thu(0, 0, 0)                                    # moi diem deu >= 1 > 0
    print(best[0])

main()

Không gian$O(N)$

Thời gian$O(3^N)$

Cách 2Quy hoạch động f[i][c] – O(N²) · 40%

Mở rộng QHĐ LIS kinh điển: gọi $f[i][c]$ là độ dài biểu đồ dài nhất kết thúc ở buổi $i$ và buổi $i$ lấy điểm thứ $c$ ($c = 0$: $a_i$, $c = 1$: $b_i$; gọi giá trị đó là $v_{i,c}$). Buổi đứng ngay trước trong biểu đồ là một buổi $j < i$ nào đó với một điểm $v_{j,e} < v_{i,c}$:

$$f[i][c] = 1 + \max\{\, f[j][e] \;:\; j < i,\ e \in \{0,1\},\ v_{j,e} < v_{i,c} \,\}\quad(\text{không có } j \text{ thì } f[i][c] = 1).$$

Vì $j < i$ nên không bao giờ dùng hai điểm của cùng một buổi. Đáp án là $\max f[i][c]$. Bảng cho ví dụ:

buổi $i$	1	2	3	4	5	6	7	8
$a_i$ / $f[i][0]$	1 / 1	5 / 2	9 / 3	9 / 4	4 / 2	9 / 5	2 / 2	7 / 4
$b_i$ / $f[i][1]$	6 / 1	9 / 2	6 / 3	8 / 4	2 / 2	9 / 5	8 / 4	6 / 3

Chẳng hạn $f[4][0] = 4$ (điểm $9$ của buổi 4) nối sau $f[3][1] = 3$ (điểm $6$ của buổi 3), và $f[6][\cdot] = 5$ nối sau $f[4][1] = 4$ (điểm $8$). Mô phỏng dưới đây tính bảng này từng ô một.

Điểm bài 1 (a) Điểm bài 2 (b)

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<array<int, 2>> v(n);                     // v[i][0] = a_i, v[i][1] = b_i
    for (auto &p : v) cin >> p[0] >> p[1];
    // f[i][c] = do dai day dai nhat ket thuc o buoi i, buoi i lay diem v[i][c]
    vector<array<int, 2>> f(n);
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int c = 0; c < 2; c++) {
            f[i][c] = 1;                            // chi gom moi buoi i
            for (int j = 0; j < i; j++)
                for (int e = 0; e < 2; e++)
                    if (v[j][e] < v[i][c]) f[i][c] = max(f[i][c], f[j][e] + 1);
            ans = max(ans, f[i][c]);
        }
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(data[1 + 2 * i]) for i in range(n)]
    b = [int(data[2 + 2 * i]) for i in range(n)]
    # fa[i] / fb[i] = do dai day dai nhat ket thuc o buoi i, buoi i lay diem a_i / b_i
    fa = [0] * n; fb = [0] * n
    ans = 0
    for i in range(n):
        x = a[i]; y = b[i]
        bx = by = 1                     # chi gom moi buoi i
        for j in range(i):
            aj = a[j]; bj = b[j]; ga = fa[j] + 1; gb = fb[j] + 1
            if aj < x and ga > bx: bx = ga
            if bj < x and gb > bx: bx = gb
            if aj < y and ga > by: by = ga
            if bj < y and gb > by: by = gb
        fa[i] = bx; fb[i] = by
        if bx > ans: ans = bx
        if by > ans: ans = by
    print(ans)

main()

Không gian$O(N)$

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

Cách 3Trường hợp a = b: LIS kinh điển O(N log N) · 20%

Khi hai điểm mỗi buổi bằng nhau, đây đúng là bài LIS. Thuật toán $O(N \log N)$ quen thuộc: giữ mảng $d$, với $d[k]$ = phần tử cuối nhỏ nhất của một dãy tăng dài $k + 1$ đã tìm được. Mảng $d$ luôn tăng dần. Gặp giá trị $v$ mới:

• tìm vị trí $k$ đầu tiên có $d[k] \ge v$ (lower_bound) — mọi $d[0..k-1] < v$ nên $v$ nối được sau dãy dài $k$, tạo dãy dài $k+1$ kết thúc bằng $v$;
• nếu $k$ bằng độ dài $d$ thì thêm $v$ vào cuối, ngược lại gán $d[k] = v$ (kết thúc nhỏ hơn thì tốt hơn).

Đáp án là độ dài mảng $d$. Lưu ý dùng lower_bound (tìm $\ge v$) vì đề yêu cầu tăng ngặt; dùng upper_bound sẽ thành dãy không giảm.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    // Subtask 3: a_i = b_i -> bai toan day con tang ngat dai nhat kinh dien
    vector<int> d;                       // d[k] = phan tu cuoi nho nhat cua day tang dai k + 1
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        int k = lower_bound(d.begin(), d.end(), a) - d.begin();
        if (k == (int)d.size()) d.push_back(a);
        else d[k] = a;
    }
    cout << d.size() << '\n';
    return 0;
}

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    # Subtask 3: a_i = b_i -> bai toan day con tang ngat dai nhat kinh dien
    d = []                               # d[k] = phan tu cuoi nho nhat cua day tang dai k + 1
    for i in range(n):
        a = int(data[1 + 2 * i])
        k = bisect_left(d, a)
        if k == len(d): d.append(a)
        else: d[k] = a
    print(len(d))

main()

Không gian$O(N)$

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

Cách 4Hai điểm mỗi buổi: xử lý điểm LỚN trước – O(N log N) · 100%

Thử dùng lại Cách 3: với mỗi buổi, đưa cả hai điểm vào mảng $d$. Vấn đề là nếu đưa điểm nhỏ trước, điểm lớn có thể "nối sau" chính điểm nhỏ của cùng buổi. Ví dụ một buổi $(1, 2)$: đưa $1$ được $d = [1]$, đưa tiếp $2$ được $d = [1, 2]$ — độ dài $2$ dù chỉ có một buổi!

Mẹo: trong mỗi buổi, đưa điểm lớn $x$ vào trước, rồi mới tới điểm nhỏ $y$ ($y < x$):

• Đưa $x$: ghi vào vị trí $k_x$ (lower_bound của $x$). Chỉ ô $d[k_x]$ thay đổi.
• Đưa $y$: vị trí $k_y$ = lower_bound của $y$. Vì $y < x$ nên $k_y \le k_x$; mọi ô trước $k_y$ đều chưa bị buổi này sửa. Vậy $y$ chỉ nối sau các dãy của những buổi trước, không bao giờ nối sau $x$.

Và $x$ khi được đưa vào cũng chỉ nhìn thấy các buổi trước. Như vậy mỗi buổi đóng góp nhiều nhất một phần tử vào mỗi dãy, đúng luật đề. Nếu $a_i = b_i$ thì chỉ cần đưa một lần.

Kết luận

LIS $O(N \log N)$ với lower_bound; mỗi buổi đưa điểm lớn trước, điểm nhỏ sau.

Điểm bài 1 (a) Điểm bài 2 (b) Thứ tự trong mỗi buổi điểm lớn trước (đúng)điểm nhỏ trước (sai)

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    // d[k] = diem cuoi NHO NHAT cua mot day tang ngat dai k + 1 tim duoc tu cac buoi da xet
    vector<int> d;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (a < b) swap(a, b);           // a >= b: xu ly diem LON truoc, diem NHO sau
        int k = lower_bound(d.begin(), d.end(), a) - d.begin();   // vi tri dau tien >= a
        if (k == (int)d.size()) d.push_back(a);
        else d[k] = a;
        if (b != a) {                    // hai diem bang nhau: chi can xet mot lan
            k = lower_bound(d.begin(), d.end(), b) - d.begin();
            if (k == (int)d.size()) d.push_back(b);
            else d[k] = b;
        }
    }
    cout << d.size() << '\n';
    return 0;
}

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    # d[k] = diem cuoi NHO NHAT cua mot day tang ngat dai k + 1 tim duoc tu cac buoi da xet
    d = []
    for i in range(n):
        a = int(data[1 + 2 * i]); b = int(data[2 + 2 * i])
        if a < b:                        # a >= b: xu ly diem LON truoc, diem NHO sau
            a, b = b, a
        k = bisect_left(d, a)            # vi tri dau tien >= a
        if k == len(d): d.append(a)
        else: d[k] = a
        if b != a:                       # hai diem bang nhau: chi can xet mot lan
            k = bisect_left(d, b)
            if k == len(d): d.append(b)
            else: d[k] = b
    print(len(d))

main()

Không gian$O(N)$

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

C++▶ Chạy tay từng dòng codeMỗi buổi: đổi chỗ để a ≥ b, đưa a vào mảng d bằng lower_bound, rồi tới b.

Dữ liệu vào (stdin) – sửa thoải mái8 1 6 5 9 9 6 9 8 4 2 9 9 2 8 7 6

Dữ liệu mẫu:

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

2using namespace std;

3int main() {

4 ios::sync_with_stdio(false);

5 cin.tie(nullptr);

6 int n;

7 cin >> n;

8 // d[k] = diem cuoi NHO NHAT cua mot day tang ngat dai k + 1 tim duoc tu cac buoi da xet

9 vector<int> d;

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

11 int a, b;

12 cin >> a >> b;

13 if (a < b) swap(a, b); // a >= b: xu ly diem LON truoc, diem NHO sau

14 int k = lower_bound(d.begin(), d.end(), a) - d.begin(); // vi tri dau tien >= a

15 if (k == (int)d.size()) d.push_back(a);

16 else d[k] = a;

17 if (b != a) { // hai diem bang nhau: chi can xet mot lan

18 k = lower_bound(d.begin(), d.end(), b) - d.begin();

19 if (k == (int)d.size()) d.push_back(b);

20 else d[k] = b;

21 }

22 }

23 cout << d.size() << '\n';

24 return 0;

25}

ChậmVừaNhanhRất nhanh

Ba lỗi hay gặp

(1) Đưa điểm nhỏ trước: có thể dùng cả hai điểm một buổi (chỉ được 36,1%). (2) Dùng upper_bound: tính dãy không giảm thay vì tăng ngặt (39,1%). (3) Tham lam luôn lấy điểm nhỏ hơn của mỗi buổi (27,5%).

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 38 test: Subtask 1 có 10 test ($N \le 12$), Subtask 2 có 9 test ($N \approx 3000$), Subtask 3 có 8 test ($a_i = b_i$, $N \approx 2\cdot10^5$; gồm dãy giảm, toàn bằng nhau, tăng không ngặt), Subtask 4 có 11 test ($N \approx 2\cdot10^5$). Các kiểu: ngẫu nhiên, miền điểm nhỏ (nhiều điểm bằng nhau), hai điểm một buổi sát nhau trên xu hướng tăng, một điểm theo xu hướng còn điểm kia ngẫu nhiên, một cột tăng một cột giảm, nửa số buổi hai điểm bằng nhau. Ngoài Subtask 3, mọi test đều có đáp án khác LIS của riêng cột $a$. Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (10)	Sub 2 (9)	Sub 3 (8)	Sub 4 (11)	Điểm
Cách 1 – Thử mọi cách $O(3^N)$	Đúng 10/10	TLE 0/9	RE 0/8	RE 0/11	15
Cách 2 – QHĐ $O(N^2)$	Đúng 10/10	Đúng 9/9	TLE 0/8	TLE 0/11	40
Cách 3 – LIS kinh điển trên cột $a$	WA 0/10	WA 0/9	Đúng 8/8	WA 0/11	20
Cách 4 – Điểm lớn trước (chuẩn)	Đúng 10/10	Đúng 9/9	Đúng 8/8	Đúng 11/11	100
Sai: dùng upper_bound	WA 9/10	WA 3/9	WA 4/8	WA 2/11	39,1
Sai: đưa điểm nhỏ trước	WA 4/10	WA 1/9	Đúng 8/8	WA 2/11	36,1
Sai: luôn lấy điểm nhỏ hơn	WA 5/10	WA 0/9	Đúng 8/8	WA 0/11	27,5
Sai: tham lam từ trái sang	WA 4/10	WA 0/9	WA 3/8	WA 0/11	13,5

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test Subtask 1, quá thời gian ở Subtask 2 và tràn ngăn xếp đệ quy ở hai subtask cuối; Cách 2 đúng 19/19 test của hai subtask đầu và quá thời gian (hơn 3 giây) ở cả 19 test còn lại; Cách 3 chỉ đúng 8/8 test Subtask 3; Cách 4 đúng 38/38 test, test lâu nhất chạy khoảng 0,05 giây. Lời giải Python của Cách 4 cũng đúng 38/38 test, chạy tối đa khoảng 0,2 giây với CPython. Ghép Cách 2 với Cách 3 (chọn theo $N$ và theo việc $a_i = b_i$) sẽ được 60%. Ví dụ của đề cố tình "hiền": cả bốn lời giải sai trong bảng đều vẫn ra đúng $5$ — nhớ tự thử những buổi kiểu $(1, 2), (3, 4)$ nha!

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 😇