Software (SOFTWARE) (Olympic 30/4 2023 – Tin học khối 10)

Nguồn: Olympic 30/4 lần XXVII – 2023 (khối 10) Độ khó: Trung bình Cây DFS XOR

Đề bài

Câu 2. (7 điểm) Software

Tâm rất yêu thích lập trình tạo phần mềm. Vào dịp rảnh rỗi Tâm đã thiết kế một phần mềm đơn giản. Màn hình phần mềm gồm $N$ địa điểm (đánh số từ $1$ đến $N$), trong đó mỗi địa điểm có đặt một bóng đèn ở trạng thái sáng hoặc tắt. Có $N - 1$ con đường một chiều nối trực tiếp giữa các cặp địa điểm. Mỗi lần Tâm chạm tay vào một địa điểm $X_i$ bất kì trên màn hình thì sẽ có một robot xuất phát từ địa điểm $X_i$ di chuyển theo các con đường một chiều, cuối cùng kết thúc ở địa điểm $1$. Robot không thay đổi trạng thái đèn ở địa điểm $X_i$ và địa điểm $1$, các địa điểm còn lại robot đã đi qua thì đèn ở địa điểm đó sẽ thay đổi sang trạng thái ngược lại (sáng thành tắt, tắt thành sáng).

Yêu cầu: Hãy cho biết khi Tâm thực hiện $K$ lần chạm tay (mỗi lần chạm tay vào một địa điểm) thì sau đó sẽ có tất cả bao nhiêu địa điểm có đèn sáng. Biết rằng robot xuất phát từ địa điểm bất kì luôn có thể di chuyển theo các con đường một chiều đến địa điểm $1$.

Dữ liệu: Cho trong file SOFTWARE.INP

• Dòng đầu tiên gồm 2 số nguyên dương $N$ và $K$ lần lượt là số địa điểm, số lần chạm tay $(1 \le N, K \le 100000)$.
• Dòng thứ hai gồm $N$ số nguyên cho biết trạng thái đèn ở $N$ địa điểm, lần lượt theo thứ tự từ địa điểm $1$ đến địa điểm $N$. Trạng thái đèn tắt là $0$, sáng là $1$.
• Dòng thứ $i$ trong $N - 1$ dòng tiếp theo gồm hai số nguyên dương $A_i$ và $B_i$ $(1 \le A_i, B_i \le N)$ cho biết có con đường một chiều nối trực tiếp từ địa điểm $A_i$ đến $B_i$.
• Dòng cuối cùng gồm $K$ số nguyên dương, trong đó số nguyên thứ $i$ là $X_i$ $(1 \le X_i \le N)$ cho biết địa điểm thứ $i$ mà Tâm thực hiện chạm tay.

Kết quả: Ghi ra file SOFTWARE.OUT số nguyên duy nhất là kết quả cần tìm.

Ràng buộc: 50% số test ứng với 50% số điểm có $1 \le N, K \le 5000$.

Thời gian làm bài cả đề: 180 phút. Đề gốc đọc/ghi file SOFTWARE.INP / SOFTWARE.OUT; code trong bài này đọc từ bàn phím và in ra màn hình cho dễ chạy thử, đi thi thì các bạn thêm 2 dòng freopen("SOFTWARE.INP", "r", stdin); freopen("SOFTWARE.OUT", "w", stdout); ở đầu hàm main nhé.

Ví dụ 1 – SOFTWARE.INP

5 3
1 0 0 0 0
2 1
4 2
3 2
5 4
4 5 4

Ví dụ 1 – SOFTWARE.OUT

3

Ví dụ 2 – SOFTWARE.INP

4 1
0 0 0 0
3 1
2 3
4 2
4

Ví dụ 2 – SOFTWARE.OUT

2

Giải thích ví dụ 1: Tâm chạm tay 3 lần.

• Lần 1 ở địa điểm 4: robot đi qua các địa điểm 4, 2, 1 và thay đổi trạng thái đèn ở địa điểm 2. Kết quả trạng thái 5 đèn theo thứ tự lần lượt là: 1 1 0 0 0.
• Lần 2 ở địa điểm 5: robot đi qua các địa điểm 5, 4, 2, 1 và thay đổi trạng thái đèn ở địa điểm 4, 2. Kết quả trạng thái 5 đèn lần lượt là: 1 0 0 1 0.
• Lần 3 ở địa điểm 4: robot đi qua các địa điểm 4, 2, 1 và thay đổi trạng thái đèn ở địa điểm 2. Kết quả trạng thái 5 đèn lần lượt là: 1 1 0 1 0.

Sau 3 lần chạm tay, có 3 địa điểm có đèn sáng là địa điểm 1, 2 và 4.

Lời mở đầu

Bài này nằm trong đề thi Olympic truyền thống 30 tháng 4 lần thứ XXVII năm 2023, môn Tin học khối 10. Mình viết hướng dẫn giải theo cách làm của mình để các bạn tham khảo thử. Bài này có thể xem như là bài dễ nhất đề (tất nhiên sẽ có nhiều ý kiến trái chiều, nhưng cá nhân mình đánh giá như vậy, vì ý tưởng không quá khó để nhìn ra). Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây 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

Trước khi vào lời giải, mình "đọc" lại đề một chút cho rõ hình dạng dữ liệu:

• Robot xuất phát ở đâu cũng đi được về địa điểm $1$, mà chỉ có đúng $N - 1$ con đường. Vậy mỗi địa điểm khác $1$ có đúng một con đường đi ra (gọi điểm đến của nó là cha), còn địa điểm $1$ không có đường đi ra. Các địa điểm tạo thành một cây có gốc là $1$, mọi con đường đều hướng về gốc.
• Mỗi lần chạm vào $X$, robot đi đúng một đường duy nhất từ $X$ lên gốc $1$, và đảo đèn của các đỉnh nằm giữa (không tính $X$ và $1$).

Ở ví dụ 1, cây trông như sau (mũi tên là hướng đường đi, đèn vàng là đang sáng): $1 \leftarrow 2$, $2 \leftarrow 4$, $2 \leftarrow 3$, $4 \leftarrow 5$. Các bạn xem hình động ở Cách 2 để thấy rõ hơn nha.

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

Cách 1Mô phỏng từng robot · O(N·K) · 50%Cách 2Đánh level + XOR lan truyền · O(N + K)

Cách 1Mô phỏng từng robot – O(N·K)

Làm đúng như đề nói: lưu nxt[a] = b là điểm đến của con đường đi ra từ $a$. Mỗi lần chạm vào $X$, robot bắt đầu từ u = nxt[X] (bỏ qua chính $X$), cứ chừng nào u chưa phải là $1$ thì đảo đèn ở u rồi đi tiếp u = nxt[u]. Cuối cùng đếm số đèn sáng.

Chạm vào chính địa điểm 1 thì sao?

Địa điểm $1$ không có đường đi ra nên nxt[1] = 0. Vòng lặp dừng khi u == 1 hoặc u == 0, nên chạm vào $1$ thì không có đèn nào bị đổi – đúng với đề.

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 light[100005], nxt[100005];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> light[i];
    }
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        nxt[a] = b;
    }
    for (int i = 1; i <= k; i++) {
        int x;
        cin >> x;
        int u = nxt[x];
        while (u != 1 && u != 0) {
            light[u] ^= 1;
            u = nxt[u];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += light[i];
    }
    cout << ans;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    light = [0] + [int(x) for x in data[2:2 + n]]
    nxt = [0] * (n + 1)
    p = 2 + n
    for _ in range(n - 1):
        a, b = int(data[p]), int(data[p + 1]); p += 2
        nxt[a] = b
    for _ in range(k):
        x = int(data[p]); p += 1
        u = nxt[x]
        while u != 1 and u != 0:
            light[u] ^= 1
            u = nxt[u]
    print(sum(light))

main()

C++▶ Chạy tay từng dòng codeCách 1: mỗi lần chạm, cho robot đi từng bước lên gốc và đảo đèn.

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

Dữ liệu mẫu:

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

2using namespace std;

3int light[100005], nxt[100005];

4int main() {

5 int n, k;

6 cin >> n >> k;

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

8 cin >> light[i];

9 }

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

11 int a, b;

12 cin >> a >> b;

13 nxt[a] = b;

14 }

15 for (int i = 1; i <= k; i++) {

16 int x;

17 cin >> x;

18 int u = nxt[x];

19 while (u != 1 && u != 0) {

20 light[u] ^= 1;

21 u = nxt[u];

22 }

23 }

24 int ans = 0;

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

26 ans += light[i];

27 }

28 cout << ans;

29 return 0;

30}

ChậmVừaNhanhRất nhanh

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

• Không gian: 2 mảng light, nxt ⇒ $O(N)$.
• Thời gian: mỗi robot đi tối đa $N$ bước ⇒ $O(N \cdot K)$. Với $N, K \le 5000$ là khoảng $2.5 \cdot 10^7$ bước, chạy ngon lành.

Không gian$O(N)$

Thời gian$O(N \cdot K)$

Chỉ được 50% điểm

Khi cây là một "đường thẳng" dài $10^5$ đỉnh và Tâm toàn chạm ở cuối đường, mỗi robot đi gần $10^5$ bước, $10^5$ robot là $10^{10}$ bước ⇒ TLE. Mình thử đúng test này thì code C++ chạy hơn 20 giây vẫn chưa xong.

Cách 2Đánh level cho các đỉnh + lan truyền XOR – O(N + K)

Nhận xét: coi đỉnh 1 là đỉnh "tối thượng"

Do tất cả các đỉnh đều hội tụ về $1$, ta có thể coi đỉnh $1$ là đỉnh tối thượng, ta gọi là level 0; sau đó đến những đỉnh nối trực tiếp với $1$ gọi là level 1; những đỉnh nối trực tiếp với các đỉnh level 1 là level 2, và cứ thế…

Ta gọi state[u] là trạng thái "có sự kiện robot đến $u$". Hãy nhớ rằng nếu robot đến đỉnh $u$ với số lần là số chẵn, ta có thể xem như robot không đến đỉnh $u$ (đảo đèn 2 lần thì như không đảo). Vì vậy state[u] chỉ cần lưu $0$ hoặc $1$ – tức là số lần đến $u$ lấy theo chẵn lẻ, và mỗi lần "thêm một lần đến" chỉ là phép ^= 1.

1. Đánh level: lưu thêm đồ thị ngược rev_adj (từ cha xuống con), rồi dùng dfs(1, 0) để đánh level cho các đỉnh. Với mỗi level, ta tạo 1 danh sách các đỉnh tại level đó: listVertex[level].
2. Ghi nhận các lần chạm: chạm vào $X$ thì robot không đổi đèn ở $X$, mà bắt đầu đổi từ đỉnh cha của $X$ (đỉnh adj[X]). Vì vậy ta chỉ đánh dấu state[cha của X] ^= 1: "có một robot đến cha của $X$". Chưa vội đi tiếp lên trên!
3. Lan truyền từ level cao nhất về level thấp nhất: với các đỉnh $u$ tại level $k$, khi xét đỉnh $u'$ (cha của $u$) tại level $k - 1$: robot nào đã đến $u$ thì cũng sẽ đi tiếp lên $u'$. Do đó state[u'] sẽ đổi từ 0 → 1 nếu state[u] = 1, hoặc giữ nguyên nếu state[u] = 0. Hay nói cách khác: state[u'] = state[u'] XOR state[u]. Vì đi từ level cao xuống level thấp, lúc xét tới $u$ thì mọi đỉnh con của $u$ đã đẩy hết "robot" của chúng lên $u$ rồi, nên state[u] lúc đó là chính xác.
4. Đếm đèn sáng: như vậy, 1 đỉnh $u$ sẽ sáng đèn nếu như đèn tại đó đang tắt nhưng state[u] = 1, hoặc đèn tại đó đang bật mà state[u] = 0. Đỉnh $1$ (level 0) thì không bao giờ bị đổi, nên đáp án khởi đầu bằng light[1] và vòng lặp level chỉ chạy tới level 1.

Tóm gọn

Đèn cuối cùng ở đỉnh $u \ne 1$ là light[u] XOR state[u], với state[u] = chẵn lẻ của số robot đi qua $u$ (không tính lúc robot xuất phát tại $u$). Thay vì cho từng robot đi lên (chậm), ta "gom" robot lại và đẩy lên từng tầng một lần duy nhất.

Minh hoạ lan truyền state theo level

Em nhập trạng thái đèn, các con đường và các lần chạm rồi bấm Tiếp. Số nhỏ màu đỏ cạnh mỗi đỉnh là state, đỉnh viền cam là đỉnh đang xét:

Đèn (đỉnh 1..N) Con đường A B, ... Các lần chạm

Ví dụ nhanh:

Source code theo tư tưởng mình đã trình bày ở trên:

#include <bits/stdc++.h>
using namespace std;
int light[100005];
vector <int> adj[100005];
vector <int> rev_adj[100005];
int n, k;
vector <int> listVertex[100005];
int state[100005];

void dfs(int u, int currentLevel) {
    listVertex[currentLevel].push_back(u);
    for (int i = 0; i < (int) rev_adj[u].size(); i++) {
        int v = rev_adj[u][i];
        dfs(v, currentLevel + 1);
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> light[i];
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        rev_adj[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= k; i++) {
        int u;
        cin >> u;
        for (int j = 0; j < (int) adj[u].size(); j++) {
            int v = adj[u][j];
            state[v] ^= 1;
        }
    }
    int ans = light[1];
    for (int level = n; level >= 1; level--) {
        for (int i = 0; i < (int) listVertex[level].size(); i++) {
            int u = listVertex[level][i];
            if (state[u] == 1 && light[u] == 0) ans++;
            if (state[u] == 0 && light[u] == 1) ans++;
            for (int j = 0; j < (int) adj[u].size(); j++) {
                int v = adj[u][j];
                state[v] ^= state[u];
            }
        }
    }
    cout << ans;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    light = [0] + [int(x) for x in data[2:2 + n]]
    adj = [[] for _ in range(n + 1)]
    rev_adj = [[] for _ in range(n + 1)]
    p = 2 + n
    for _ in range(n - 1):
        u, v = int(data[p]), int(data[p + 1]); p += 2
        adj[u].append(v)
        rev_adj[v].append(u)
    # dfs(1, 0) viết bằng stack để tránh giới hạn đệ quy của Python
    listVertex = [[] for _ in range(n + 1)]
    st = [(1, 0)]
    while st:
        u, lv = st.pop()
        listVertex[lv].append(u)
        for v in rev_adj[u]:
            st.append((v, lv + 1))
    state = [0] * (n + 1)
    for _ in range(k):
        u = int(data[p]); p += 1
        for v in adj[u]:
            state[v] ^= 1
    ans = light[1]
    for level in range(n, 0, -1):
        for u in listVertex[level]:
            if state[u] != light[u]:
                ans += 1
            for v in adj[u]:
                state[v] ^= state[u]
    print(ans)

main()

Bản Python mình viết dfs bằng stack tự quản lý thay cho đệ quy, vì cây có thể là một đường thẳng sâu $10^5$ tầng, vượt giới hạn đệ quy mặc định của Python. Thứ tự các đỉnh trong cùng một level có thể khác bản C++ nhưng không ảnh hưởng kết quả (các đỉnh cùng level không phụ thuộc nhau).

C++▶ Chạy tay từng dòng codeCách 2: DFS đánh level, đánh dấu state ở cha của đỉnh chạm, rồi lan truyền XOR từ level sâu nhất lên.

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

Dữ liệu mẫu:

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

2using namespace std;

3int light[100005];

4vector <int> adj[100005];

5vector <int> rev_adj[100005];

6int n, k;

7vector <int> listVertex[100005];

8int state[100005];

9

10void dfs(int u, int currentLevel) {

11 listVertex[currentLevel].push_back(u);

12 for (int i = 0; i < (int) rev_adj[u].size(); i++) {

13 int v = rev_adj[u][i];

14 dfs(v, currentLevel + 1);

15 }

16}

17

18int main() {

19 cin >> n >> k;

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

21 cin >> light[i];

22 }

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

24 int u, v;

25 cin >> u >> v;

26 adj[u].push_back(v);

27 rev_adj[v].push_back(u);

28 }

29 dfs(1, 0);

30 for (int i = 1; i <= k; i++) {

31 int u;

32 cin >> u;

33 for (int j = 0; j < (int) adj[u].size(); j++) {

34 int v = adj[u][j];

35 state[v] ^= 1;

36 }

37 }

38 int ans = light[1];

39 for (int level = n; level >= 1; level--) {

40 for (int i = 0; i < (int) listVertex[level].size(); i++) {

41 int u = listVertex[level][i];

42 if (state[u] == 1 && light[u] == 0) ans++;

43 if (state[u] == 0 && light[u] == 1) ans++;

44 for (int j = 0; j < (int) adj[u].size(); j++) {

45 int v = adj[u][j];

46 state[v] ^= state[u];

47 }

48 }

49 }

50 cout << ans;

51 return 0;

52}

ChậmVừaNhanhRất nhanh

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

• Không gian: các mảng light, state, đồ thị xuôi/ngược và danh sách level đều $O(N)$.
• Thời gian: DFS $O(N)$; mỗi lần chạm $O(1)$ (mỗi đỉnh chỉ có 1 cha) ⇒ $O(K)$; vòng lặp level duyệt mỗi đỉnh 1 lần ⇒ $O(N)$. Tổng cộng $O(N + K)$.

Không gian$O(N)$

Thời gian$O(N + K)$

Về độ sâu đệ quy

Nếu cây là một đường thẳng $10^5$ đỉnh thì dfs đệ quy sâu $10^5$ tầng. Mỗi tầng tốn rất ít bộ nhớ nên với stack mặc định (8 MB trên Linux) code C++ vẫn chạy ổn – mình đã thử đúng test này. Nếu máy chấm để stack nhỏ (ví dụ 1 MB trên Windows) thì các bạn có thể đổi dfs sang dạng dùng stack/queue (BFS theo level) như bản Python cho chắc ăn.

Ghi chú của mình: code của Cách 2 mình dựng lại theo đúng hướng và tên biến trong bài gốc (link code cũ trên paste.org hiện không truy cập được). Code C++ và Python của cả 2 cách đã được kiểm tra với 2 ví dụ của đề, 300 bộ test ngẫu nhiên nhỏ ($N, K \le 12$, có cả cây dạng đường thẳng, cây rậm) so với code vét cạn tự cho robot đi theo đường – khớp hết, và 100 bộ test $N, K \le 400$ so chéo giữa 2 cách – khớp hết. Với $N = K = 10^5$: Cách 2 (C++) chạy khoảng 0.3 giây, bản Python khoảng 0.6–0.9 giây; Cách 1 (C++) với cây dạng đường thẳng chạy quá 20 giây (TLE đúng như phân tích), còn với $N = K = 5000$ chỉ mất khoảng 0.2 giây.

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 😇