Editorial for flashmob: Flash Mob

Hiểu bài toán

Bài toán mô phỏng một giải đấu giữa các lớp học. Ban đầu, một lớp cụ thể (C1) giữ cờ vô địch. Trong n tuần, các trận đấu diễn ra, mỗi trận giữa hai lớp ai và bi, trong đó ai thắng bi. Quy tắc cập nhật cờ vô địch là: nếu lớp đang giữ cờ bị đánh bại (xuất hiện ở vị trí thứ hai trong cặp đấu, bi), thì lớp thắng (ai) sẽ trở thành người giữ cờ mới. Yêu cầu xác định lớp đang giữ cờ vô địch sau cùng và số lượng các lớp khác nhau đã từng giữ cờ vô địch trong suốt quá trình.

Các cách tiếp cận

Cách Mô phỏng trực tiếp

#include <stdio.h>
#include <string.h>

int main() {
    int c, n;
    scanf("%d %d", &c, &n);

    // Mảng đánh dấu các lớp đã từng giữ cờ
    int has_been_champion[34] = {0};
    has_been_champion[c] = 1;

    int current_champion = c;

    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);

        // Kiểm tra xem người thách đấu (b) có phải là đương kim vô địch không
        if (b == current_champion) {
            // Nếu thắnm, người thắng (a) trở thành vô địch mới
            current_champion = a;
            // Đánh dấu lớp mới đã giữ cờ
            has_been_champion[a] = 1;
        }
    }

    // Đếm tổng số lớp đã giữ cờ
    int count = 0;
    for (int i = 1; i <= 33; i++) {
        if (has_been_champion[i]) {
            count++;
        }
    }

    printf("%d %d\n", current_champion, count);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận mô phỏng y như mô tả bài toán. Ta sử dụng biến current_champion để lưu lớp đang giữ cờ và một mảng has_been_champion để đánh dấu các lớp nào đã từng giữ cờ. Với mỗi trận đấu, ta chỉ cần so sánh người thua (b) với đương kim vô địch. Nếu khớp, ta cập nhật đương kim vô địch và đánh dấu lớp mới. Cuối cùng, ta đếm số phần tử trong mảng đã được đánh dấu.

Cách Lưu trữ lịch sử

#include <stdio.h>

int main() {
    int t, n;
    scanf("%d %d", &t, &n);

    // Mảng lp để lưu trạng thái: 0 (chưa giữ), 1 (đã giữ), 2 (đã thua)
    int lp[34] = {0};
    lp[t] = 1; // Lớp ban đầu đã giữ cờ

    while (n--) {
        int a, b;
        scanf("%d %d", &a, &b);

        // Nếu người thách thức (b) là đương kim vô địch (t)
        if (b == t) {
            // Đánh dấu lớp mới (a) đã giữ cờ
            lp[a] = 1;
            // Đánh dấu lớp cũ (t) đã thua (hoặc không còn giữ cờ)
            lp[t] = 2;
            // Cập nhật đương kim vô địch mới
            t = a;
        }
    }

    int count = 0;
    for (int i = 1; i < 34; i++) {
        if (lp[i] != 0) count++;
    }

    printf("%d %d ", t, count);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách tiếp cận này cũng mô phỏng trực tiếp nhưng sử dụng một biến duy nhất t để lưu đương kim vô địch thay vì biến flag. Nó cập nhật trạng thái trong mảng lp để ghi nhận sự thay đổi. Tuy nhiên, logic tăng biến đếm dem trực tiếp trong vòng lặp có thể sai nếu một lớp giữ cờ nhiều lần (mặc dù trong bài này không xảy ra), nên cách đếm cuối cùng an toàn hơn.

Cách Quản lý trạng thái bằng mảng 2 chiều

#include <stdio.h>

int main() {
    int c, n;
    scanf("%d %d", &c, &n);

    // Mảng 2 chiều để lưu trữ các trận đấu
    int matches[100][2];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &matches[i][0], &matches[i][1]);
    }

    int current_flag = c;
    int w[34] = {0}; // Mảng đánh dấu lớp đã giữ cờ
    w[c] = 1;

    // Duyệt qua các trận đấu đã lưu
    for (int i = 0; i < n; i++) {
        // Nếu người thua (cột 2) là đương kim vô địch
        if (matches[i][1] == current_flag) {
            // Cập nhật đương kim vô địch mới
            current_flag = matches[i][0];
            // Đánh dấu lớp mới
            if (w[current_flag] == 0) w[current_flag] = 1;
        }
    }

    int count = 0;
    for (int i = 0; i < 34; i++) {
        if (w[i] == 1) count++;
    }

    printf("%d %d", current_flag, count);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Phương pháp này khác biệt ở chỗ nó đọc và lưu trữ toàn bộ dữ liệu đầu vào vào mảng 2 chiều matches trước, sau đó mới xử lý. Nó sử dụng biến flag để theo dõi đương kim vô địch và mảng w để đánh dấu. Tuy nhiên, việc lưu trữ mảng 2 chiều là không cần thiết vì ta chỉ cần xử lý tuần tự các trận đấu ngay khi đọc input. Nó gây tốn bộ nhớ O(n) không cần thiết, nhưng logic xử lý vẫn đúng và hiệu quả về mặt thời gian.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là một dạng mô phỏng trạng thái (state simulation). Trạng thái duy nhất cần theo dõi là người đang giữ cờ.
• Một lớp chỉ được coi là 'đã từng giữ cờ' khi nó chính thức trở thành đương kim vô địch (người thắng trong một trận đấu mà người thua đang giữ cờ).
• Mảng đánh dấu (boolean array) là cấu trúc dữ liệu tối ưu để đếm số lượng phần tử duy nhất (vì giới hạn lớp học chỉ là 33).

Lỗi thường gặp

• Nhầm lẫn giữa người thắng (a) và người thua (b). Người thua (b) phải trùng với đương kim vô địch thì mới có sự thay đổi.
• Quên đánh dấu lớp ban đầu (C1) vào danh sách những người đã giữ cờ.
• Đánh dấu sai trạng thái: Chỉ đánh dấu lớp mới khi nó thực sự trở thành vô địch, không đánh dấu lung tung.