Kinh nghiệm (BROTHERS (Olympic 30/4 2019 Khối 11)

Nguồn: Olympic 30/4 năm 2019 – Tin học khối 11 – Bài 2 Độ khó: Trung bình Quy hoạch động QHĐ trên lưới Nhận xét

Đề bài

Bài 2: Kinh nghiệm (7 điểm) – Kỳ thi Olympic truyền thống 30/4 lần thứ XXV – năm 2019, môn Tin học khối 11 (đề chính thức, trường THPT chuyên Lê Hồng Phong, TP. Hồ Chí Minh).

Hai anh em An và Bình tham gia trò chơi thám hiểm trên bảng số XtremeMaze. Bảng có kích thước $N \times M$ ($N$ dòng và $M$ cột), các ô trong bảng được đánh số từ trái sang phải và từ trên xuống dưới.

Tại mỗi ô của bảng có ghi một số nguyên là số điểm kinh nghiệm mà người chơi sẽ nhận được khi đi vào ô này. Cần lưu ý là số điểm tại một số ô có thể là số âm; khi đó, điểm kinh nghiệm của người chơi sẽ bị giảm nếu đi vào ô này.

An và Bình bắt đầu tại ô trái trên, đánh số là $(1, 1)$. Mỗi lượt, một người chỉ có thể di chuyển tới ô kề cạnh ngay phía dưới hoặc ô kề cạnh ngay bên phải và không được phép đi ra khỏi bảng. Khi đi qua mỗi ô, người chơi nhận được số điểm kinh nghiệm bằng số nguyên ghi ở ô đó. Hành trình kết thúc tại ô $(N, M)$.

Mục tiêu của trò chơi này là hai anh em đạt được tổng số điểm cao nhất có thể. Theo quy định, các ô mà An và Bình đi qua không được phép trùng nhau, ngoại trừ ô bắt đầu tại vị trí $(1, 1)$ và ô kết thúc tại vị trí $(N, M)$. Quy ước: giá trị điểm kinh nghiệm tại ô $(1, 1)$ và ô $(N, M)$ đều bằng 0.

Yêu cầu: Hãy viết chương trình tính tổng số điểm kinh nghiệm lớn nhất mà An cùng với Bình đạt được.

Dữ liệu: Vào từ file văn bản BROTHERS.INP gồm:

• Dòng đầu chứa hai số nguyên $N$ và $M$ $(2 \le N, M \le 200)$, số dòng và số cột của bảng.
• $N$ dòng tiếp theo, mỗi dòng ghi $M$ số nguyên là số điểm kinh nghiệm tại mỗi ô trên bảng. Điểm kinh nghiệm tại mỗi ô có giá trị tuyệt đối không vượt quá 100.

Kết quả: Ghi ra file văn bản BROTHERS.OUT duy nhất một số nguyên là tổng điểm lớn nhất mà An cùng với Bình đạt được.

Ràng buộc:

• 30% số điểm của bài tương ứng với các test có $N \le 3$ và $M \le 200$.
• 40% số điểm khác của bài tương ứng với các test có $N \le 50$ và $M \le 50$.
• 30% số điểm còn lại: $N, M \le 200$ (dòng này bị khuất trong ảnh đề mình có, mình ghi theo giới hạn chung của đề).

Trên hệ thống chấm online LQDOJ (mã bài TWOPATHS) thì đọc dữ liệu từ bàn phím và in ra màn hình.

Ví dụ – input

3 3
0 2 3
4 5 6
7 8 0

Ví dụ – output

32

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

Bài này theo đánh giá của mình cũng không phải bài dễ, nhưng cũng không xem là bài khó, nó ở mức vừa. Nếu như bạn nào không để ý được yếu tố tổng số bước 2 người đi là như nhau thì sẽ làm khó, nhìn ra được thì dễ dàng hơn. Ngoài ra thông thường các bạn sẽ chọn giải pháp quy hoạch động 4 chiều thì sẽ bị TLE và thậm chí MLE luôn. Bản chất bài này chỉ cần quy hoạch động 3 chiều thôi: thực tế chỉ cần biết số bước đã đi và biết vị trí hàng của mỗi người là sẽ suy ra được cột của mỗi người.

Giải thích ví dụ cho bạn nào chưa hiểu đề: bảng $3 \times 3$, cả hai cùng xuất phát ở góc trái trên, cùng về đích ở góc phải dưới, mỗi bước chỉ đi xuống hoặc sang phải, và hai đường đi không được có ô chung (trừ 2 ô đầu, cuối). Cách đi tốt nhất là: An đi phải → xuống → phải → xuống, qua các ô $2, 5, 6$ (được $13$ điểm); Bình đi xuống → xuống → phải → phải, qua các ô $4, 7, 8$ (được $19$ điểm) ⇒ tổng $13 + 19 = 32$, đúng đáp án của đề. Để ý nếu An đi phải → phải → xuống → xuống (qua $2, 3, 6$, được $11$ điểm) thì bỏ phí mất ô số 5 ở giữa, tổng chỉ còn $30$. Các bạn có thể kiểm chứng lại bằng khung minh hoạ phía dưới nhé.

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 để nhảy tới:

Cách 1Quy hoạch động 3 chiều f[số bước][hàng An][hàng Bình] · O(N · M · (N + M))

Cách 1Quy hoạch động 3 chiều theo số bước – O(N · M · (N + M))

Nhận xét: hai người luôn đi cùng số bước

Đây là hình ảnh minh hoạ đường đi của An & Bình theo hướng giải của mình, với An là chữ A và Bình là chữ B:

AAAAAAA B A B A BBBB A B AAAAAAAA B A BBBBB A B A B A BBBBBBB

An và Bình khi đi từ $(1, 1)$ đến $(N, M)$ đều trải qua số lượng bước giống nhau là $N + M - 2$ bước (do chỉ có thể di chuyển xuống dưới và qua phải). Do đó, ta hãy chấp nhận An sẽ đi đường "nằm trên" so với Bình, tức tại mỗi bước đi, hàng của An luôn $\le$ hàng của Bình. Hàng của An chỉ bằng hàng của Bình nếu như 2 người cùng ở ô $(1, 1)$ hoặc cùng đến ô $(N, M)$.

Biết số bước và hàng ⇒ suy ra cột

Giả sử sau khi 2 người di chuyển $i$ bước, An ở hàng $x_1$, Bình ở hàng $x_2$. Mỗi bước tăng hàng hoặc cột thêm 1 nên ta có $x_1 + y_1 - 2 = i$ và $x_2 + y_2 - 2 = i$, suy ra:
$y_1 = i + 2 - x_1, \quad y_2 = i + 2 - x_2$
Vậy trạng thái chỉ cần 3 số $(i, x_1, x_2)$ thay vì 4 số $(x_1, y_1, x_2, y_2)$. Các ô cùng số bước $i$ nằm trên cùng một đường chéo phụ của bảng.

Vì sao QHĐ 4 chiều không ổn?

Nếu lưu $f[x_1][y_1][x_2][y_2]$ thì có $200^4 = 1{,}6 \cdot 10^9$ trạng thái, vừa TLE vừa MLE (mảng int cỡ 6,4 GB). Với 3 chiều thì chỉ còn $(N + M) \cdot N \cdot N \approx 400 \cdot 200 \cdot 200 = 1{,}6 \cdot 10^7$ trạng thái.

Công thức quy hoạch động

Gọi f[i][x1][x2] là tổng điểm lớn nhất khi An và Bình di chuyển được $i$ bước, An đứng ở hàng $x_1$, Bình đứng ở hàng $x_2$.

• Bài toán cơ sở: khi 2 bạn xuất phát tại $(1, 1)$, chưa di chuyển, nên f[0][1][1] = 0. Các f[i][x1][x2] còn lại khởi tạo bằng inf (một số âm rất nhỏ, nghĩa là "chưa tới được").
• Đáp án: f[n + m - 2][n][n], tức cả hai cùng ở ô $(N, M)$.

Gọi hàm value(x1, y1, x2, y2) là giá trị cả 2 người nhận được khi An đứng tại ô $(x_1, y_1)$, Bình đứng tại ô $(x_2, y_2)$ (nếu trùng ô, tức ô $(N, M)$, thì chỉ tính 1 lần). Từ trạng thái f[i][x1][x2], sau 1 bước có 4 tình huống:

1. An đi sang phải, Bình đi sang phải: f[i+1][x1][x2] = max(f[i+1][x1][x2], f[i][x1][x2] + value(x1, y1+1, x2, y2+1)).
2. An đi xuống, Bình đi sang phải (cần kiểm soát hàng của An vẫn $\le$ hàng của Bình: $x_1 + 1 \le x_2$): f[i+1][x1+1][x2] = max(..., f[i][x1][x2] + value(x1+1, y1, x2, y2+1)).
3. An đi sang phải, Bình đi xuống (cần $x_2 + 1 \le N$): f[i+1][x1][x2+1] = max(..., f[i][x1][x2] + value(x1, y1+1, x2+1, y2)).
4. An đi xuống, Bình đi xuống (cần $x_2 + 1 \le N$): f[i+1][x1+1][x2+1] = max(..., f[i][x1][x2] + value(x1+1, y1, x2+1, y2)).

Ngoài ra ở mỗi tình huống, hàm check đảm bảo 2 người không đứng chung một ô, trừ khi đó là ô đích $(N, M)$.

Vì sao giữ An "nằm trên" là đủ?

Hai đường đi không giao nhau (trừ 2 đầu) thì luôn có một đường nằm phía trên – phải, đường còn lại nằm phía dưới – trái. Hai người lại giống hệt nhau nên ta luôn có thể đặt tên người đi đường trên là An. Nhờ vậy chỉ cần xét $x_1 \le x_2$, giảm một nửa số trạng thái, và chỉ cần cấm trùng ô (2 người cùng hàng ở cùng số bước thì chắc chắn cùng ô).

Em nhập bảng (dòng đầu $N$, $M$, sau đó là bảng) rồi bấm Tiếp để xem đường đi tối ưu mà QHĐ tìm ra, từng bước một. Đường chéo tô nhạt là các ô có cùng số bước $i$:

Bảng 3 3 0 2 3 4 5 6 7 8 0

Ví dụ nhanh:

Source code giải quyết theo tư tưởng mình đã trình bày ở trên và cũng đã nộp thành công trên web, các bạn xem để được hiểu rõ hơn:

#include <bits/stdc++.h>

using namespace std;
const int inf = -10000007;
int f[405][205][205];
int a[205][205];
int n, m;

int value(int x1, int y1, int x2, int y2) {
    if (x1 == x2 && y1 == y2) {
        return a[x1][y1];
    }
    return a[x1][y1] + a[x2][y2];
}

bool check(int x1, int y1, int x2, int y2) {
    if (x1 != x2 || y1 != y2) {
        return true;
    }
    if (x1 == x2 && x1 == n && y1 == y2 && y2 == m) {
        return true;
    }
    return false;
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    int steps = n + m - 2;
    for (int i = 0; i <= steps; i++) {
        for (int x1 = 1; x1 <= n; x1++) {
            for (int x2 = 1; x2 <= n; x2++) {
                f[i][x1][x2] = inf;
            }
        }
    }
    f[0][1][1] = 0;
    for (int i = 0; i < steps; i++) {
        for (int x1 = 1; x1 <= n; x1++) {
            for (int x2 = x1; x2 <= n; x2++) {
                int y1 = i + 2 - x1;
                int y2 = i + 2 - x2;
                if (check(x1, y1 + 1, x2, y2 + 1) == true) {
                    f[i + 1][x1][x2] = max(f[i + 1][x1][x2], f[i][x1][x2] + value(x1, y1 + 1, x2, y2 + 1));
                }
                if (x1 + 1 <= x2) {
                    if (check(x1 + 1, y1, x2, y2 + 1) == true) {
                        f[i + 1][x1 + 1][x2] = max(f[i + 1][x1 + 1][x2], f[i][x1][x2] + value(x1 + 1, y1, x2, y2 + 1));
                    }
                }
                if (x2 + 1 <= n) {
                    if (check(x1, y1 + 1, x2 + 1, y2) == true) {
                        f[i + 1][x1][x2 + 1] = max(f[i + 1][x1][x2 + 1], f[i][x1][x2] + value(x1, y1 + 1, x2 + 1, y2));
                    }
                    if (check(x1 + 1, y1, x2 + 1, y2) == true) {
                        f[i + 1][x1 + 1][x2 + 1] = max(f[i + 1][x1 + 1][x2 + 1], f[i][x1][x2] + value(x1 + 1, y1, x2 + 1, y2));
                    }
                }
            }
        }
    }
    cout << f[steps][n][n];
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    a = [[0] * (m + 2) for _ in range(n + 2)]
    k = 2
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            a[i][j] = int(data[k])
            k += 1
    NEG = -10 ** 9
    steps = n + m - 2
    # f[x1][x2]: tổng điểm lớn nhất sau i bước, An ở hàng x1, Bình ở hàng x2 (x1 <= x2)
    f = [[NEG] * (n + 2) for _ in range(n + 2)]
    f[1][1] = 0
    for i in range(steps):
        g = [[NEG] * (n + 2) for _ in range(n + 2)]
        lo = max(1, i + 2 - m)          # chỉ xét các hàng mà cột y = i + 2 - x nằm trong bảng
        hi = min(n, i + 1)
        for x1 in range(lo, hi + 1):
            y1 = i + 2 - x1
            row = f[x1]
            for x2 in range(x1, hi + 1):
                cur = row[x2]
                if cur == NEG:
                    continue
                y2 = i + 2 - x2
                # An sang phải, Bình sang phải
                if y2 + 1 <= m:
                    if x1 != x2:
                        v = cur + a[x1][y1 + 1] + a[x2][y2 + 1]
                    elif x1 == n and y1 + 1 == m:
                        v = cur + a[x1][y1 + 1]
                    else:
                        v = NEG
                    if v > g[x1][x2]:
                        g[x1][x2] = v
                # An xuống, Bình sang phải
                if x1 + 1 <= x2 and y2 + 1 <= m:
                    if x1 + 1 != x2:
                        v = cur + a[x1 + 1][y1] + a[x2][y2 + 1]
                    elif x2 == n and y2 + 1 == m:
                        v = cur + a[x2][y2 + 1]
                    else:
                        v = NEG
                    if v > g[x1 + 1][x2]:
                        g[x1 + 1][x2] = v
                if x2 + 1 <= n:
                    # An sang phải, Bình xuống
                    if y1 + 1 <= m:
                        v = cur + a[x1][y1 + 1] + a[x2 + 1][y2]
                        if v > g[x1][x2 + 1]:
                            g[x1][x2 + 1] = v
                    # An xuống, Bình xuống
                    if x1 != x2:
                        v = cur + a[x1 + 1][y1] + a[x2 + 1][y2]
                    elif x1 + 1 == n and y1 == m:
                        v = cur + a[x1 + 1][y1]
                    else:
                        v = NEG
                    if v > g[x1 + 1][x2 + 1]:
                        g[x1 + 1][x2 + 1] = v
        f = g
    print(f[n][n])

main()

Giải thích một số chỗ trong code:

1. Hằng inf = -10000007 đóng vai trò "âm vô cùng". Code không kiểm tra f[i][x1][x2] != inf trước khi chuyển trạng thái, nhưng vẫn đúng: tổng điểm thật chỉ nằm trong khoảng $\pm 2 \cdot 400 \cdot 100 = \pm 80\,000$, nên một giá trị xuất phát từ inf cộng thêm bao nhiêu cũng vẫn nhỏ hơn mọi giá trị thật rất xa, không bao giờ thắng trong max.
2. Vòng x1, x2 chạy từ 1 đến n nên có những trạng thái mà cột y = i + 2 - x nằm ngoài bảng. Những trạng thái này không bao giờ quay về được ô $(N, M)$ (cột chỉ tăng chứ không giảm) nên không ảnh hưởng đáp án. Bản Python mình giới hạn luôn $x$ trong đoạn $[\max(1, i + 2 - M), \min(N, i + 1)]$ và bỏ qua trạng thái chưa tới được để chạy nhanh hơn.
3. Bộ nhớ: mảng f[405][205][205] kiểu int tốn khoảng 68 MB. Để ý f[i + 1] chỉ phụ thuộc f[i], nên nếu đề giới hạn bộ nhớ chặt hơn, các bạn chỉ cần giữ 2 lớp (lớp hiện tại và lớp kế tiếp) như bản Python là còn chưa tới 1 MB.

C++▶ Chạy tay từng dòng codeQHĐ f[i][x1][x2]: sau i bước, An ở hàng x1, Bình ở hàng x2; cột suy ra y = i + 2 − x.

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

Dữ liệu mẫu:

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

2

3using namespace std;

4const int inf = -10000007;

5int f[405][205][205];

6int a[205][205];

7int n, m;

8

9int value(int x1, int y1, int x2, int y2) {

10 if (x1 == x2 && y1 == y2) {

11 return a[x1][y1];

12 }

13 return a[x1][y1] + a[x2][y2];

14}

15

16bool check(int x1, int y1, int x2, int y2) {

17 if (x1 != x2 || y1 != y2) {

18 return true;

19 }

20 if (x1 == x2 && x1 == n && y1 == y2 && y2 == m) {

21 return true;

22 }

23 return false;

24}

25

26int main () {

27 cin >> n >> m;

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

29 for (int j = 1; j <= m; j++) {

30 cin >> a[i][j];

31 }

32 }

33 int steps = n + m - 2;

34 for (int i = 0; i <= steps; i++) {

35 for (int x1 = 1; x1 <= n; x1++) {

36 for (int x2 = 1; x2 <= n; x2++) {

37 f[i][x1][x2] = inf;

38 }

39 }

40 }

41 f[0][1][1] = 0;

42 for (int i = 0; i < steps; i++) {

43 for (int x1 = 1; x1 <= n; x1++) {

44 for (int x2 = x1; x2 <= n; x2++) {

45 int y1 = i + 2 - x1;

46 int y2 = i + 2 - x2;

47 if (check(x1, y1 + 1, x2, y2 + 1) == true) {

48 f[i + 1][x1][x2] = max(f[i + 1][x1][x2], f[i][x1][x2] + value(x1, y1 + 1, x2, y2 + 1));

49 }

50 if (x1 + 1 <= x2) {

51 if (check(x1 + 1, y1, x2, y2 + 1) == true) {

52 f[i + 1][x1 + 1][x2] = max(f[i + 1][x1 + 1][x2], f[i][x1][x2] + value(x1 + 1, y1, x2, y2 + 1));

53 }

54 }

55 if (x2 + 1 <= n) {

56 if (check(x1, y1 + 1, x2 + 1, y2) == true) {

57 f[i + 1][x1][x2 + 1] = max(f[i + 1][x1][x2 + 1], f[i][x1][x2] + value(x1, y1 + 1, x2 + 1, y2));

58 }

59 if (check(x1 + 1, y1, x2 + 1, y2) == true) {

60 f[i + 1][x1 + 1][x2 + 1] = max(f[i + 1][x1 + 1][x2 + 1], f[i][x1][x2] + value(x1 + 1, y1, x2 + 1, y2));

61 }

62 }

63 }

64 }

65 }

66 cout << f[steps][n][n];

67 return 0;

68}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng f có $(N + M - 1) \cdot N \cdot N$ phần tử ⇒ $O((N + M) \cdot N^2)$, khoảng 68 MB với khai báo của mình; dùng 2 lớp thì chỉ còn $O(N^2)$.
• Thời gian: 3 vòng lặp lồng nhau $i$, $x_1$, $x_2$, mỗi trạng thái 4 chuyển ⇒ $O((N + M) \cdot N^2)$. Mình viết gọn là $O(N \cdot M \cdot (N + M))$ (hai cách viết cùng cỡ $1{,}6 \cdot 10^7$ khi $N = M = 200$).

Không gian$O((N + M) \cdot N^2)$

Thời gian$O(N \cdot M \cdot (N + M))$

Bản Python chạy chậm

Với $N = M = 200$, bản Python của mình (đã tối ưu bằng 2 lớp và bỏ trạng thái ngoài bảng) vẫn mất khoảng 5,5 giây trên máy mình, nên nhiều khả năng chỉ ăn được 2 subtask đầu. Bạn nào muốn đủ điểm thì nên nộp bằng C++ nhé.

Ghi chú của mình: code C++ và Python ở trên đã được kiểm tra với 400 bảng ngẫu nhiên ($N, M \le 7$, giá trị từ $-100$ đến $100$), so với code vét cạn thử mọi cặp đường đi – khớp hết. Với $N = M = 200$: bản C++ chạy khoảng 0.2–0.45 giây, bản Python khoảng 5.5 giây; các bảng dẹt $2 \times 200$, $200 \times 2$ toàn số $-100$ cũng cho kết quả đúng.

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 😇