Tư liệu cũ

Giới thiệu

Tạp chí VNOI định kỳ sẽ quay trở lại cùng chuyên mục giới thiệu các bài viết, tư liệu học thuật và các contest luyện tập được chuẩn bị bởi các thế hệ Tình nguyện viên VNOI trong suốt 5 năm vừa qua. Với mong muốn góp phần cung cấp nguồn tài liệu và bài tập đáng tin cậy cho cộng đồng học sinh, sinh viên yêu thích lập trình thuật toán, chuyên mục được biên tập nhằm giúp độc giả ôn luyện và nghiên cứu từ những kiến thức cơ bản đến nâng cao để hướng tới các kỳ thi lập trình trong nước và quốc tế.

Các tài liệu và contest về chủ đề Hình học

Hình học tính toán luôn được xem là một trong những chủ đề khó và thử thách nhất trong lập trình thi đấu. Khác với các chủ đề thuần toán rời rạc như Quy hoạch động hay Đồ thị, hình học đòi hỏi khả năng xử lý số thực chính xác cùng tư duy trực quan không gian. Chính vì vậy, các bài toán hình học thường được xếp ở vị trí bài khó nhất trong nhiều kỳ thi APIO, IOI, ICPC hay kỳ thi chọn học sinh giỏi quốc gia.

Các bài toán hình học luôn đòi hỏi người giải phải xét rất nhiều trường hợp xử lý khi tiếp cận bài toán, xử lý các trường hợp biên (edge case) đối với các mô hình phẳng hoặc mô hình không gian cũng như đòi hỏi tính cẩn thận khi xử lý sai số số thực. Các bài toán hình học luôn yêu cầu cách triển khai rất phức tạp, dễ gặp lỗi và buộc người giải phải tốn rất nhiều thời gian giải quyết dưới áp lực của môi trường thi đấu.

Nhằm hỗ trợ cộng đồng người học tiếp cận chủ đề này một cách hệ thống, các Tình nguyện viên Team Wiki đã biên soạn bộ bài viết về Hình học tính toán, tập trung truyền tải những kiến thức cốt lõi và phổ biến nhất về chủ đề này:

• Hình học tính toán phần 1: Những khái niệm cơ bản
• Hình học tính toán phần 2: Sự giao nhau của đường thẳng và các ứng dụng
• Hình học tính toán phần 3: Đa giác

Bên cạnh tư liệu lý thuyết, nền tảng chấm bài VNOJ cũng đã tổ chức các kỳ thi luyện tập theo chủ đề, cung cấp nguồn bài tập tiếng Việt uy tín và chất lượng, phục vụ quá trình rèn luyện kỹ năng giải các bài tập hình học:

• Educational Geometry Contest
• Educational Geometry Contest Part 2

Các tài liệu và contest về chủ đề Quy hoạch động

Quy hoạch động luôn là một trong những chủ đề cốt lõi và có phạm vi ứng dụng rộng nhất trong Lập trình thi đấu. Đây là kỹ thuật tối ưu hóa mạnh mẽ dựa trên việc chia nhỏ bài toán thành các bài toán con, tận dụng kết quả đã tính toán để đạt được hiệu quả thời gian.

Không chỉ yêu cầu tư duy logic và phân tích bài toán thành các bài toán con, chủ đề này còn đòi hỏi người học phải rèn luyện kỹ năng nhận diện mô hình, kỹ thuật tối ưu bộ nhớ, và đôi khi cần kết hợp với các chủ đề nâng cao như Cấu trúc dữ liệu, Toán học rời rạc, Bitmask hay Đồ thị. Với tính vận dụng và phân hóa cao, các bài toán Quy hoạch động luôn xuất hiện trong hầu hết các kỳ thi lập trình từ cấp khu vực cho đến quốc tế.

Trong suốt nhiều năm vừa qua, các Tình nguyện viên Team Wiki VNOI đã biên soạn hệ thống bài viết về Quy hoạch động trên VNOI Wiki, giúp độc giả từng bước xây dựng tư duy và tiếp cận các kỹ thuật từ cơ bản đến nâng cao. Các bài viết học thuật Tiếng Việt về chủ đề Quy hoạch động có thể được tìm thấy tại VNOI Wiki.

Song song với tài liệu lý thuyết, nền tảng chấm bài VNOJ cũng đã tổ chức các kỳ thi luyện tập chủ đề Quy hoạch động, được chọn lọc kỹ lưỡng và bám sát cấu trúc các đề thi lớn, giúp người học phát triển tư duy và rèn luyện kỹ năng giải bài toàn diện:

• Educational Dynamic Programming Advanced Contest Part 1
• Educational Dynamic Programming Advanced Contest Part 2

Các tài liệu và contest về chủ đề Đường đi Euler và HLD

Trong lập trình thi đấu, các bài toán giải quyết theo mô hình cây luôn đòi hỏi những kỹ thuật xử lý dữ liệu khó để đảm bảo hiệu quả thời gian và quản lý không gian dữ liệu một cách tối ưu. Hai trong số những kỹ thuật quan trọng và phổ biến nhất cho nhóm bài toán này là Đường đi Euler (Euler Tour) và Heavy-Light Decomposition (HLD).

Euler Tour là kỹ thuật biến một cây thành một dãy tuyến tính bằng việc “phẳng hóa” cấu trúc cây, cho phép áp dụng thêm các cấu trúc dữ liệu như Segment Tree hay Fenwick Tree để xử lý nhanh các truy vấn trên đoạn, đặc biệt là các truy vấn trên cây con. Đây là nền tảng của rất nhiều bài toán cây từ cơ bản đến nâng cao trong ICPC hay IOI.

Trong khi đó, Heavy-Light Decomposition là kỹ thuật phân chia cây thành các đường đi “nặng” - “nhẹ”, giúp chuyển các truy vấn trên đường đi giữa hai đỉnh bất kỳ về một số lượng nhỏ các truy vấn trên đoạn. HLD là một trong những kỹ thuật khó và quan trọng nhất trong xử lý truy vấn trên cây, thường xuất hiện trong các bài toán mang tính phân loại cao, yêu cầu người giải kết hợp khả năng tư duy với các cấu trúc dữ liệu mạnh mẽ để đạt hiệu năng tối ưu.

Nhằm hệ thống hóa và hỗ trợ người học tiếp cận hai kỹ thuật thiết yếu này, các Tình nguyện viên Team Wiki đã biên soạn các bài viết hướng dẫn chi tiết trên VNOI Wiki:

• Heavy-Light Decomposition (HLD)
• Đường đi Euler trên cây

Bên cạnh nguồn tư liệu lý thuyết, các Tình nguyện viên Team Contest VNOI tổ chức một contest luyện tập theo chủ đề nhằm giúp người học nắm vững kiến thức và sẵn sàng để vận dụng các kỹ thuật này:

• Educational Euler Tour and HLD Contest

Các tài liệu về chủ đề Cây tiền tố (Trie)

Trong lập trình thi đấu, cấu trúc dữ liệu Trie (còn gọi là cây tiền tố) là một trong những công cụ hiệu quả khi làm việc với tập hợp các xâu hoặc các tập hợp số (dưới dạng nhị phân). Khác với các cấu trúc dữ liệu truyền thống như cây tìm kiếm nhị phân hay bảng băm, Trie cho phép quản lý và truy vấn dữ liệu dựa trên từng ký tự/từng bit theo cấu trúc phân tầng, từ đó đạt được hiệu năng truy vấn vượt trội đối với các bài toán liên quan đến tiền tố hoặc các truy vấn nhiều lần trên tập dữ liệu lớn.

Cấu trúc dữ liệu Trie thường được ứng dụng trong các bài toán từ điển, tự động gợi ý trong văn bản, tối ưu truy vấn XOR, cũng như các bài xử lý chuỗi phức tạp trong những kỳ thi lớn. Trên những nền tảng cơ sở về kiến thức và cài đặt của Trie, Team Wiki của VNOI đã biên soạn và cập nhật bài viết hướng dẫn chi tiết về chủ đề này trên VNOI Wiki:

• Cây tiền tố - Trie

Các contest luyện tập thuộc Dự án sinh test các kỳ thi chính thức của VNOI

Dự án sinh test các kỳ thi chính thức của VNOI được triển khai nhằm tổng hợp các đề thi và bài toán lập trình từ những kỳ thi chọn đội tuyển Học sinh giỏi Quốc gia của các địa phương và đơn vị đào tạo, giúp học sinh và sinh viên có một nguồn luyện tập chuẩn mực và bám sát thực tiễn để chuẩn bị cho các kỳ thi học sinh giỏi các cấp. Qua việc số hóa bộ đề và tổ chức trên nền tảng thi trực tuyến VNOJ. Đội ngũ Tình nguyện viên Team Contest thuộc VNOI kỳ vọng dự án sẽ góp phần nâng cao khả năng tự ôn luyện của học sinh với sự mô phỏng sát với kỳ thi cấp tỉnh, cấp quốc gia và quốc tế.

Các kỳ thi đã được số hóa và tổ chức lại trên hệ thống VNOJ trong khuôn khổ dự án:

• Kỳ thi chọn Đội tuyển HSGQG Thừa Thiên Huế 2023–2024
• Kỳ thi chọn Đội tuyển HSGQG Quảng Trị 2024–2025

Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.

Coding Challenge #1

Coding Challenge #1 có tên là Đường đi. Đây là một bài toán về chủ đề đường đi ngắn nhất trên đồ thị, với điểm khác biệt là cách xây dựng tập cạnh thông qua các truy vấn nối và tô màu đỉnh.

Bài toán này chứng kiến 182 độc giả tham gia giải và 30 bài giải đạt điểm tuyệt đối. Đội ngũ Tạp chí VNOI xin phép chọn lọc ra 2 lời giải được các độc giả gửi về cho Tạp chí.

Đề Bài

Đề bài gốc có thể được đọc trên hệ thống VNOJ Coding Challenge #1 - Đường đi

Cho một đồ thị vô hướng gồm ~N~ đỉnh, ban đầu đồ thị này không có cạnh nào. Mỗi đỉnh thứ ~i~ được gán một màu ~c_i~. Bạn cần thực hiện lần lượt ~Q~ thao tác, mỗi thao tác thuộc một trong hai loại sau:

• Loại 1: 1 x y - nối toàn bộ các đỉnh có màu ~x~ với toàn bộ các đỉnh có màu ~y~.

• Loại 2: 2 u v - đổi màu của toàn bộ các đỉnh ~i~ có ~c_i = u~ thành ~c_i = v~.

Sau khi thực hiện xong tất cả các thao tác, hãy in ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, ..., c_N~ - màu ban đầu của từng đỉnh ~(1 \le c_i \le N)~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~t, x, y~ mô tả các thao tác ~(1 \le t \le 2, 1 \le x, y \le N)~.

Output

• In ra ~N~ số nguyên, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~. Nếu không tồn tại đường đi, in ra ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

0 1 -1 1 2

Notes

• Ban đầu: chưa có cạnh nào;

• Thao tác 1 1 2: Nối toàn bộ đỉnh màu ~1~ với toàn bộ đỉnh màu ~2~ ~\Rightarrow~ Tạo cạnh giữa các đỉnh ~{1, 5}~ với ~{2, 4}~;

• Thao tác 2 3 2: Đổi toàn bộ đỉnh màu ~3~ thành màu ~2~ ~\Rightarrow~ Đỉnh ~3~ có màu ~2~;

• Thao tác 1 2 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~;

• Thao tác 1 1 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~.

Sau cùng, đường đi ngắn nhất từ đỉnh ~1~ đến các đỉnh khác là:

• Đỉnh ~1~ ~\rightarrow~ chính nó: ~0~

• Đỉnh ~2~: ~1~ ~\rightarrow~ ~2~ (độ dài ~1~)

• Đỉnh ~3~: Không tồn tại đường đi (~-1~)

• Đỉnh ~4~: ~1~ ~\rightarrow~ ~4~ (độ dài ~1~)

• Đỉnh ~5~: ~1 \rightarrow 2 \rightarrow 5~ (độ dài ~2~)

Minh họa test ví dụ

Lời giải #1

Subtask 1

• Giới hạn bổ sung: ~N, Q \le 100~

Ý tưởng:

• Vì giới hạn của subtask này là nhỏ, chúng ta có thể giải quyết subtask này bằng cách thực hiện chính xác như những gì đề yêu cầu.

  • Với thao tác loại ~1~ với hai màu ~x~ và ~y~, chúng ta duyệt tuần tự để tìm tập các đỉnh có màu ~x~ và tập các đỉnh có màu ~y~ rồi với mỗi cặp đỉnh từ hai tập, ta thêm cạnh nối hai chiều giữa hai đỉnh.

  • Với thao tác loại ~2~ với hai màu ~u~ và ~v~, chúng ta duyệt tuần tự và gán màu ~v~ cho các đỉnh có màu ~u~

    ~ c[i] \leftarrow v \quad \forall \, (c[i] = u) ~

• Sau khi thực hiện xong tất cả các thao tác, để tìm ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị, ta có thể sử dụng thuật toán BFS từ đỉnh ~1~ trên đồ thị không trọng số dựng được.

Độ phức tạp:

• Cách giải như trên có độ phức tạp về thời gian là ~O(Q \cdot N^2)~ trong trường hợp xấu nhất

  • Quá trình đọc dữ liệu có độ phức tạp về thời gian là ~O(N + Q)~

  • Với mỗi thao tác loại ~1~, vì mỗi màu có ~O(N)~ đỉnh có màu đó, ta sẽ phải xem xét qua ~O(N^2)~ cặp đỉnh cho hai màu ~x~ và ~y~.

  • Với mỗi thao tác loại ~2~, ta phải quyệt qua ~O(N)~ đỉnh.

  • Bước chạy thuật toán BFS sẽ có độ phức tạp về thời gian là ~O(N + |E|)~ với ~|E|~ là số cạnh của đồ thị sau khi ta đã dựng xong. Vì dữ liệu có thể chứa ~O(Q)~ thao tác loại ~1~, ta có ~|E| = O(Q \cdot N^2)~. Nói cách khác, bước xử lý tìm đường đi ngắn nhất có độ phức tạp ~O(Q \cdot N^2)~

• Tương tự, độ phức tạp bộ nhớ của cách giải trên là ~O(Q \cdot N^2)~ trong trường hợp tệ nhất bởi ta phải lưu ~O(Q \cdot N^2)~ cạnh đồng thời cùng một lúc

Code minh họa:

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];

void addEdges(const int x, const int y) {
    for (int i = 1; i <= N; ++i) {
        if (c[i] != x)
            continue;
        for (int j = 1; j <= N; ++j) {
            if (c[j] != y)
                continue;
            graph[i].push_back(j);
            graph[j].push_back(i);
        }
    }
}

void changeColors(const int u, const int v) {
    for (int i = 1; i <= N; ++i)
        if (c[i] == u)
            c[i] = v;
}

void runBFS() {
    queue<int> q;

    minimumDistance[1] = 0;
    q.push(1);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++i) {
        minimumDistance[i] = INF;
        cin >> c[i];
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (t == 1)
            addEdges(x, y);
        else
            changeColors(x, y);
    }

    runBFS();

    for (int i = 1; i <= N; ++i)
        cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';

    cout << '\n';

    return 0;
}

Subtask 2

• Giới hạn bổ sung: Chỉ có thao tác loại ~1~

Ý tưởng:

• Với giới hạn của subtask này, ta có nhận xét rằng với hai đỉnh ~x~ và ~y~ đều khác ~1~ và có cùng màu thì đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~x~ và ~y~ nên bằng nhau. Nếu ta đặt ~d[i]~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~i~, ta có: ~\forall x, y \, (c[x] = c[y]) \land (x \neq 1) \land (y \neq 1) \rightarrow d[x] = d[y]~

  Chứng minh chi tiết:

  • Giả sử tồn tại hai đỉnh ~x~ và ~y~ đều khác ~1~ và có cùng màu nhưng đường đi ngắn nhất từ đỉnh ~1~ đến hai đỉnh ~x~ và ~y~ lại khác nhau. Không làm mất tính tổng quát, ta xét trường hợp ~d[x] < d[y]~
  • Xét một đường đi ngắn nhất bất kì từ ~1~ đến ~x~, gọi ~z~ là đỉnh ngay trước ~x~ trên đường đi đó (~1 \rightarrow ... \rightarrow z \rightarrow x~). Vì đồ thị chứa cạnh từ ~z~ tới ~x~, danh sách thao tác phải bao gồm ít nhất một thác như sau: 1 c[z] c[x]. Vì đỉnh ~x~ và ~y~ có cùng màu (~c[x] = c[y]~), đồ thị cũng chứa cạnh từ ~z~ tới ~y~. Điều này đồng nghĩa với việc tồn tại đường đi từ ~1~ tới ~y~ với độ dài ~d[z] + 1 = d[x]~ mà ~d[x] < d[y]~ (theo giả định trước đó) ~\Rightarrow~ Tồn tại đường đi từ ~1~ tới ~y~ với độ dài ngắn hơn ~d[y]~; mâu thuẫn với định nghĩa của ~d[y]~

• Từ nhận xét này, ta nhận thấy rằng trừ đỉnh ~1~, các đỉnh chỉ có thể được phân biệt với nhau bằng màu (nói cách khác, không có sự phân biệt giữa các đỉnh cùng màu). Dựa vào đây, ta có thể dùng màu để đại diện cho các đỉnh đó. Cụ thể hơn, thay vì xây dựng đồ thị như đề bài (với số cạnh trong trường hợp tệ nhất đạt xấp xỉ ~Q \cdot N^2~), ta có thể xây dựng một đồ thị khác ~G' = (V', E')~ có các đỉnh là các màu và có cạnh giữa ~x'~ và ~y'~ nếu tồn tại thao tác 1 x' y'. ~\Rightarrow~ Số cạnh của đồ thị ~G'~ sẽ không vượt quá ~Q~ (~|E'| = O(Q)~), cho phép chúng ta tìm đường đi ngắn nhất giữa đỉnh đại diện cho màu của đỉnh ~1~ và các đỉnh còn lại trong ~V'~ với độ phức tạp cho phép. Nếu đặt ~T = \{(t_i, x_i, y_i) \, | \, 1 \leq i \leq Q\}~ là tập hợp các thao tác sử dụng, ta có:

  • ~V' = \{c[u] \, | \, 1 \leq u \leq N \}~
  • ~E' = \{(x, y) \, | \, ((1, x, y) \in T) \land (x, y \in V') \}~

• Với các đỉnh ~x~ có màu khác với màu của đỉnh ~1~ (~c[x] \neq c[1]~), độ dài đường đi ngắn nhất từ ~1~ tới ~x~ sẽ bằng với độ dài đường đi ngắn nhất từ ~c[1]~ tới ~c[x]~ trong ~G'~.

• Với các đỉnh ~x~ không phải là đỉnh ~1~ nhưng có cùng màu với đỉnh ~1~ (~c[x] = c[1]~), ta sẽ có ba trường hợp sau:

  • Tồn tại thao tác 1 c[1] c[1] (nối giữa các đỉnh có màu ~c[1]~ với nhau) ~\Rightarrow~ Độ dài đường đi ngắn nhất từ ~1~ tới ~x~ bằng ~1~.
  • Không tồn tại thao tác như trên nhưng ~c[1]~ có cạnh nối tới màu khác (trong ~G'~) ~\Rightarrow~ Độ dài đường đi ngắn nhất từ ~1~ tới ~x~ bằng ~2~ (ta tốn một bước để từ đỉnh ~1~ đi đến một đỉnh bất kì có màu kề với ~c[1]~ rồi đi đến ~x~).
  • Các điều kiện trên đều không thỏa ~\Rightarrow~ Không tồn tại đường đi giữa ~1~ và ~x~

Độ phức tạp:

• Cách giải như trên có độ phức tạp về thời gian là ~O(N + Q)~ trong trường hợp xấu nhất bởi việc dựng đồ thị và tìm đường đi ngắn nhất (với thuật toán BFS) có độ phức tạp ~O(N + Q)~.

• Tương tự, độ phức tạp bộ nhớ của cách giải trên là ~O(N + Q)~ trong trường hợp tệ nhất.

Code minh họa:

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
bool existed[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];

void runBFS() {
    queue<int> q;

    minimumDistance[c[1]] = 0;
    q.push(c[1]);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    bool sourceFlag = false;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++i) {
        minimumDistance[i] = INF;
        cin >> c[i];
        existed[c[i]] = true;
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (!existed[x] || !existed[y])
            continue;
        graph[x].push_back(y);
        graph[y].push_back(x);
        if (x == c[1] && y == c[1])
            sourceFlag = true;
    }

    runBFS();

    cout << 0 << ' ';

    for (int i = 2; i <= N; ++i) {
        if (c[i] != c[1]) {
            cout << ((minimumDistance[c[i]] < INF) ? minimumDistance[c[i]] : (-1)) << ' ';
            continue;
        }
        cout << (sourceFlag ? 1 : ((!graph[c[1]].empty()) ? 2 : (-1))) << ' ';
    }

    cout << '\n';

    return 0;
}

Subtask 3

• Giới hạn bổ sung: Tất cả thao tác loại ~2~ xuất hiện trước thao tác loại ~1~

Ý tưởng:

• Ta nhận thấy rằng, nếu ta có thể cập nhật được màu các đỉnh sau khi xử lý xong các thao tác loại ~2~ (với độ phức tạp hợp lý), bài toán sẽ được đưa về subtask ~2~.

• Ta có nhận xét rằng mỗi thao tác loại ~2~ có thể được xem như gồm hai bước:

  • Gộp hai tập đỉnh lại thành một tập đỉnh.
  • Đánh số (tên màu) lại tập đỉnh mới. Ví dụ như trong sample test được đưa ra, thao tác 2 3 2 (thao tác thứ ~2~ trong danh sách các thao tác) có thể được xem như việc gộp tập đỉnh ~\{2, 4\}~ (có màu ~2~) và ~\{3\}~ (có màu ~3~) thành tập đỉnh mới ~\{2, 3, 4\}~ và đánh màu ~2~ cho tập đỉnh này.

• Dựa trên nhật xét này và giới hạn của subtask, chúng ta có thể sử dụng cấu trúc dữ liệu Disjoint Set Union để thực hiện các thao tác loại ~2~ và cập nhật màu của đỉnh.

Lưu Ý: Ý tưởng chỉ có thể giải quyết subtask ~3~ (và subtask ~2~), không thể áp dụng trong mọi trường hợp. Khi các thao tác loại ~1~ và loại ~2~ được thực hiện đan xen, một màu có thể có tập đỉnh thay đổi theo thời gian.

Độ phức tạp:

• Độ phức tạp về thời gian của ý tưởng nêu trên có thể là ~O(Q \cdot \alpha(N) + N)~ hoặc ~O(Q \cdot \log(N) + N)~ (tùy thuộc vào cách ta cài đặt cấu trúc dữ liệu Disjoint Set Union):

  • Nếu cấu trúc dữ liệu Disjoint Set Union được cài đặt với cả hai phương pháp gộp theo kích cỡ và nén đường đi thì độ phức tạp trung bình cho mỗi lần gộp tập đỉnh là ~O(\alpha(N))~ (với ~\alpha(N)~ là hàm Ackermann nghịch đảo). Nếu chỉ một trong hai phương pháp được sử dụng thì độ phức tạp cho mỗi lần gộp tập đỉnh là ~O(\log(N))~.
  • Độ phức tạp của các bước xử lý còn lại của cách giải đã nêu sẽ tương tự với cách giải cho subtask ~2~ trước đó, tức ~O(N + Q)~.

• Độ phức tạp về bộ nhớ của cách giải trên sẽ tương tự với subtask ~2~, tức ~O(N + Q)~.

Code minh họa:

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    void resize(const int n) {
        roots.resize(n, -1);
    }

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    int unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return x;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        return roots[y] = x;
    }

};

signed roots[MAX_N], minimumDistance[MAX_N];
vector<int> graph[MAX_N];
DisjointSetUnion dsu;
int N, Q, c[MAX_N];

void runBFS() {
    queue<int> q;

    minimumDistance[c[1]] = 0;
    q.push(c[1]);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    bool firstTypeOperationPhase = false, sourceFlag = false;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    dsu.resize(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> c[i];
        minimumDistance[i] = INF;
        int &root = roots[c[i]];
        root = (root ? dsu.unite(root, i) : i);
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (t == 2) {
            int &rootX = roots[x];
            if (rootX == 0)
                continue;
            int &rootY = roots[y];
            rootY = (rootY ? dsu.unite(rootX, rootY) : rootX);
            rootX = 0;
            continue;
        }
        if (!firstTypeOperationPhase) {
            for (int i = 1; i <= N; ++i)
                if (roots[i])
                    c[dsu.getRoot(roots[i])] = i;
            for (int i = 1; i <= N; ++i)
                c[i] = c[dsu.getRoot(i)];
            firstTypeOperationPhase = true;
        }
        if (roots[x] == 0 || roots[y] == 0)
            continue;
        graph[x].push_back(y);
        graph[y].push_back(x);
        if (x == c[1] && y == c[1])
            sourceFlag = true;
    }

    runBFS();

    cout << 0 << ' ';

    for (int i = 2; i <= N; ++i) {
        if (c[i] != c[1]) {
            cout << ((minimumDistance[c[i]] < INF) ? minimumDistance[c[i]] : (-1)) << ' ';
            continue;
        }
        cout << (sourceFlag ? 1 : ((!graph[c[1]].empty()) ? 2 : (-1))) << ' ';
    }

    cout << '\n';

    return 0;
}

Subtask 4

Ý tưởng:

• Việc xử lý trên đồ thị xây dựng như ở subtask ~1~ yêu cầu độ phức tạp thời gian lớn bởi đồ thị sẽ chứa rất nhiều cạnh (~O(Q \cdot N^2)~ cạnh). Tuy nhiên, ta nhận thấy rằng các thao tác này chỉ phụ thuộc vào mối quan hệ giữa các tập đỉnh chứ không bắt buộc phải giữa từng cặp đỉnh cụ thể. Do đó, ta có thể tìm cách xây dựng một đồ thị nén, trong đó:

  • Khoảng cách ngắn nhất từ đỉnh ~1~ đến cách đỉnh khác trong đồ thị gốc vẫn được giữ nguyên trong đồ thị mới này.
  • Số lượng cạnh không quá lớn.

• Để xây dựng một đồ thị có ít cạnh hơn nhưng vẫn giữ nguyên khoảng cách ngắn nhất, ta có thể tạo các đỉnh đại diện cho từng tập đỉnh cùng màu (ở một thời điểm).

  Chúng ta có thể xem xét một đồ thị ví dụ như sau để dễ hình dung ý tưởng hơn. Giả sử ta cần thêm các cạnh nối từ tất cả các đỉnh xanh đến tất cả các đỉnh cam. Mục tiêu của ta không phải là tạo đủ mọi cạnh giữa hai tập, mà chỉ cần đảm bảo rằng tồn tại đường đi có độ dài 1 từ tập xanh đến tập cam. Thay vì thêm ~r \times b~ cạnh (với ~r~ là số đỉnh xanh và ~b~ là số đỉnh cam), ta tạo hai đỉnh mới:

  • Đỉnh ~B~ với ý nghĩa là với mọi đỉnh có thể đến được từ đỉnh ~B~ thì cũng có thể đến được từ các đỉnh xanh tới tổng trọng số không đổi.
  • Đỉnh ~R~ với ý nghĩa là với mọi đỉnh có thể đến được đỉnh ~R~ thì cũng có thể đến được các đỉnh cam tới tổng trọng số không đổi. Sau đó:
  • Thêm các cạnh có trọng số ~0~ từ mỗi đỉnh xanh tới ~B~, và từ ~R~ tới mỗi đỉnh cam.
  • Thêm một cạnh có trọng số ~1~ từ ~B~ tới ~R~. Khi đó, đi từ một đỉnh xanh ~x~ tới một đỉnh cam ~y~ tương đương với đi qua đường ~x \rightarrow B \rightarrow R \rightarrow y~ có tổng trọng số ~1~. Bằng cách nén như vậy, số cạnh giảm từ ~r \times b~ xuống còn ~r + b + 1~.

• Mở rộng từ ý tưởng như trên, với mỗi tập đỉnh tại một điểm trong quá trình thực hiện các thao tác, ta sẽ tạo hai đỉnh đi và về (tương tự đỉnh ~B~ và ~R~ trong ví dụ trên) để đại diện cho tập đó. Cụ thể hơn:

  • Với mỗi màu và tập đỉnh của nó ở thời điểm ban đầu (khi chưa thực hiện bất kì thao tác nào trong danh sách), ta tạo hai đỉnh cùng cạnh trọng số ~0~ tương ứng (như ví dụ trên).
  • Khi ta xử lý thao tác loại ~2~, ta (có thể) sẽ có một tập đỉnh mới. Trong trường hợp đó, ta cũng tạo hai đỉnh mới đại diện cho tập đỉnh của màu sau khi được gộp lại và thực hiện nối như sau:
    • Ta nối các đỉnh đi của hai tập cũ đến đỉnh đi mới với trọng số ~0~.
    • Ta nối đỉnh về mới đến các đỉnh về của hai tập cũ với trọng số ~0~.
  • Khi ta xử lý thao tác loại ~1~, ta chỉ cần thêm cạnh trọng số ~1~ giữa đỉnh đến và đỉnh đi của các tập đỉnh được xem xét trong thác tác (ta sẽ thêm tối đa hai cạnh bởi cạnh bởi cạnh trong đồ thị gốc là vô hướng).

• Sau khi ta dựng xong đồ thị (sau khi xử lý xong hết các thao tác trong danh sách), để tìm đường đi ngắn nhất từ đỉnh ~1~ đến các đỉnh còn lại, ta có thể sử dụng thuật toán BFS 0-1 bởi các cạnh của đồ thị có trọng số ~0~ hoặc ~1~ (hoặc thuật toán Dijkstra nhưng với độ phức tạp lớn hơn).

Ý tưởng cho subtask này có nhiều điểm tương đồng với cách xây dựng Kruskal Reconstruction Tree.

Độ phức tạp:

• Độ phức tạp về thời gian của ý tưởng nêu trên là ~O(N + Q)~

  • Việc dựng đồ thị có độ phức tạp ~O(N + Q)~ bởi:
    • Khi dựng đỉnh mới và cạnh ở thời điểm ban điểm, ta sẽ thêm ~C~ đỉnh và ~2 \cdot N~ cạnh với ~C~ là số màu phân biệt ban đầu (~1 \leq C \leq N~; với mỗi đỉnh ban đầu, ta sẽ thêm hai cạnh mới).
    • Với mỗi thao tác loại ~2~, ta thêm tối đa hai đỉnh và bốn cạnh. Ta có ~O(Q)~ thao tác loại ~2~.
    • Với mỗi thao tác loại ~1~, ta thêm tối đa hai cạnh. Ta có ~O(Q)~ thao tác loại ~1~.
  • Thuật toán BFS 0-1 có độ phức tạp ~O(N + Q)~ vì đồ thị được dựng lên có ~O(N + Q)~ đỉnh và cạnh (nếu ta sử dụng thuật toán Dijkstra, độ phức tạp sẽ là ~O((N + Q)\log(N + Q) + N + Q)~).

• Tương tự, ý tưởng nêu trên có độ phức tạp về bộ nhớ là ~O(N + Q)~.

Code minh họa:

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 3E5 + 5, MAX_VERTEX_COUNT = 1E6 + 6, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
bool minimized[MAX_VERTEX_COUNT];
pair<int, int> vertexPairs[MAX_N];
vector<pair<int, bool> > graph[MAX_VERTEX_COUNT];
signed vertexCount, minimumDistance[MAX_VERTEX_COUNT];

void runBFS() {
    deque<int> q;

    for (int i = 2; i <= vertexCount; ++i)
        minimumDistance[i] = INF;

    q.push_back(1);

    for (; !q.empty();) {
        const int x = q.front();
        q.pop_front();
        if (minimized[x])
            continue;
        minimized[x] = true;
        for (const auto &[y, w] : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + w)) {
                if (w)
                    q.push_back(y);
                else
                    q.push_front(y);
            }
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    vertexCount = N;

    for (int i = 1; i <= N; ++i) {
        cin >> c[i];
        auto &[source, sink] = vertexPairs[c[i]];
        if (source <= 0) {
            source = ++vertexCount;
            sink = ++vertexCount;
        }
        graph[i].emplace_back(source, 0);
        graph[sink].emplace_back(i, 0);
    }

    for (int q = 1, t = 0; q <= Q; ++q) {
        cin >> t;
        if (t == 1) {
            int x = 0, y = 0;
            cin >> x >> y;
            const auto &[sourceX, sinkX] = vertexPairs[x];
            const auto &[sourceY, sinkY] = vertexPairs[y];
            if (sourceX && sinkY) {
                graph[sourceX].emplace_back(sinkY, 1);
                graph[sourceY].emplace_back(sinkX, 1);
            }
        } else {
            int u = 0, v = 0;
            cin >> u >> v;
            const auto [sourceU, sinkU] = vertexPairs[u];
            const auto [sourceV, sinkV] = vertexPairs[v];
            auto &[source, sink] = vertexPairs[v];
            vertexPairs[u] = make_pair(0, 0);
            source = ++vertexCount;
            sink = ++vertexCount;
            graph[sourceU].emplace_back(source, 0);
            graph[sourceV].emplace_back(source, 0);
            graph[sink].emplace_back(sinkU, 0);
            graph[sink].emplace_back(sinkV, 0);
        }
    }

    runBFS();

    for (int i = 1; i <= N; ++i)
        cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';

    cout << '\n';

    return 0;
}

Trình Chấm (tự viết):

import time
import shutil
import random
import subprocess
from abc import ABC
from pathlib import Path
from typing import List, Tuple

class TestGenerator(ABC):

    MIN_N: int = 1
    MAX_N: int = 300_000
    MIN_Q: int = 1
    MAX_Q: int = 300_000

    def __init__(self):
        self.N: int = 0
        self.Q: int = 0
        self.c: List[int] = []
        self.operations: List[Tuple[int, int, int]] = []
        self.generate()

    def generate(self):
        self.N = random.randint(self.MIN_N, self.MAX_N)
        self.Q = random.randint(self.MIN_Q, self.MAX_Q)
        self.c = [random.randint(1, self.N) for _ in range(self.N)]
        self.operations = self._generate_operations()

    def _generate_operations(self) -> List[Tuple[int, int, int]]:
        return [self._generate_random_operation(random.randint(1, 2)) for _ in range(self.Q)]

    def _generate_random_operation(self, operation_type: int) -> Tuple[int, int, int]:
        return (operation_type, random.randint(1, self.N), random.randint(1, self.N))

    def write_to_file(self, filename: str) -> None:
        path = Path(filename)
        path.parent.mkdir(parents = True, exist_ok = True)
        with path.open('w') as f:
            f.write(f"{self.N} {self.Q}\n")
            f.write(" ".join(map(str, self.c)) + "\n")
            for t, x, y in self.operations:
                f.write(f"{t} {x} {y}\n")

class Subtask1TestGenerator(TestGenerator):
    MAX_N = 100
    MAX_Q = 100

class Subtask2TestGenerator(TestGenerator):
    def _generate_operations(self) -> List[Tuple[int, int, int]]:
        return [self._generate_random_operation(1) for _ in range(self.Q)]

class Subtask3TestGenerator(TestGenerator):
    def _generate_operations(self) -> List[Tuple[int, int, int]]:
        second_type_operation_count = random.randint(0, self.Q)
        return [self._generate_random_operation(2 if i < second_type_operation_count else 1) for i in range(self.Q)]

class Subtask4TestGenerator(TestGenerator):
    pass

class Validator:

    TIME_LIMIT_IN_SECONDS = 1
    VERDICTS = ["AC", "WA", "TLE", "RE"]

    def __init__(self, tested_program_path: str, correct_program_path: str):
        self.tested_program = Path(tested_program_path)
        self.correct_program = Path(correct_program_path)
        for program in (self.tested_program, self.correct_program):
            if not program.exists():
                raise FileNotFoundError(f"Program not found: {program}")
            if not program.suffix.lower() == '.exe':
                raise ValueError(f"Program must be an .EXE file: {program}")

    def run_program(self, program_path: Path, input_file: Path, output_file: Path) -> Tuple[str, float, bool]:
        program_directory = program_path.parent
        destination_input = program_directory / "input.INP"
        shutil.copy(input_file, destination_input)
        destination_output = program_directory / output_file.name
        if destination_output.exists():
            destination_output.unlink()
        start_time = time.time()
        try:
            process = subprocess.run(
                [str(program_path)],
                stdout=subprocess.PIPE,
                stderr=subprocess.PIPE,
                timeout=self.TIME_LIMIT_IN_SECONDS,
                text=True,
                cwd=str(program_directory)
            )
            execution_time = time.time() - start_time

            if process.returncode != 0:
                return "RE", execution_time, False

            if destination_output.exists():
                with destination_output.open('r') as f:
                    output = f.read().strip()
            else:
                output = process.stdout.strip()

            return "OK", execution_time, True, output

        except subprocess.TimeoutExpired:
            return "TLE", self.TIME_LIMIT_IN_SECONDS, False, ""
        except Exception as e:
            return "RE", time.time() - start_time, False, str(e)
        return "IE", time.time() - start_time, False, ""

    def compare_outputs(self, tested_output: str, correct_output: str) -> str:
        tested_lines = [line.strip() for line in tested_output.splitlines() if line.strip()]
        correct_lines = [line.strip() for line in correct_output.splitlines() if line.strip()]

        if tested_lines == correct_lines:
            return "AC"
        return "WA"

    def validate_test(self, input_file: str) -> Tuple[str, float]:
        input_path = Path(input_file)
        input_directory = input_path.parent

        correct_verdict, correct_time, correct_success, correct_output = self.run_program(
            self.correct_program, input_path, self.correct_program.parent / "output.OUT"
        )
        if not correct_success:
            return f"Correct program failed: {correct_verdict}", correct_time

        answer_file = input_directory / "answer.txt"
        with answer_file.open('w') as f:
            f.write(correct_output)

        tested_verdict, tested_time, tested_success, tested_output = self.run_program(
            self.tested_program, input_path, self.tested_program.parent / "output.OUT"
        )
        if not tested_success:
            return tested_verdict, tested_time

        output_file = input_directory / "output.out"
        with output_file.open('w') as f:
            f.write(tested_output)

        verdict = self.compare_outputs(tested_output, correct_output)
        return verdict, tested_time

SUBTASK_GENERATORS = [
    Subtask1TestGenerator,
    Subtask2TestGenerator,
    Subtask3TestGenerator,
    Subtask4TestGenerator,
]

SUBTASK_TEST_PERCENTAGES = [20, 30, 20, 30]

TOTAL_TEST_COUNT = 100

if __name__ == "__main__":
    random.seed(20251004)
    subtask_test_counts = [TOTAL_TEST_COUNT * percentage // 100 for percentage in SUBTASK_TEST_PERCENTAGES]
    validator = Validator(
        tested_program_path = "programs/tested_program/main.exe",
        correct_program_path = "programs/correct_program/main.exe",
    )
    overall_summary = {}
    for verdict in Validator.VERDICTS:
        overall_summary[verdict] = 0
    for subtask_index in range(len(SUBTASK_GENERATORS)):
        generator = SUBTASK_GENERATORS[subtask_index]()
        subtask_summary = {}
        for verdict in Validator.VERDICTS:
            subtask_summary[verdict] = 0
        for test_index in range(subtask_test_counts[subtask_index]):
            filename = f"tests/subtask{subtask_index + 1:02d}/test{test_index + 1:02d}/input.INP"
            generator.generate()
            generator.write_to_file(filename)
            verdict, tested_time = validator.validate_test(filename)
            subtask_summary[verdict] += 1
            print(f"Subtask {subtask_index + 1}, Test {test_index + 1}: Verdict = {verdict}, Time = {tested_time:.3f}s")
        print(f"Subtask {subtask_index + 1} Summary:")
        for verdict, count in subtask_summary.items():
            overall_summary[verdict] += count
            print(f"\t{verdict}: {count} tests")
    print("Overall Summary:")
    for verdict, count in overall_summary.items():
        print(f"\t{verdict}: {count} tests")

Lời giải #2

Subtask ~1~: ~N, Q \le 100~

Đây là subtask đơn giản nhất của bài toán. Đối với subtask này, ta chỉ cần xây dựng đồ thị theo yêu cầu của bài toán là giải được.

Việc tìm đường đi ngắn nhất từ đỉnh ~1~ có thể được thực hiện bằng thuật toán BFS.

Độ phức tạp của thuật toán và các subtask nói chung là bằng ~\mathcal{O}(A + B)~ với ~A~ là thời gian xây dựng đồ thị, còn ~B~ là thời gian thực hiện tìm đường đi ngắn nhất tới các đỉnh.

Đối với subtask này, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q \times N^2), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(N^2)~.

Subtask ~2~: chỉ có thao tác loại ~1~

Cách nối các cặp đỉnh là không hiệu quả với giới hạn cao (~N \le 3 \times 10^5~) nên ta cần một hướng tiếp cận khác.

Ta sẽ chia các đỉnh dựa trên màu sắc của chúng. Mỗi nhóm màu sắc sẽ có hai đỉnh ảo: một đỉnh ảo đi vào và một đỉnh ảo đi ra.

Ở hình minh hoạ dưới đây, các đỉnh được nhóm theo màu, các đỉnh màu xanh lá là các đỉnh ảo đi ra còn màu đỏ là các đỉnh ảo đi vào nhóm màu đó.

Với mỗi truy vấn loại ~1~, ta sẽ xây dựng các cung nối các đỉnh ảo như sau:

• Nối đỉnh ảo đi ra của màu ~x~ với đỉnh ảo đi vào của màu ~y~
• Nối đỉnh ảo đi ra của màu ~y~ với đỉnh ảo đi vào của màu ~x~

Hình minh hoạ dưới đây là đồ thị sau truy vấn 1 1 2.

Trọng số của các cung được phân định như nhau: các cung nối đỉnh thực với đỉnh ảo hoặc đỉnh ảo với đỉnh thực có trọng số là ~0~, các cung nối các đỉnh ảo với nhau có trọng số là ~1~. Với các giá trị trọng số này, việc tìm đường đi ngắn nhất từ đỉnh ~1~ có thể được thực hiện bằng thuật toán BFS 0 - 1.

Đối với subtask ~2~, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(Q)~.

Subtask ~3~: Tất cả thao tác loại ~2~ xuất hiện trước thao tác loại ~1~

Các thao tác loại ~2~ là các thao tác thay đổi màu sắc của các đỉnh trên đồ thị. Vì vậy, với các thao tác loại ~2~ xuất hiện trước, ta chỉ cần thay đổi các giá trị màu sắc thành màu mới tương ứng. Sau đó, khi còn lại các thao tác loại ~1~, ta thực hiện giống như subtask ~2~.

Giống như subtask ~2~, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(Q)~.

Subtask ~4~: không có giới hạn bổ sung

Đối với subtask cuối cùng, hướng giải quyết sẽ tương tự với subtask ~2~, tuy nhiên sẽ có đôi chút điểm khác biệt.

Đối với các thao tác loại ~1~, việc thêm các cạnh và trọng số sẽ giống hệt như subtask ~2~.

Còn với các thao tác loại ~2~, ta xử lí như sau: tạo hai đỉnh ảo vào và ra mới cho màu ~v~. Sau đó, ta tạo cung nối đỉnh ra cũ của hai màu ~u, v~ với đỉnh ra mới của màu ~v~, và tạo cung nối đỉnh vào mới của màu ~v~ với đỉnh ra cũ của hai màu ~u, v~. Các cung mới này có trọng số là ~0~.

Ở hình minh hoạ này mô tả đồ thị sau truy vấn thao tác loại ~2~ 2 2 3.

Sau khi nối xong, ta coi đỉnh ảo vào và ra cũ của ~u, v~ "hết hạn sử dụng" - không coi các đỉnh ảo này là đại diện cho các nhóm các đỉnh chung màu nữa.

Một lưu ý nữa là nếu không có nhóm điểm màu ~u~ hoặc ~v~ hoặc cả hai thì ta không cần thiết phải nối các đỉnh ảo của nhóm màu đấy với các đỉnh ảo mới của ~v~.

Sau khi xây dựng xong, ta có thể tìm đường đi ngắn nhất từ đỉnh ~1~ bằng BFS 0 - 1.

Giống như subtask ~2~ và ~3~, ta có độ phức tạp ~\mathcal{O}(A + B)~ với ~A = \mathcal{O}(Q), B = \mathcal{O}(|V| + |E|)~ với ~|V| = \mathcal{O}(N), |E| = \mathcal{O}(Q)~.

Xin trân trọng cảm ơn các tác giả đã đồng hành cùng chuyên mục. Các tác giả có bài giải được đăng trong Tạp chí VNOI - Số 1 đã được đội ngũ Tạp chí VNOI liên hệ để nhận phần quà tri ân từ VNOI.

Xin chào các bạn!

Chào mừng các bạn đến với chuyên mục FAQ của tạp chí VNOI. Đây là nơi chúng mình sẽ giải đáp tất cả những thắc mắc, băn khoăn của các bạn về câu lạc bộ, về con người và về những dự án mà VNOI đang ấp ủ.

Trong số đầu tiên này, chúng mình đã nhận được rất nhiều câu hỏi thú vị. Hãy cùng VNOI đi tìm câu trả lời cho 3 câu hỏi được quan tâm nhất nhé!

1. VNOI được hình thành như thế nào?

VNOI (Viet Nam Olympiad in Informatics) là cộng đồng của các học sinh, sinh viên đam mê bộ môn tin học. Được thành lập từ năm 2008 bởi các cựu học sinh khối chuyên toán tin trên cả nước đã tham gia các kỳ thi học sinh giỏi quốc gia và quốc tế - với sứ mệnh lan toả, thúc đẩy và phát triển nền Tin học Việt Nam - VNOI đã nhận được sự tham gia, ủng hộ và đóng góp của đông đảo thế hệ học sinh, sinh viên.

Trái với suy nghĩ của nhiều người, VNOI không bắt đầu như một CLB có cơ cấu tổ chức, mà nó ra đời với tư cách là một diễn đàn. Người sáng lập ra VNOI lúc ban đầu là anh Ngô Minh Đức. Đồng hành cùng anh Đức là các admin đời đầu có thể kể đến như: anh Khúc Anh Tuấn, Đoàn Mạnh Hùng, Nguyễn Hoành Tiến, Nguyễn Minh Hiếu.

Cũng trong khoảng thời gian đó, ấp ủ ý tưởng về một trình chấm trực tuyến cho các bạn học sinh, sinh viên Việt Nam, nhóm các sinh viên bao gồm anh Nguyễn Đình Tư và Nguyễn Minh Hiếu đã lập ra VOJ với sự hỗ trợ của ban quản trị SPOJ, với mục đích ban đầu là để tạo sân chơi cho các bạn đội tuyển của THPT Chuyên Sư Phạm - Đại học Quốc Gia Hà Nội, và VOJ ngày ấy cũng chính là tiền thân của VNOJ sau này. Vào năm 2020, VNOI đã có những dự án chuyển một số bài tập từ VOJ lên hệ thống Codeforces (với nguyên nhân chính là VOJ dần xuất hiện những điểm yếu so với những hệ thống chấm bài hiện đại), tuy nhiên, dù việc tải các bài tập lên hệ thống Codeforces đã chính thức hoàn tất, ban quản trị vẫn nhận thấy sẽ có nhiều sự bất tiện khi Codeforces có thể bị sập hay lag khi diễn ra contest, gây ra hạn chế cho các bạn muốn luyện tập các nguồn bài từ VOJ. Chính vì lẽ đó, VNOI quyết định phát triển dự án VNOJ - VNOI Online Judge - với mong muốn tạo ra một hệ thống chấm bài riêng của Việt Nam: “do người Việt, vì người Việt”. Ngày 28/02/2021, Đại hội thành lập Câu lạc bộ Olympic Tin học Việt Nam (VNOI) đã được diễn ra dưới sự tham dự và chỉ đạo của đại diện hội Tin học Việt Nam (VAIP), đánh dấu thời khắc VNOI trở thành một nhánh của Hội, và ngày 07/04/2021 VNOI chính thức có bài đăng giới thiệu về VNOJ trên fanpage của CLB.

Trong gần 2 thập kỷ qua, VNOI đã phát triển từ một diễn đàn nhỏ trở thành một CLB vững mạnh với một hệ thống sinh thái học tập mở, có thể kể đến như:

• VNOJ - VNOI Online Judge: hệ thống chấm bài trực tuyến hàng đầu tại Việt Nam, nơi đông đảo các bạn trẻ tin tưởng và lựa chọn cho quá trình ôn tập trước thềm các kỳ thi lớn như VOI, ICPC, và Olympic Tin học Sinh viên. Tính đến ngày 28/01/2024, VNOJ đã tiếp nhận và xử lý 4744496 lượt nộp bài, tương ứng khoảng 4688 lượt nộp bài trong một ngày.
• VNOI Wiki: Thư viện VNOI được xây dựng với mục đích chia sẻ kiến thức Tin học đến với tất cả mọi người.
• VNOI Roadmap: một lộ trình học tập hoàn hảo được đánh giá theo mức độ khó tăng dần - phù hợp cho tất cả các đối tượng học sinh, sinh viên, và đặc biệt hữu ích cho các bạn mới bắt đầu tiếp xúc với Tin học và Lập trình thi đấu.
• Các giải đấu thường niên, uy tín như VNOI Cup (lần đầu tổ chức năm 2022) ra đời, tạo ra sân chơi cọ xát đỉnh cao cho cộng đồng.

Với việc cung cấp kho tàng kiến thức Wiki - phổ cập nhiều kiến thức chuyên sâu về thuật toán trong Lập trình thi đấu và trang chấm bài VNOJ, VNOi đã là người bạn đồng hành của nhiều bạn học sinh, sinh viên tham gia các đấu trường quốc tế như ICPC World Finals, IOI, …, góp phần nâng vị thế của Việt Nam trên đấu trường quốc tế và thường xuyên góp mặt trong top 10 quốc gia dẫn đầu tại IOI mỗi năm. Năm 2022 cũng đánh dấu một cột mốc đặc biệt với nền Tin học Việt Nam khi đội tuyển EggCentroy đến từ Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội (UET) là đội tuyển Việt Nam đầu tiên giành được huy chương tại Kỳ thi Lập trình sinh viên quốc tế ICPC World Finals 2021 - cũng là tấm huy chương đầu tiên của Đông Nam Á.

Bên cạnh giao lưu kiến thức chuyên môn, VNOI còn là nơi giao lưu, kết nối giữa nhiều thế hệ. Hiện nay, nhiều cựu thành viên VNOI đã trở thành những tên tuổi lớn trong ngành lĩnh vực Tin học và Công nghệ thông tin như: anh Phạm Văn Hạnh (HCV IOI 2015), anh Lê Yên Thanh (người sáng lập Busmap), Phạm Nam Long (CEO Abivin), Lê Xuân Mạnh (CTO Kyber Network), Nguyễn Việt Dũng (CTO Krystal)... Bên cạnh đó là rất nhiều chuyên gia, kỹ sư đang làm việc tại các tập đoàn toàn cầu như Google, Facebook, Microsoft hay trở thành giáo sư, nhà nghiên cứu hàng đầu tại các trường Đại học.

Chính sự kết nối và "truyền lửa" liên tục qua các thế hệ này chính là sức mạnh và giá trị bền vững mà VNOI đã và đang hướng đến.

2. Làm sao để mình có thể tham gia đóng góp cho VNOI?

VNOI luôn chào đón mọi sự chung tay góp sức từ tất cả các bạn trên khắp mọi miền Tổ quốc! Có hai cách chính để bạn có thể tham gia đóng góp cho VNOI:

Cách 1: Trở thành Tình nguyện viên (TNV) chính thức qua các đợt tuyển:

VNOI vận hành như một CLB với nhiều phân nhóm (như team kĩ thuật, team contest, team wiki và team cộng đồng). Định kỳ, VNOI sẽ có các đợt tuyển TNV để tìm kiếm những thành viên mới, những người sẵn sàng dành thời gian và tâm huyết để cùng chúng mình xây dựng nên một cộng đồng ngày càng lớn mạnh.

Để có thể trở thành một TNV chính thức của VNOI, hãy theo dõi fanpage VNOI để cập nhật thông tin về các đợt tuyển quân nhé.

Cách 2: Đóng góp tự do thông qua các dự án hiện có của VNOI:

Nếu bạn không phải là TNV VNOI, nhưng vẫn rất yêu quý VNOI và muốn góp sức, bạn vẫn có thể:

• Viết bài cho VNOI Wiki: Chia sẻ các kiến thức học thuật, bài giảng về những thuật toán thú vị,...
• Đóng góp “tag problem” cho bài tập trên VNOJ: Giúp phân loại kho tàng bài tập khổng lồ của VNOJ, để các bạn đi sau dễ dàng tìm kiếm và luyện tập theo chủ đề.

Mọi sự đóng góp, dù là nhỏ nhất, đều vô cùng quý giá và góp phần trực tiếp xây dựng cộng đồng Tin học Việt Nam ngày một lớn mạnh.

3. Trong những năm qua, VNOI tự hào nhất về thành tựu hoặc tác động nào mà CLB đã tạo ra?

Ngay từ khi thành lập, chúng mình đã đặt ra sứ mệnh "thúc đẩy và phát triển nền Tin học Việt Nam" - một hành trình đầy tham vọng và cũng nhiều thách thức, đặc biệt là khi chúng mình quyết tâm rằng VNOI là một tổ chức phi lợi nhuận và hoạt động hoàn toàn dựa trên sức lực của các bạn Tình nguyện viên và các bạn trẻ mong muốn cống hiến. Điều VNOI tự hào nhất là đã xây dựng và duy trì thành công một hệ sinh thái học tập phi lợi nhuận, mở và hoàn toàn miễn phí.

• Trước đây, tài liệu và môi trường luyện tập chất lượng cao chỉ tập trung ở các thành phố lớn hoặc các trường chuyên. Với VNOJ - hệ thống chấm bài tự động với hàng ngàn bài tập và các contest được diễn ra liên tục và chất lượng và VNOI Wiki - kho tàng kiến thức học thuật từ cơ bản đến nâng cao, đã phá vỡ rào cản đó. Giờ đây, bất kỳ học sinh nào, dù ở vùng sâu vùng xa, chỉ cần có kết nối Internet là có thể tiếp cận được nguồn tài liệu và nền tảng luyện tập ngang bằng với các bạn ở những thành phố lớn.
• VNOI đã trở thành cầu nối vô giá giữa các thế hệ yêu Tin học. Những cựu học sinh chuyên Tin, những người đã thành danh hoặc đang theo học tại các trường đại học hàng đầu, nay quay về đóng góp với tư cách là admin, người ra đề, người viết bài… thậm chí có những admin VNOI còn vô cùng trẻ tuổi và tài năng. Điều này tạo ra một vòng tuần hoàn tri thức và đam mê, "cho đi và nhận lại", khiến ngọn lửa Tin học được truyền đi không bao giờ tắt.

Cuối cùng, mình chỉ muốn nói là điều VNOI tự hào nhất chính là đã góp phần tạo ra một sân chơi bình đẳng, nơi tất cả mọi người đều có cơ hội học hỏi, phát triển và kết nối với nhau bằng niềm đam mê chung. Xin chào các bạn!

Giới thiệu

Nhân vật khách mời thứ 2 của Tạp chí VNOI lần này là một người thầy vô cùng nổi tiếng không chỉ trong cộng đồng Lập trình thi đấu mà còn cả trong cộng đồng Tin học nói chung. Thầy là đồng tác giả trong cuốn Sách giáo khoa Chuyên Tin nổi tiếng, và cũng đã dẫn đoàn dự thi IOI của Việt Nam trong nhiều năm, trong đó có năm 1999 - khi Việt Nam đứng đầu thế giới với 3 huy chương vàng. Và hôm nay chúng mình xin được giới thiệu đến mọi người, thầy Nguyễn Thanh Tùng.

Phỏng vấn

Khi mà Tin học còn là một lĩnh vực rất mới, cơ duyên nào đã đưa thầy đến với sự lựa chọn này?

Hiện tại thì Tin học không còn là “môn mới” nữa – mọi người đều đã quen biết, trẻ em được tiếp xúc với môn học này từ rất sớm. Nhưng trước đây thì nền Tin học vẫn còn non trẻ, và tôi bước vào ngành Tin học theo sự sắp đặt của xã hội.

Những năm 60 của thế kỷ XX là thời kỳ kỷ luật Xã hội Chủ nghĩa rất mạnh – sinh viên không phải chọn ngành, nhà nước phân công, phân ngành dựa trên nhu cầu phát triển của xã hội. Tình cờ, tôi được phân vào ngành “Toán học Tính toán”. Thời kì ấy chưa có tên gọi Tin học, Tin học nằm trong toán và là khoa học tính toán. Sở thích của tôi lúc bấy giờ là Hoá học, nói chung tôi chỉ biết sơ qua về sự tồn tại của máy tính, vì thế không có sở thích rõ rệt với ngành học. Tuy nhiên, nhà nước đã phân công, và sinh viên chúng tôi cần tích cực tiếp nhận, nỗ lực làm tốt công việc của mình.Và vì thế, tôi là một trong những người tham gia vào lĩnh vực Tin học Việt Nam tương đối sớm.

Thầy là một trong những người thầy đầu tiên của nền Tin học Việt Nam. Trong thời kỳ đầu, thầy đã gặp những khó khăn, trở ngại gì, và thầy đã vượt qua như thế nào?

Giống như hoàn cảnh chung của Việt Nam cho tới giữa những năm 90 của thế kỉ XX: tài liệu rất khan hiếm và mọi người phải hết sức cố gắng đọc, tìm hiểu thêm.

Đặc biệt, mọi người phải chắt chiu từng giờ máy một. Số lượng máy ít ỏi nên, chi phí sử dụng máy lúc bấy giờ cực kỳ đắt – một giờ dùng máy tính bằng vài ba chục ngày công lao động. Vì thế mọi người đều phải cố gắng làm việc nghiêm túc, hiệu quả nhất có thể.

Vậy thì khi đó, trước khi đưa mã nguồn lên máy chạy, các thầy cần kiểm tra rất đúng không ạ?

Thời kỳ đó, chúng tôi có những đợt thực tập được sử dụng máy, và phải làm việc trực tiếp bằng lệnh máy, không phải ngôn ngữ lập trình thông thường. Khi đó có ba loại ngôn ngữ lập trình phổ biến COBOL, Fortran và ALGOL-60. Người sử dụng bình thường chủ yếu dùng Fortran và ALGOL-60, còn người làm Tin học sẽ chủ yếu sử dụng ALGOL-60.

Đương nhiên, chúng tôi phải rất cẩn thận trong lập trình. Sau khi lập trình xong, chúng tôi phải đục lỗ trên băng/bìa và gửi cho chạy. Nếu có sai sót gì thì về phải sửa và gửi lại, có khi mất cả ngày trời mới lại có kết quả.

Chính vì vậy, việc lập trình đòi hỏi sự cẩn thận chu đáo từng tí một, và đặc biệt rất là tiết kiệm giờ - nếu như chạy máy quá nhiều giờ, kinh phí sẽ không thể đủ, không ai có thể có đủ kinh tế để chi trả như thế cả. Mặc dù chúng tôi được nhà trường tạo điều kiện rất nhiều, nhưng không có nghĩa là được phung phí quá mức khả năng chi trả của Khoa.

Dạ thưa thầy, vậy máy tính là của công ty/đơn vị nào ạ?

Tôi học ở Nga, khi đó có hai loại máy: máy của nhà trường, và máy của các xí nghiệp liên kết với nhà trường. Chúng tôi được tạo điều kiện được thực tập ở các xí nghiệp đó. Nhưng (ở xí nghiệp) thường thường chúng tôi phải làm vào chiều tối và ban đêm, vì ban ngày được dành cho phục vụ sản xuất, trong khi máy của nhà trường sẽ dành cho nghiên cứu khoa học và các khoá luận, đồ án tốt nghiệp của sinh viên. Cũng vì thế, các đợt thực tập của sinh viên năm nhất, năm hai sẽ bị đẩy lùi lại, nếu không chịu khó, cố gắng sẽ không làm được quá nhiều việc.

Thầy thấy việc dạy và học ở Việt Nam có khác gì ở nước ngoài không ạ?

Khi trở về Việt Nam, tôi may mắn được dạy Đại Học Bách Khoa. Ở Đại Học Bách Khoa, phần lớn giảng viên trưởng thành từ các trường đào tạo của Nga, thành ra phong cách làm việc của chúng tôi cũng hao hao những ngày còn theo học ở nước ngoài.

Thời kì ấy, toàn bộ miền Bắc Việt Nam chỉ còn một máy Minsk-22 thôi, thành ra việc thực tập của mọi người là chuyện rất là hiếm hoi – nó chỉ như cuộc “thử nghiệm” một lần. Sau này, máy Minsk-22 được chuyển giao cho trường Đại Học Bách Khoa, từ đó có nhiều cơ hội làm việc hơn. Giữa những năm 80, Việt Nam đặt mua máy EC-1022 – loại máy tính tương đương với máy IBM 360/40 gần như hiện đại nhất của nước mình (trong miền Nam, Mỹ đã đưa máy IBM 360/50 hiện đại hơn). Máy tính của trường Bách Khoa chiếm diện tích hơn 200m2, bằng nhiều phòng gộp lại để có thể lắp ráp và chạy như bình thường.

Lúc bấy giờ, để dùng máy tính, ta phải điền đục lỗ. Muốn có được chương trình, phải gửi chương trình đó cho bộ phận xuyên phiếu, và lấy tấm bìa đã được xuyên đem ra cho bộ phận chạy. Chúng tôi ở ngay trong nhà trường, được phụ trách máy và tự mình chạy lấy, nhưng không thể chạy vô tội vạ vì còn phải phục vụ các hợp đồng sản xuất.

Ở thời kỳ đầu, khi đưa môn Tin học xuống phổ thông, tình hình lúc ấy như thế nào, và khó khăn ra sao ạ?

Lần đầu tiên đưa Tin học vào nhà trường phổ thông là năm 1995 với chương trình phân ban, có lẽ đó là chương trình Tin học phổ thông thành công nhất. Nhờ chương trình phân ban, những em học sinh có hứng thú với công nghệ mới chọn học, vì thế thái độ học rất nghiêm túc. Cộng thêm sự xuất hiện của máy vi tính, mỗi trường được trang bị từ 8 – 10 máy, “nguồn vốn” đó đối với năm 1995 là đủ để cho các bạn học sinh được thực hành, làm việc. Cả học sinh và giáo viên đều hào hứng hơn khi được tiếp cận với Tin học – với cái “mốt” của thời đại.

Sau này, đáng tiếc, không được như vậy nữa. Khi mà máy tính trở nên phổ biến, người ta thấy rằng chuyện đó quá đơn giản, và không còn chú tâm như xưa. Họ tập trung vào khai thác những gì đã có sẵn trên máy, việc tự mình học tập, tự mình tìm hiểu, tự mình làm ra sản phẩm thì ít được chú ý hơn. Cái gì nhiều quá thì nó trở thành bình thường.

Trong quá trình thầy dạy cả phổ thông lẫn đại học, thầy thấy tâm đắc nhất điều gì?

Bất kì ngành nghề nào cũng có những học sinh, sinh viên rất giỏi, và cũng có những bạn khá yếu, đó là chuyện bình thường. Tuy nhiên, đối với ngành Tin học, sinh viên nào giỏi thì sẽ cực giỏi, còn sinh viên nào đã kém thì … sẽ cực kém. Tin học đòi hỏi sự say mê, và tính “kỷ luật xã hội” của chúng ta chưa cao lắm. Điều đó dẫn đến chuyện năng suất làm việc trong Tin học của một số người rất yếu, và càng yếu thì họ càng xa rời nó thôi. Do đó trình độ phân hoá trong một lớp học đã rất lớn rồi, chưa nói đến giữa các ngành nghề khác nhau, sử dụng Tin học như công cụ.

Thầy có ấn tượng với các cá nhân, các khoá học sinh nào có thành tựu lớn, có đóng góp lớn cho nền Tin học không ạ?

Đóng góp thì tôi nghĩ có rất nhiều người đóng góp, trong nhiều lĩnh vực khác nhau, cũng thuộc Tin học, nhưng thuộc nhiều ngành nghề khác nhau. Từ năm 1989, chúng ta có Olympic Tin học Quốc tế, nước mình tham gia từ năm 1989 tới bây giờ, và năm nào cũng có giải chính thức. Đặc biệt, năm 1999 ở Thổ Nhĩ Kỳ, chúng ta còn đứng nhất thế giới!

Thực sự mà nói, những học sinh của mình, bạn nào giỏi thì sẽ cực giỏi. Đó là đặc trưng của khu vực châu Á – aicó sự kiên trì, tính kỷ luật, và có đam mê, sẽ đào rất sâu vào lĩnh vực đó.

Olympic Học sinh giỏi Tin học (IOI) bấy giờ chỉ được cử ba học sinh đi thi, trong khi thi Olympic sinh viên (ICPC) được cử đi nhiều hơn, từ một đến hai, thậm chí ba đội. Từ những năm 2000 trở lại đây, nước ta có tham gia thi ICPC, tuy nhiên, với tầng lớp sinh viên hồi đấy, thành tích ở mức tạm, chưa được cao lắm nhưng cũng không phải là quá tệ.

Đối với học sinh, việc đào tạo trong nhà trường, mặt bằng giáo dục cao hơn, nên có phong trào của tất cả các trường. Chính vì vậy, ta chọn được lớp tốt nhất, và ta cũng có nhiều học sinh giỏi hơn. Mặt khác, sinh viên lại theo từng trường, không thể tập hợp toàn bộ trí tuệ toàn quốc: Trường nào làm được công việc tốt thì sẽ gặt hái được kết quả tương đối khá. Trong khi đó, Học sinh giỏi Quốc gia sẽ tập trung tất cả học sinh và chọn các phần tinh tú nhất.

Với việc thi ICPC, em thấy rằng một team mạnh không chỉ là sự kết hợp của ba bạn mạnh, mà được cấu thành từ những bạn với các điểm mạnh khác nhau. Thầy có nhận xét gì về thi ICPC so với thi Học sinh giỏi ạ ?

Việc chọn lọc đội tuyển ICPC như chọn đội tuyển bóng đá giữa các thành phố - được cục bộ hoá. Các đội ICPC đi thi như những trận bóng giữa các thành phố với nhau, chất lượng trung bình sẽ không cao bằng “Đội tuyển Quốc gia” – các bạn thi HSGQG.

ICPC đòi hỏi tính hoàn thiện tuyệt đối, khác với đánh giá mức độ hoàn thiện của VOI. Học sinh khi thi HSGQG, thỏa mãn được bao nhiêu test sẽ nhận được điểm tương ứng với kết quả, trong khi đó, sinh viên cần phải làm đúng 100% mới được công nhận tương xứng. Cách làm việc của hai phía cũng khác nhau. Học sinh thi cá nhân thuần túy, sinh viên được đòi hỏi phải có tinh thần đồng đội, tính tổ chức, phương pháp làm việc thích hợp. Một số đội ít chú ý đến việc tổ chức phối hợp đồng đội, thì năng suất làm việc sẽ giảm đi đáng kể.

Hiện nay, Bộ Giáo Dục đang đẩy mạnh phổ cập môn Tin học đến các cấp phổ thông. Năm vừa rồi, Tin học lần đầu tiên được đưa vào làm một trong các môn thi tốt nghiệp. Thầy có nhận xét gì về vai trò của môn Tin học hiện nay?

Từ việc được thực hiện chương trình phân ban 1995 từ năm 1999, Tin học đã được phổ cập toàn bộ ở cấp phổ thông. Tuy nhiên ở thời đó, môn Tin học chưa phải là môn để đi thi. Việc đưa Tin học vào một trong các môn thi sẽ là động lực cho cả học sinh và giáo viên, nâng cao chất lượng giáo dục. Với sự chú ý đó, kiến thức tin học sẽ không thay đổi ngày một ngày hai, nhưng sẽ tiến triển dần dần, ngày một tăng lên.

Thầy có lời khuyên gì cho thế hệ học sinh / giáo viên trẻ đang theo đuổi ngành Tin học không ạ?

Tôi đã nhận lời tham gia giảng dạy trong một trại hè mùa thu năm nay tại UIT (trường Đại Học Công nghệ Thông tin, Đại học Quốc gia thành phố Hồ Chí Minh). Trại hè bao gồm các học sinh tham gia học chương trình thuật toán, những bạn sinh viên đã qua đào tạo chuyên sâu, và những bạn sinh viên mới bắt đầu. Trong đó, bao giờ tôi cũng nhấn mạnh đối với học tập và nghiên cứu, đặc biệt là môn Tin học, đòi hỏi cả kiến thức và kĩ năng: Không chỉ là ta biết, mà ta còn phải làm được.

Vì vậy, ta cần duy trì cho học sinh cái sự nỗ lực cố gắng, sẵn sàng vượt qua mọi khó khăn. Khi dạy, ta có những đặc thù cần phải nhắc, phải lưu ý cho học sinh sinh viên. Đặc biệt, với các bạn sinh viên năm nhất, năm hai, những ví dụ cụ thể với tác động trực tiếp lên sinh viên sẽ cực kì hiệu quả.

Tin học không chỉ đơn thuần là từ toán mà ra, nó bao gồm tất cả các mặt của khoa học kĩ thuật và đời sống xã hội. Chính vì thế, ta có thể thâm nhập nhiều lĩnh vực khác nhau, với Tin học là công cụ hỗ trợ đắc lực. Tin học nằm trong diện toán rời rạc, có nhiều thứ không dính dáng gì đến nhau. Nhưng nếu con người ta bắt nhịp được nhịp điệu, quy luật của bộ môn này, thì ta mới nhanh chóng lĩnh hội được kiến thức.

Không biết các bạn đã từng nghe bài Trường Ca Sông Lô của Văn Cao chưa?

Em đã từng nghe rồi mà em không thuộc ạ.

Toàn bộ bài hát ấy, lời văn rất là trúc trắc. Ví dụ như hai câu đầu:

Nghe có vẻ rất trúc trắc. Nhưng nếu ta nghe cái âm nhạc của nó, và ta nghe lặp lại chỉ một vài lần, thì hoàn toàn có thể “thuộc” và nhớ lại được câu này.

Chỉ khi con người ta bắt nhịp được nhịp điệu, thì ta mới có thể dễ dàng nhớ nó được. Ta phải lưu ý điều này: Khi trang bị kiến thức, ta không thể ồ ạt ôm tất cả mọi thứ, mà phải ôn từng phần một. Với tính chất rời rạc của Tin học, ta không có tính chất liên tục như giải tích hay hình học. Vì thế, giáo viên phải cho học sinh, sinh viên thấy được rằng, dù trang bị cho từng mảng nhỏ đó, khi kết hợp lại, ta nhận được kết quả có tính liên tục, hài hoà với nhau.

“Các bạn nhìn vào tấm ảnh này, nhìn liên tục 20 giây.

Sau đó (không chớp mắt) nhìn lên tường. Nếu không thấy gì, hãy chớp một lần.

Bạn tìm thấy điều gì đặc biệt?”

Chăm chú nhìn vào chấm đỏ hình bên trái hay 4 dấu chấm giữa hình bên phải 20 giây sau đó nhìn lên tường. Nếu chưa thấy gì – chớp mắt một lần.

Nhà trường trang bị từng mảng kiến thức nhỏ, và các mảng ấy có vẻ rời rạc, không dính dáng gì với nhau. Tuy nhiên, kết quả của toàn bộ quá trình ấy sẽ tự động tái cấu trúc trong đầu chúng ta, tạo một mảng kiến thức hoàn chỉnh như một phương trình giải tích liên tục. Đó là cái mà học sinh và sinh viên cần phải quán triệt được, để có câu trả lời mỗi khi tự vấn sự “nhảy cóc” liên tục tới các mảng khác nhau.

Ban đầu, bức tranh này đơn giản, sẽ nhanh chóng tạo được hình, nhưng cũng nhanh chóng mất đi. Nếu ta trang bị sâu hơn, học sâu và nhiều hơn, chi tiết sẽ đọng lại lâu và chắc. Xác định tư tưởng ban đầu là cực kỳ quan trọng, để tránh sự chán nản tức thì, hay cố ý bỏ qua một số phần. Như trong hình ảnh phía trên, chỉ cần bỏ qua một vài vết đen, ta sẽ không nhìn thấy được bức tranh đấy nữa.

Tin học là ngành khoa học định lượng, cái gì cũng cần chỉ ra cách làm việc, không chỉ đơn thuần là lý thuyết.

Ta có công thức S = vt (Đường đi bằng tốc độ nhân thời gian) mà học sinh lớp 7 ai cũng đã từng học qua. Khi xem bắn pháo hoa mùng 2 tháng 9, thì họ có xác định được nó nổ cách mặt đất bao nhiêu mét không?

“Bạn có biết được pháo hoa tầm cao nổ cách mặt đất bao nhiêu mét không?

D..Dạ em không biết ạ. Em đoán chắc là tầm 150m ạ.”

Ánh sáng ta nhìn thấy ngay lập tức, nhưng âm thanh phải cần một khoảng thời gian chờ. Thành ra khoảng cách có thể tính bằng khoảng thời gian giữa việc ta nhìn thấy và nghe thấy nhân với tốc độ âm thanh. Nhưng mà phải làm thế nào để vừa xem pháo hoa, vừa tính được thời gian? Không phải ai cũng có đồng hồ bấm giờ!

Tin học sẽ chỉ cho người ta phương pháp, các cách làm việc để đạt được mục đích: Một trong số các quy tắc là như này: Khi ta nói “Mississippi”, thời gian sẽ trôi qua một giây. Giả sử ta nói được hai lần như thế, và đến lần thứ ba ta nghe thấy tiếng nổ. Thế là ta có thể tự suy ra được khoảng thời gian xấp xỉ 2.33 giây, và tính được độ cao ở mức xấp xỉ 750m. Điều này hoàn toàn phù hợp với lý thuyết pháo hoa tầm cao (nổ từ độ cao 100m đến 800m).

Tin học không phải là chỉ áp dụng công thức S = vt. Nó đặt ra câu hỏi: làm thế nào để có được t, và từ đó làm thế nào để tính được khoảng cách. Khác với Vật Lý – sử dụng công thức và những con số cho sẵn, người làm Tin học cần chỉ ra cách có được con số đó, và đó là cái mà người ta cần ở Tin học - những con số hoàn toàn cụ thể.

Công thức S = vt là công thức vật lý rất phổ cập, và ta sẽ gặp nó rất nhiều lần, không ở dạng này thì cũng ở dạng khác. Nếu như lúc nào tôi cũng nhắc S = vt, học sinh sinh viên sẽ rất chán, chả nhớ gì cả. Nhưng nếu họ bí một bài tập nào đó, thì một lần gợi ý “Có nhớ chuyện bắn pháo hoa không?” sẽ là chìa khóa cực kỳ hữu hiệu. Cần phải gợi cho họ hình ảnh gì đó. Nếu mình chỉ hỏi: hãy cho tôi biết hai câu đầu tiên trong bài hát nổi tiếng nhất của Văn Cao, thì rất ít người liên tưởng được. Chỉ khi tiếng nhạc vang lên, họ mới có thể nhớ được những lời ca đến từ bài Trường Ca Sông Lô.

Tin học được ứng dụng rộng rãi, và nó có chỗ để phát triển trong mọi lĩnh vực. Nếu như có Tin học, ta sẽ có được cách nhìn, cách đánh giá sâu sắc hơn.

“Bạn có nhớ bài Thu Điếu của Nguyễn Khuyến không?”

Bài thơ hồi tưởng lại phong cảnh làng quê nước ta thời kì phong kiến. Nhưng nó còn một cái hay khác nữa làm bài thơ rất hấp dẫn: ( Nguyễn Khuyến dùng vần “eo” vốn rất khó gieo vần, bài thơ hay về mặt hình ảnh, nhưng còn hay về mặt nghệ thuật nữa.Khi bạn muốn làm một bài thơ gì đó và lên AI tìm từ gieo vần, bạn sẽ thấy vần “eo” có số lượng ít hơn hẳn các vần khác.

Tin học có thể hỗ trợ ta trong lĩnh vực này. Mỗi khi bí từ, ta có thể sử dụng Tin học để tìm kiếm vốn từ mới, từ đó có thể chọn được từ thích hợp cho bài thơ của mình.Tin học không chỉ phục vụ cho tính toán, mà nó còn được ứng dụng trong rất nhiều lĩnh vực, kể cả thơ ca.

Cái gì cũng có cái đẹp của nó, và giáo viên cần phải cho học sinh thấy được cái đẹp đó.

“Các bạn có đọc truyện cổ Andersen không?”

Trong đó, đặc trưng các câu chuyện Andersen quán triệt rất rõ sự trân trọng cái đẹp, cái tốt, để có thể động viên, làm động lực phát triển cho người đọc đi lên, không nhìn vào mặt tiêu cực. Nếu ta chịu khó nhìn vào mặt tích cực, cái gì cũng có ưu điểm cả. Vì thế ta cần định hướng học sinh tìm hiểu, nhìn vào ưu điểm của nó.

Trong câu chuyện về chim hoạ mi của Andersen, tác giả đã ca ngợi vẻ đẹp của nghĩa địa (!). Nghĩa địa đương nhiên là chẳng có gì, nhưng Andersen đã thuyết phục người đọc nhìn vào cái đẹp của nó: “Chim họa mi hót ca ngợi vẻ đẹp bình yên của nghĩa địa, nơi có những hàng phong cao vút đứng cúi đầu lặng lẽ, nơi ngào ngạt hương thơm của các khóm hoa hồng bạch với thảm cỏ xanh mướt mềm mại như nhung và đẫm lệ người đời”

Khi tiếp cận hình ảnh nghĩa địa theo hướng khác, ngay cả thần chết cũng bị chinh phục bởi vẻ đẹp tích cực của nó và không cầm lòng phải quay về ngay. Sự lạc quan đã đuổi thần chết đi, và nhà vua khoẻ mạnh trở lại.

Làm sao để học sinh thấy ưu điểm, không chỉ nói một lần, mà phải lặp lại thật nhiều lần. Trên cơ sở đó, ta có thể cung cấp cho học sinh rất nhiều kiến thức khác nhau mà không thể dạy ở bên ngoài được – cực kì đa dạng, và ra khỏi phạm vi nhà trường.

“Các bạn hãy đọc một số đề bài sau”

PIRAMID.CPP

Một mặt, ta dạy cho học sinh sinh viên khai thác các công cụ để lập trình một cách nhanh chóng. Mặt khác, ta còn phải trang bị được những kiến thức xã hội mà không lúc nào khác có thể thêm vào được – nếu dạy trong những dịp khác thì nó sẽ trở thành dạy dỗ người khác. Phải để học sinh, sinh viên tự cảm nhận lấy:

• Quảng cáo là thành tố không thiếu được trong cuộc sống, nhưng không phải mọi quảng cáo đều định hướng tới lợi ích của xã hội

• “Bán cát cho người Ả Rập, bán tủ lạnh cho người Eskimo”. Những thứ mà người ta chẳng cần đến nhưng quảng cáo vẫn khuyến khích mua như lẽ đương nhiên.

Ta không thể dạy học sinh những thứ đấy được, phải để các em tự thấm dần qua thời gian. Đề thì có vẻ rất dài, nhưng bài code khá ngắn, tạo hứng thú cho các bạn học sinh hơn. Kiến thức thu được không nằm ở map hay set, mà là ở kiến thức thực tế liên quan tới quảng cáo, người Ả Rập và người Eskimo.

Cái này là nền tảng thấm vào một cách tự nhiên. Sau này có thể các bạn sẽ quên, nhưng một khi được hỏi “định bán cát cho người Ả Rập đấy à?” thì lại nhớ liền. (cười).

BLURB.CPP

Bài này mục đích chính nhắc về bảo vệ môi trường, và sau đó là những biến đổi toán học khá khó chịu, nhắc nhở rằng không phải bài nào cũng dễ chịu.

Toán và Tin đi liền với nhau. Ta không phủ nhận vai trò của toán học. Ta bắt buộc phải dẫn xuất công thức có vẻ rất đơn giản này, bởi vì tính từng bước một sẽ mất rất nhiều thời gian. Sử dụng toán học, ta có thể đạt được độ phức tạp O(1). Giá trị của việc biến đổi toán học rất quan trọng. Và thông qua những bài như thế này, ta nhấn mạnh việc không được coi thường môn này hơn môn khác, cũng như đâu đó là thông điệp về bảo vệ môi trường.

Số lượng và Chất lượng có mối quan hệ rất chặt chẽ. Khi số lượng thay đổi, thì chất lượng sẽ thay đổi – cái mà người ta hay nói là quy luật lượng-chất (triết học Marx – Lenin), số lượng thay đổi đến một mức nào đó sẽ mang lại thay đổi về chất lượng: Những giá trị như n <= 10^9 hay t <= 10^5 sẽ cho ra kết quả chạy tới hơn 10^27!

Giả sử như tôi đưa bài này trước năm 2021, bài sẽ mở ra nhiều vấn đề mới trong xử lý cộng, nhân và thậm chí là chia số lớn. Người học sẽ được tiếp cận với các công cụ mới hơn, như trong trường hợp này là số nguyên 128 bit, được đưa vào C++ từ Codeblocks 21 trở đi. Nếu như ta nắm được công cụ tốt thì mọi chuyện sẽ đơn giản hơn rất nhiều. Chi phí chất xám để nắm vững công cụ sẽ hiệu quả hơn nhiều so với cái ta bỏ ra để làm từng công việc một, và công việc này có thể gặp rất nhiều lần.

Chìa khoá để hướng tới tương lai là học những khả năng mới của công cụ, và giáo viên phải cho học sinh thấy được cái lợi của điều ấy. Ta có ca ngợi tới bao nhiêu đi nữa nhưng không có ví dụ thực tiễn, thì hiệu quả sẽ không cao. Ta phải đầu tư rất nhiều về nội dung của đầu bài, định hướng của bi tập: bao gồm kiến thức xã hội, bồi dưỡng con người và kiến thức liên quan đến công cụ cụ thể.

Tôi nghĩ rằng Tin học không đến độ quá khó, nhưng điều mọi người hay làm khiến cho Tin học trở nên khó hơn, mất đi tính hấp dẫn, đó chính là mọi người thúc đẩy quá trình lên quá nhanh. Như người xưa hay nói “Trăng đến rằm thì tròn”, không thể thúc học sinh làm bài tập khó, những vấn đề rắc rối. Ta cần hướng dẫn tư duy giải thuật, quen với cách triển khai, đón nhận giải thuật. Đi từng bước, từng bước một. Dần dần, học sinh sẽ trưởng thành hơn.

Những điều thầy chia sẻ cho các bạn học sinh, và đặc biệt cho các thầy cô, thật sự đáng trân quý. Em mong rằng tinh thần của thầy, câu chuyện của thầy sẽ truyền cảm hứng cho những thế hệ học sinh, giáo viên mãi về sau.

Chúng em xin cảm ơn thầy vì những chia sẻ cho số báo lần này!

Giới thiệu

Nhân vật khách mời đầu tiên của Tạp chí VNOI số lần này là bạn trẻ vô cùng nổi tiếng trong cộng đồng thời gian qua. Vốn là một học sinh Chuyên Toán từ trường Phổ thông Năng khiếu, nhưng vô tình bén duyên với môn Tin và gặt hái được nhiều thành công, với gần đây nhất là rank 32 tại ICPC World Finals 2025, là một trong những đội thi Việt Nam có phong độ tốt nhất tại kỳ thi cũng như trong lịch sử của trường Đại học Khoa học tự nhiên, ĐHQG-HCM. Đằng sau thành công đó là những câu chuyện chưa được kể, hôm nay hãy cũng chúng mình khám phá những câu chuyện đó với bạn Lê Nguyễn Hữu An!

Phỏng vấn

Ngày hôm nay, chúng ta sẽ cùng trò chuyện cùng anh Lê Nguyễn Hữu An thuộc team HCMUS-Atcoder, đội tuyển đã có thành tích tốt nhất trong lịch sử trường Đại học Khoa học Tự nhiên, ĐHQG-HCM tại đấu trường ICPC World Finals!

Handle anh rất thường dùng trên các Online Judge là Pannda, có vẻ là từ tên tiếng Anh của gấu trúc. Vậy tại sao lại là gấu trúc?

Từ lần đầu tiên lúc anh online là hồi tầm lớp 6, là anh lên Discord thì anh không muốn đặt tên thật của anh nên anh để tên là “Ann” (2 chữ “n”). Thì lúc đó ở cái Discord có 1 hội Guildplay (chơi game theo nhóm) là hội của những con gấu, thì anh là con panda (cười). Cuối cùng thì mới có cái tên Pannda như vậy.

Cơ duyên nào khiến anh biết đến lập trình thi đấu? Động lực của anh để bắt đầu với bộ môn này là gì?

Trước khi vào cấp 3, thì anh theo đuổi bộ môn Toán, nên gần như là không biết về Tin học luôn. Đầu năm lớp 10 thì trường mở thi chọn Đội dự tuyển Học sinh giỏi, thì lúc đó anh quyết định chọn môn Tin mà không chọn môn Toán, thì cũng một phần là do anh nhận tư vấn từ anh trai. Với lại có khi anh cũng cảm thấy tự ti với cái khả năng Số học của mình nên anh thi môn Tin. Lúc thi dự tuyển thì anh rớt, nhưng lúc sau thì anh cố vào học, cố xin để được học ấy, thì anh vẫn được học chung.

Lúc mới tiếp cận môn Tin thì anh gần như là không đặt kỳ vọng gì hết, cho nên anh thấy việc được đọ sức với các bạn là một nguồn động lực rất là lớn. Cảm nhận của anh thì tới bây giờ cái điều đó vẫn đúng với anh, tức là cái việc đọ sức á. Trong quá trình ôn Học sinh giỏi Quốc gia và ICPC thì anh thấy khi mà có 2 người làm chung 1 bài, cứ đọ nhau rồi nghĩ rồi “moi” cách làm của nhau để tiếp thu. Còn trước khi thi dự tuyển, để chuẩn bị cho dự tuyển thì anh còn được giới thiệu đến Codeforces, thì từ đó anh “marry” (sử dụng thường xuyên) cái trang này luôn. Anh ngồi giải bài và tầm hơn nửa năm anh làm Codeforces thì chỉ có làm bài và làm bài thôi chứ anh không có tham gia thi, tại anh sợ.

Anh đã bao giờ tưởng tượng nếu không theo đuổi Lập trình thi đấu thì anh nghĩ sự nghiệp học tập của anh sẽ trông như thế nào không?

Thì đây là câu hỏi giả thiết nên anh cũng thấy nó hơi… khó trả lời. Nhưng ít nhất thì anh thấy nó khác nhau cũng khá nhiều. Tại vì thời gian anh dành cho Lập trình thi đấu nhiều, nên nếu không theo đuổi từ đầu thì có rất nhiều thứ có thể xảy ra. Mà anh nghĩ dù có CP hay không thì anh cũng đi theo cái khuynh hướng cá nhân vốn có của mình. Với lại nếu như không có CP thì anh nghĩ những cái kỹ năng tư duy thuật toán với lại cái cách xử lý trong môi trường nghiêm ngặt và tốc độ cao của mình, thì anh nghĩ là không biết bây giờ anh có đạt được không. Hơn nữa là CP có một cái hệ thống cộng đồng rất là rộng và dày, nên là do CP thì anh mới may mắn được biết tới và góp mặt trong buổi phỏng vấn này.

Theo em được biết thì anh có xuất phát điểm hồi cấp 3 là học sinh Chuyên Toán trường Phổ thông Năng Khiếu. Anh cảm thấy nền tảng Chuyên Toán có giúp anh nhiều trong chặng đường theo đổi Học sinh giỏi Quốc gia/Quốc tế hay kì thi ICPC sau này không và nó giúp anh như thế nào?

Thật ra thì anh chuyển hướng sang Tin từ đầu cấp 3 rồi, nên là anh cũng không lên lớp (chính khóa) nhiều, vì vậy cũng không thể nói mình thừa hưởng trọn vẹn cái nền tảng Chuyên Toán ở Phổ Thông Năng Khiếu được. Nên là nền tảng Toán của anh chủ yếu là được hình thành ở cấp 2 đến đầu cấp 3 thôi. Nhiều người hay nhầm anh với cựu Chuyên Tin, anh thấy cũng khá đúng (cười). Với như nãy anh có nói, trước đó anh cũng không tự tin về mặt số trị cho lắm, anh nghĩ có cái điểm mạnh về tổ hợp và hình học thì cũng để dựa dẫm vào 2 điểm mạnh đó để thi Học sinh giỏi Toán hồi cấp 2 và Tuyển sinh 10. Thì khi qua CP anh thấy những mảng đó cũng liên quan và anh trở nên mạnh ở Cấu trúc dữ liệu với Đồ thị. Còn ngoài kiến thức cứng trong Toán thì trong trải nghiệm của anh thì thấy ít nhiều thì sau này cũng có cơ hội nào đó để áp dụng mà, ví dụ như đại số, tổ hợp, hay tích phân,... thì có thể thấy trong những bài CP sẽ áp dụng được nhiều. Để nói về một cái trải nghiệm cụ thể thì, có lần anh tìm hiểu về Decision Tree (là toán, game và tổ hợp ấy) thì sẽ phải tìm hiểu về Minimax thì anh học tầm cuối lớp 10. Một năm rưỡi sau thì nó lại có trong Siêu cúp, anh nhớ lại và anh giải được bài. Thật ra kiến thức đấy cũng không Toán lắm. Anh thấy dấu ấn quan trọng nhất của môn Toán là nó rèn cho anh cái kỹ năng tư duy trừu tượng, một cái kỹ năng mà anh nghĩ là sẽ luôn cần tới trong cái con đường học thuật của anh. Trong CP thì nếu không biết cách tư duy trừu tượng thì cũng sẽ không biết cách mô hình hóa các bài toán để giải.

Trong năm học 2024-2025 thì anh An vừa có năm học đầu tiên ở đại học, nhưng đã có thể đại diện trường tham dự ICPC World Finals – một điều không nhiều người có thể làm được. Cảm nghĩ của anh về việc tham dự một kì World Finals khi còn là sinh viên năm nhất là như thế nào?

Thứ nhất thì anh cảm thấy vinh dự khi được tham gia ICPC World Finals từ năm nhất, với lại anh thấy tự hào với team, bởi ngày từ đầu lúc thành lập team là bọn anh đã xác định mục tiêu là muốn tham gia World Finals rồi. Một phần cũng là do hai anh teammates năm trước (Vũ Quốc Lâm và Võ Khắc Triệu) đã thể hiện tương đối tốt ở vòng Asia Championship. Do xác định mục tiêu từ sớm vậy nên tụi anh có nhiều thời gian để làm việc và lên kế hoạch cá nhân. Với anh cũng thấy vui vì ở kỳ ICPC này anh có rất nhiều trải nghiệm mới, lớn nhất là lần đầu tiên anh được làm việc trong 1 team mà quản lý con người sâu sắc đến vậy. Anh thấy rất là thỏa mãn. Với anh được trải nghiệm văn hóa dân tộc và đất nước ở nhiều nơi trên thế giới, nó khác nhau về mặt hoạt động và tinh thần họ hướng tới. Ví dụ như ở Jakarta đi, thì anh thấy họ cử cho mỗi đội là 1 tình nguyện viên để hướng dẫn từ đầu đến cuối luôn, họ cũng rất là hiếu khách. Còn ở Singapore chẳng hạn, thì BTC họ cho mình tự do và độc lập hơn.

Năm đầu anh tham gia ICPC nên anh thấy anh chưa có quá nhiều kiến thức, cụ thể là mấy kiến thức mới ở ICPC anh chưa kịp làm quen. Anh rất biết ơn các anh trong team AtCoder vì đã hướng dẫn anh và cũng như là đã có chung đam mê và tham vọng để đi xa cùng với anh như này. Tấn Minh: Anh có gặp khó khăn gì trong việc vừa thích nghi môi trường học tập mới trên đại học, vừa thực hiện lịch luyện tập nghiêm ngặt của một đội ICPC đặt mục tiêu cao không?

Khó khăn thì anh nghĩ cũng không có nhiều, vì từ khi vào đại học thì anh tin vào sức mạnh của kỷ luật, anh nghĩ điều này giúp ích rất là lớn cho việc điều hòa giữa bài tập trên trường với lại ICPC. Nhưng mà có những giai đoạn, đặc biệt là lúc thi World Finals thì anh cũng bị quá tải một tí. Anh đã phải cắt một vài buổi training nên anh cũng hơi tiếc là chất lượng training không được hoàn chỉnh cho lắm.

Team của anh thì train vào các ngày Thứ 7, Chủ Nhật nên là nhiều cơ hội, hoạt động ngoại khóa anh cũng không tham gia được. Nói chung là anh cũng tham, muốn có nhiều thứ mà anh không ôm được hết, nhưng mà anh nghĩ đây là một phần của công bằng thôi.

Anh có thể mô tả vai trò của anh trong team HCMUS-AtCoder kể cả trong và ngoài lúc thi đấu không?

Trong contest thì team gồm 3 thành viên, 3 thành viên đều có xuất thân thi OI (Olympiad in Informatics) hết cho nên những bài dễ thì ai cũng có thể độc lập làm được. Còn về chuyên môn thì tụi anh chia như này: anh đảm nhiệm Cấu trúc dữ liệu và Đồ thị; anh Triệu làm các bài toán Số và Toán; anh Lâm thì làm Hình học, DP (Quy hoạch động) với mấy bài tối ưu hóa. Thì việc chia như này anh nghĩ là 1 chiến lược cho các team tham gia thi ICPC.

Còn ngoài contest thì anh nghĩ có nhiều cái đáng nói hơn như là cách vận hành của team, cách team rút kinh nghiệm và tổ chức các buổi training nội bộ, team cũng thường xuyên họp mặt để đốc thúc nhau, trao đổi và góp ý về những vấn đề thiếu sót của nhau, cũng như bàn về kế hoạch training sắp tới. Anh cũng giống như hai thành viên còn lại là luôn tích cực xác định vấn đề tồn đọng của team để khắc phục và đưa ra một hướng đi chung. Với có vẻ là từ lúc vào team thì anh cũng “du nhập” một vài thứ vào team, hai anh teammate kia cũng theo style code của anh luôn.

Style code mà anh du nhập vào là trông như thế nào nhỉ?

Là kiểu “bớt CP” hơn ấy. Tại vì khi thi team như vậy thì hiểu code nhau là một điều rất quan trọng nên phải thống nhất một style code. Style code của anh thì anh chia từng module ra rất là phân biệt, gần như module này không liên quan tới module kia luôn. Mặc dù cách code sẽ dài hơn một xíu… à không dài hơn rất là nhiều luôn (cười), nhưng anh nghĩ như vậy thì thành viên có thể quản lý đọc code của nhau dễ hơn.

Cái style đó là anh có ở đại học hay từ khi nào?

Từ hồi cấp 3 anh đã code như vậy rồi.

Theo quan sát của em qua các kì thi có ghi hình như ICPC World Finals hay VNOI Cup thì anh An có vẻ là một người rất điềm tĩnh khi thi đấu, đặc biệt là em chưa thấy anh ăn mừng một cái “AC” nào. Những lúc đối mặt với áp lực thi đấu (còn ít thời gian, cần vượt qua 1 bài tập rất khó để vượt lên,...), anh thường suy nghĩ gì để giữ được cái đầu lạnh như vậy?

Ờm… thứ nhất thì anh không biết ghi hình của anh trông như thế nào nhưng theo anh thấy bản thân anh không có bình tĩnh lắm đâu (cười). Đúng là bình thường anh cũng hay đi qua đi lại với hơi bồn chồn trong lúc thi ấy. Nhưng có một cái anh thấy là anh không có lo lắng ở mấy cái kỳ thi CP, anh nghĩ là do anh thấy một phần là CP vui, phần khác là anh cần tập trung để nghĩ bài, nên cũng không có tâm trí nghĩ ngợi hay lo lắng điều gì khác.

Cái việc mà anh không có ăn mừng á, anh nghĩ cái đó là do kế hoạch của team đã như vậy rồi, kế hoạch là phải AC bài này trong thời gian này nên anh cũng không có tưng bừng lắm. Nhiều lúc thì anh bug, hoặc là bí một bài thì anh cũng có hơi cay, vì vậy là đầu anh cũng có hơi nóng một tí. Với mấy cái bài mà rối thì anh sẽ đóng băng luôn. Anh nghĩ team anh cũng nhận diện được anh bị như vậy cho nên cũng có ghi trong chiến lược, ghi rõ là trong những tình huống đó thì anh phải giữ được cái đầu lạnh. Nếu cần thì teammate nhắc nhau luôn, cũng vì vậy nên anh có thể kiểm soát bản thân và bình tĩnh lại được. Một số lúc như vậy thì teammate vào hỗ trợ giải bài cùng anh luôn, hoặc anh đổi bài khác để khởi động lại đầu óc, cần thiết thì ra bên ngoài nghỉ ngơi và đi vệ sinh.

Ngoài ra việc không ăn mừng cũng có 1 phần lý do là càng về cuối thì ta càng dễ tập trung hơn, do lúc đó ta đã xác định được các bài cụ thể cần phải giải quyết. Còn khoảng giữa giờ thì mình có nhiều bài để đắn đo, để đưa ra quyết định. Trong các contest mà tụi anh trải qua thì phần lớn tầm 4 tiếng cuối là tụi anh đã có được cái kịch bản rồi. Thì cứ theo vậy mà làm.

Ví dụ như ở Asia Pacific Championship đi, thật ra cuối giờ tụi anh có nguy cơ rớt World Finals rồi. Thì 1 tiếng cuối, theo kế hoạch là tụi anh tách người ra giải 2 bài, đến 30 phút cuối mà vẫn không được thì tụi anh hợp lại làm 1 bài. Cuối cùng tụi anh chả giải thêm bài nào hết (nhưng vẫn đi World Finals). Một phần anh nghĩ là do team đã có kế hoạch như vậy rồi nên khi mà thấy cận kề rớt World Finals thì team anh vẫn giữ được bình tĩnh và tuân theo kế hoạch, ít nhất là trước khi contest kết thúc. Nên anh nghĩ là có kế hoạch thì tâm lý sẽ dễ tập trung hơn dưới áp lực thi đấu.

Anh nghĩ đâu là mấu chốt giúp HCMUS-AtCoder trở thành đội tuyển có thành tích tốt nhất tại đấu trường ICPC World Finals cũng như sự thành công tại các kì thi khác?

Anh nghĩ cái mấu chốt của team anh là hiểu được sự tương tác và gắn kết của team mình, cái “chemistry” (sự gắn kết) á. Từ đó tụi anh làm việc hay đưa ra chiến thuật cũng xoay quanh cái hiểu biết đó. Cả team đều có chung một nhận định là mỗi thành viên trong team làm việc riêng lẻ thì khá là yếu. Điều này có thể thấy được trong một vài kỳ thi mà tụi anh đã làm, nếu cứ cái phong độ đó thì cá nhân từng người tụi anh sẽ không thể thể hiện được các thành tích cao như vậy được. Nhưng mỗi người đều chuyên sâu một mảng, và cái sự bao phủ đó lại rộng ra cho nên lúc hiểu được vai trò của các thành viên vậy thì thứ nhất là biết ai sẽ làm bài nào là tốt nhất; thứ hai là lúc làm mà mình có kỹ thuật gì cần biết thêm, thì mình sẽ biết nhờ ai, hay nếu bí bài thì biết ai sẽ có hướng khả thi.

Sau khi làm việc nhóm một thời gian thì tụi anh hiểu rõ cái “chemistry” này hơn, cụ thể thì hiểu cái cách thức của mỗi người nghĩ, như cái hệ điều hành ấy. Từ đó định hình được cách giao tiếp phù hợp, ví dụ như anh thì anh sẽ không theo kịp được những hết những ý tưởng của các anh khác nói, cho nên nếu như mấy anh khác có giải thích đề bài/hướng làm thì các anh sẽ cố tóm tắt cho anh thôi. Cụ thể đi sâu chi tiết như nào thì tính sau. Ngược lại thì anh Triệu thường muốn nghe giải thích một cách rất là đầy đủ, kiểu toán học cụ thể. Anh Lâm lúc đọc đề thì muốn được đề gạch chân sẵn để đọc tiện hơn, nên tụi anh cũng biết trước lúc đọc đề trước thì gạch chân cho ảnh. Nói chung là khi mọi người hiểu cách mỗi người nghĩ thì cách thức giao tiếp sẽ hiệu quả hơn. Với lại như vậy cũng sẽ hiểu được các điểm yếu của nhau, ví dụ như khi anh cài rối quá thì anh sẽ chết luôn, còn anh Lâm thì hay ra ý tưởng rất là táo bạo, thường thì đúng nhưng cũng có lúc ngộ nhận (cười). Các điểm yếu của team thì tụi anh cũng cố tìm cách giải quyết bằng cách họp lại với nhau để nghĩ chiến lược.

Anh nghĩ một lý do mà team anh thường hay bị “nổ” là do bị bug giai đoạn đầu, khi mà bug như vậy thì coi như contest đó “nổ”, coi như chết tới cuối giờ. Để giải quyết việc này thì tụi anh record lại buổi training của tụi anh luôn. Sau này sẽ quan sát lại thì nhận diện được những cái lỗi, tụi anh sẽ phải xác định những cái nguyên nhân gốc và nghĩ cách sửa chữa. Anh nghĩ cái quá trình luân hồi feedback và khắc phục như này sẽ giúp cho tụi anh thấy là tụi anh dần cải thiện được rõ rệt luôn. Ngoài cái đó còn nhiều yếu tố khác nữa, ví dụ như là chí hướng tham vọng từ sớm, rồi tụi anh cũng tự tìm hiểu các nơi để train, các trại training, có cơ sở để biết mặt bằng đối thủ đề mà đặt mục tiêu cho phù hợp.

Trước khi bắt đầu hành trình rất ngoạn mục cùng HCMUS-AtCoder thì ở cấp 3 anh cũng từng là một thành viên của đội tuyển trường Phổ thông Năng Khiếu và sau này là đội tuyển quốc gia. Sự khác biệt lớn nhất mà anh nhận thấy giữa việc thi đấu cá nhân hồi cấp 3 và quá trình tham gia ICPC cùng đồng đội là gì?

Về mặt hình thức thi thì anh thấy ICPC và OI rất là khác nhau. OI thì gồm 3 bài và từ 3 đến 5 tiếng. Mỗi bài thì mất rất lâu để nghĩ và gần như cần phải thiên về một bài để làm luôn. Nên anh nghĩ nó yêu cầu cao về khả năng nghĩ sâu của thí sinh. Lúc anh thi và train thì anh thấy bài tập OI rất là hay luôn, nó luôn có cái gì đó mở mang cho mình. Còn đối với ICPC thì nó lại yêu cầu độ rộng kiến thức, cái khả năng áp dụng được kiến thức đó với lại cách phân bổ công việc hiệu quả trong môi trường teamwork như vậy. Về mặt cảm nhận thì anh thấy có một điểm lớn là trong OI anh phải tự làm mọi thứ, tất nhiên thì vẫn có thể thiên về một cái mảng nào đó nhưng để làm tốt nhất một cái đề OI thì mình phải biết nhiều về các dạng và hiểu sâu. Còn ở ICPC thì tụi anh có thêm một cái “quyền” được dựa dẫm nhau. Mỗi người chuyên sâu một mảng thì hiệu suất sẽ cao hơn và cái workload của mỗi người nó sẽ vừa phải. Cũng do vậy nên anh thấy quá trình luyện tập của anh năng động hơn. Một mùa thi ICPC dài 1 năm như vậy nên là cái khoảng thời gian làm việc cũng khá dài, tụi anh có được sự ăn ý của nhau thì nó cũng hình thành một cái văn hóa trong team. Nói chung là anh thấy ICPC năng động hơn OI nhiều.

Nếu anh được chọn một trong hai cái đó để theo đuổi lâu dài luôn thì anh nghĩ là anh sẽ chọn cái nào?

Chắc chắn là ICPC (cười).

Anh An là một người rất chú trọng trong việc giữ gìn sức khỏe, đặc biệt là việc đi tập gym. Không biết là trong những lần anh phải dốc sức cho những kì thi quan trọng như VOI, TST, APIO, APAC, ICPC World Finals,... thì anh đã duy trì việc rèn luyện sức khỏe như thế nào?

Thứ nhất thì anh thấy CP-er đi tập gym cũng nhiều, thấy xung quanh toàn tập gym (cười). Với lại anh theo một cái triết lý rằng sức khỏe là quan trọng nhất, tại vì tương lai mình còn làm nhiều thứ, ít nhất là mình phải bảo quản và bồi dưỡng cái cơ thể này. Với anh muốn đính chính là anh chỉ tập calisthenics chứ anh không tập gym, tại vì anh thấy nó tiện hơn với lịch trình cá nhân của mình. Với lại mục đích các nhân của anh thì cũng không phải là bodybuilding, mà chỉ là để cảm nhận cơ thể mình khỏe hơn thôi.

Lần đầu anh bắt đầu tập calis thì chắc tầm giữa năm 2023. Trong năm đó thì cũng lên VOI xuống chó, cũng không duy trì đều đặn lắm, nhưng hết năm đó thì anh tập được thói quen là duy trì tập mỗi tuần được ít nhất 2-3 buổi. Trừ khi anh phải xa nhà hoặc bị bệnh thì anh sẽ tập ít lại. Lúc ở quê thì anh thường hay chạy bộ vào buổi tối, tại vì anh thấy nó thoải mái cho tinh thần cho anh. Anh thấy cái việc tập nó có một cái giá trị trị liệu, cá nhân anh thì nếu như không tập, não bộ và thể trạng hoạt động không hiệu quả bằng như có tập. Anh muốn nhắn gửi đến mọi người nên duy trì thói quen tập thể thao, vì nó tốt cho mình về mọi mặt.

Việc tập calisthenics có giúp ích cho anh trong quá trình chinh phục các thành tích mà anh đã có không?

Anh thấy việc tập nó giúp ích hoàn toàn về mặt tâm lý của anh luôn á, nó cải thiện về cảm quan của mình, từ đó mà nó cải thiện cái chất lượng cuộc sống của mình luôn. Thì cái đó là cái lý do anh thấy quan trọng hơn, còn thi đấu thì chắc chắn là nếu nó giúp cho mình về tinh thần thì nó sẽ giúp ích về thi đấu rồi.

Anh với anh Lâm thì có một cái mê tín là trước khi thi một cuộc thi ICPC nào đó thì tụi anh sẽ hít đất, ngay tại phòng thi luôn. Ừ, Anh và anh Lâm sẽ hít đất tầm 30 cái, ở vị trí thi, ở Jakarta, ở Hà Nội, ở Singapore với ở Baku.

Thế anh Triệu ở đâu?

Triệu ngồi nhìn (cười). Triệu thật ra cũng hơi phản đối, sợ tụi anh mất sức. Anh thì thấy nó lại đẩy máu lên não hơn nên anh muốn làm. Tụi anh sẽ làm tầm 20 phút trước khi thi đấu.

Cuối cùng, anh có thể gửi một vài lời nhắn nhủ đến các bạn trẻ đang có mục tiêu và tham vọng lớn trên các đấu trường Lập trình thi đấu cấp Quốc gia và Quốc tế không?

Anh không dám chắc là anh có nhiều kinh nghiệm nhưng theo trải nghiệm của anh thì đối với các bạn thi ICPC hoặc có dự định thi ICPC, mình nghĩ là quan trọng nhất là cứ tìm hiểu cái sự ăn ý và gắn kết trong đội của mình, cứ vui vẻ trải nghiệm và từ đó anh tin là cái trải nghiệm đó sẽ tạo hình cái hành trình của team các bạn. Còn lại thì mình nghĩ nếu như có đam mê thì mình sẽ thực hiện được cái tham vọng đó của mình thôi. Anh gửi các bạn lời chúc may mắn.

Buổi phỏng vấn đến đây cũng kết thúc rồi. Thay mặt VNOI, em xin cảm ơn anh An đã nhận lời hợp tác với tụi em trong buổi phỏng vấn lần này. Hy vọng là sẽ được gặp lại anh An trong những lần tiếp theo!

Bạn cảm thấy lo sợ trong những kì thi chấm offline? Bạn bình thường làm bài rất tốt nhưng khi chấm offline lại bị điểm kém vì sai những lỗi vớ vẩn? Bạn code sai một bài rất khó và debug mãi không được vì không có test sai? Tất cả những vấn đề đó sẽ được giải quyết đơn giản với một chương trình chấm bài tự động, giúp bạn tự kiểm tra bài mình và phát hiện test sai. Bài viết này sẽ giới thiệu với bạn những bước cơ bản nhất để viết trình chấm - một kĩ thuật mà bạn nên thành thạo trước khi thi HSG: Viết trình chấm.

Đề thi HSGQG Tin học năm học 2024-2025 chứng kiến nhiều thí sinh sừng sỏ ngã ngựa bởi bài được đánh giá “dễ xơi" nhất đề. Bởi vì đề yêu cầu bắt đầu từ đỉnh 1, thí sinh cần đánh dấu (thông qua memset) các đỉnh khác để cho ra kết quả tối ưu như đề bài. Test mẫu của Bộ Giáo dục không bao gồm trường hợp này, cũng như do nhiều bạn đọc thiếu mất đi dữ kiện đó, dẫn đến việc các bạn không thể phát hiện ra được lỗi sai. Hãy đọc thật kĩ đề để không mất điểm trong kỳ VOI sắp tới nhé!

Tourist – Huyền thoại bất khả chiến bại của lập trình thi đấu

1. Giới thiệu về Tourist

Trong bài viết này, VNOI xin mời các bạn cùng tìm hiểu về Tourist – lập trình viên xuất sắc bậc nhất thế giới, biểu tượng của nền lập trình thi đấu toàn cầu. Tourist tên thật là Gennady Korotkevich, một thần đồng lập trình người Belarus. Anh sinh năm 1994 tại Gomel, Belarus. Sinh ra trong một gia đình có cả cha và mẹ đều làm trong lĩnh vực lập trình, Gennady Korotkevich sớm được tiếp xúc với máy tính và nuôi dưỡng niềm đam mê với thuật toán từ nhỏ. Anh theo học tại Đại học ITMO (Nga) từ năm 2012 đến 2018 và nhận bằng Thạc sĩ Khoa học Máy tính. Hiện nay, Tourist đang làm việc tại Devin, một công ty phần mềm được sáng lập bởi Scott Wu – một huyền thoại khác trong làng lập trình thi đấu hay còn được biết tới với biệt danh là cha đẻ của Devin AI.

Tourist bắt đầu nổi lên trong giới CP với khả năng tư duy vượt trội từ những năm mới 10 tuổi. Trong suốt tuổi thiếu niên, Gennady giành 7 huy chương vàng Olympic Tin học Quốc tế (IOI) và đặc biệt trong đó có Tourist đã giành huy chương vàng liên tục trong 6 năm - kỷ lục chưa từng có trong lịch sử. Dù nổi tiếng toàn cầu, Tourist vẫn giữ lối sống giản dị, tập trung vào đam mê giải thuật và không ngừng thử thách bản thân trong các cuộc thi lớn như Codeforces và AtCoder, nơi anh được xem là lập trình viên thi đấu vĩ đại mọi thời đại.

Có người từng bảo rằng: “nếu contest đấy tourist không vô địch, bởi vì tourist đã không tham gia” câu nói nửa đùa nửa thật ấy đã phản ánh đúng vị thế “bất khả chiến bại” của anh trong làng lập trình thi đấu. Từ năm 2007 đến 2012, anh đã lập kỷ lục 6 huy chương vàng liên tiếp tại Olympic Tin học Quốc tế (IOI), trong đó có 3 lần liên tục giành vị trí top 1 (theo nguồn CP HOF), trong đó năm 2011 anh vô địch với ngôn ngữ Pascal, một kỷ lục vô tiền khoáng hậu chưa ai từng thiết lập. Khi trở thành sinh viên của Đại học ITMO (Nga), anh tiếp tục gặt hái vinh quang với 2 chức vô địch thế giới ACM ICPC vào các năm 2013 và 2015 (đặc biệt vào năm 2015, team Tourist đã giải được 13/13 bài chỉ trong 5 tiếng thi đấu). Không dừng lại ở đó, Tourist còn thống trị hàng loạt sân chơi danh giá như Google Code Jam, Facebook Hacker Cup (Meta Hacker Cup), Topcoder Open và AtCoder Grand Contest. Đặc biệt, anh là người đầu tiên trong lịch sử Codeforces đạt rating trên 4000, một kỷ lục khiến cộng đồng ngưỡng mộ. Đến nay, dù đã chạm tới mọi đỉnh cao, Gennady vẫn tiếp tục thi đấu - không vì danh hiệu, mà vì niềm vui chinh phục và tình yêu với thuật toán.

2. Phân tích biểu đồ độ khó

Từ những thành tích siêu khủng trên, bhạn đọc đã bao giờ thắc mắc Gennady đã học và code những gì để điều đó không?

Biểu đồ trên thể hiện phổ độ khó của các bài tập mà Tourist đã giải, được phân loại theo mức điểm rating từ 800 đến 3500. Có thể thấy, anh không chỉ giải nhiều bài dễ – với hơn 190 bài ở mức 800 điểm – mà còn duy trì hiệu suất ấn tượng ở mọi cấp độ, đặc biệt là trong khoảng từ 1700 đến 2000 điểm, nơi số bài giải đạt đỉnh khoảng 140 bài. Thực tế, số lượng bài có độ khó trên 3000 mà Tourist giải không quá nhiều so với một số cao thủ khác trong top 10 Codeforces, chẳng hạn như jiangly – người đã giảm tới hơn 7000 bài và từng đạt mức rating 4000. Tuy nhiên, điểm nổi bật của Tourist không nằm ở số lượng, mà ở chất lượng cùng hiệu suất vượt trội trong mỗi lần tham gia thi đấu.

Điều đó thể hiện khả năng tư duy toàn diện, chiến lược tối ưu và sự ổn định đáng kinh ngạc của anh trong suốt nhiều năm chinh phục các thử thách thuật toán. Phổ điểm này phản ánh rõ phong cách đặc trưng của Tourist: ổn định, bao quát và không ngừng thử thách giới hạn của bản thân.

3. Chủ đề các bài Tourist đã giải

Tiếp theo đây, bài viết này sẽ cùng các bạn tìm hiểu về những dạng Tourist “hứng thú”.

Qua biểu đồ trên, chúng ta cũng có thể thấy rằng Tourist đã chinh phục gần 3000 bài trên Codeforces – một con số khổng lồ thể hiện sự bền bỉ và niềm đam mê mãnh liệt với lập trình thi đấu. Trong đó, các bài thuộc chủ đề Greedy và Math cũng chiếm nhiều nhất gần 25% mỗi dạng. Kết hợp với hàng trăm bài thuộc các mảng như Dynamic Programming, Implementation, Constructive Algorithms hay Graphs, thành tích này chứng minh rằng Tourist không chỉ là “vua giải thuật”, mà còn là biểu tượng toàn năng của giới competitive programming.

4. Những câu chuyện thú vị về Tourist

Bên cạnh những thành tích đáng nể, chúng ta cũng ghi nhận được nhiều sự thật thú vị về Tourist được cộng đồng mạng truyền nhau. Có ý kiến hài hước cho rằng: “Tourist đã sử dụng thuật toán FFT để nhân số từ khi còn học tiểu học” – một câu nói thể hiện rõ sự ngưỡng mộ lẫn khâm phục đối với tài năng và phong cách đặc biệt của anh. Một người khác cũng hài hước chia sẻ rằng: “Tourist không bao giờ cần gọi thợ sửa ống nước, anh chỉ cần chạy thuật toán luồng cực đại là xong” – một câu đùa nhưng đồng thời thể hiện sự am hiểu và thành thạo của anh trong lĩnh vực thuật toán. Cộng đồng mạng còn có vô số “huyền thoại” khác về Gennady Korotkevich như: “Tourist có thể sắp xếp nhị phân với một dãy chưa được sắp xếp” hay “Nếu Tourist nộp ra kết quả sai, thì chắc chắn người ra đề đã sai”. Tất cả những câu nói vui ấy không chỉ thể hiện sự ngưỡng mộ mà còn khẳng định vị thế huyền thoại của Tourist trong làng lập trình thi đấu.

5. Huyền thoại vẫn còn đang viết tiếp

Dù đã chinh phục mọi đỉnh cao mà dân CP có thể mơ tới, Tourist vẫn tiếp tục code. Mới đây, vào ngày 30/10, anh đã quay trở lại vị trí số 1 trên Codeforces, tiếp tục ‘AC’ như thể đó là hơi thở thường nhật. Có lẽ, chừng nào anh còn thi đấu, cộng đồng lập trình vẫn sẽ còn kể mãi những “truyền thuyết” về người đã biến mọi bài toán thành nghệ thuật – Gennady Korotkevich. Và VNOI hy vọng rằng, qua chuyên mục này, các bạn độc giả sẽ có thêm cảm hứng và kinh nghiệm để chinh phục các kỳ thi lớn trong tương lai.

🙌 Vòng chung kết VNOI CUP 2025 sẽ diễn ra vào tuần tới tại thủ đô Hà Nội, các bạn đã sẵn sàng chưa?

💕 Đối với bảng mở rộng, chúng mình đã gửi thông tin xác nhận đến email thí sinh đủ điều kiện tham dự! Các bạn hãy kiểm tra hòm thư và xác nhận tình trạng tham dự Bảng mở rộng - Vòng chung kết VNOI CUP 2025 để ghi danh mình ngay nhé.

🔥 Mọi thắc mắc về thủ tục, quy trình làm đơn, xin vui lòng liên hệ với fanpage VNOI để được giải quyết sớm nhất!

✨ Bảng mở rộng Chung kết VNOI CUP 2025

Bảng mở rộng sẽ được tổ chức song song với bảng thi của 24 thí sinh tham gia Chung kết chính thức tại trường THCS - THPT Newton. BTC sẽ cung cấp nước uống và đồ ăn nhẹ cho thí sinh trong quá trình thi.

🖊️ Thể lệ:

• Bảng thi đấu sẽ có tối đa 30 thí sinh tham dự.
• Tiêu chí lựa chọn: BTC sẽ ưu tiên thí sinh có thứ hạng cao nhất dựa trên tổng điểm của 2 vòng loại. Danh sách thí sinh được chọn sẽ được thông báo qua email.
• Chỉ có thí sinh TOP 3 tham gia bảng mở rộng sẽ được nhận giấy chứng nhận từ BTC.

⚠️ Lưu ý dành cho thí sinh:

• Thí sinh mang theo laptop cá nhân để làm bài thi.
• BTC KHÔNG thu phí đăng ký.
• Thí sinh tự chủ động chi phí di chuyển, ăn uống, lưu trú.

❤️ VNOI hẹn gặp các bạn tại Hà Nội 🚀

🎉 Hai vòng loại của VNOI CUP 2025 đã thành công tốt đẹp, đánh dấu một nửa chặng đường của cuộc hành trình VNOI CUP 2025 với điểm đến cuối cùng tại thủ đô Hà Nội! Qua 2 vòng thi, 150 thí sinh đủ điều kiện để nhận được chiếc áo VNOI CUP phiên bản mới nhất cũng đã được lộ diện 🙌 Và không để các bạn phải chờ đợi lâu nữa, ngay sau đây, BTC xin công bố danh sách các thí sinh đủ điều kiện nhận áo VNOI CUP 2025

📌 Để xác nhận thông tin, các bạn có tên trong danh sách trên vui lòng điền form trước 20h00’ ngày 30/06/2025. Sau thời gian này, những bạn chưa điền form xác nhận thông tin với BTC sẽ bị hủy phần thưởng.

⚠ Bằng việc điền form trên, bạn đã xác nhận tuân thủ đúng các quy định của cuộc thi bao gồm:

• Chỉ dùng 1 tài khoản VNOJ cho cả 2 vòng thi
• Có tên trong danh sách nhận áo
• Không tham gia trao đổi với thí sinh khác
• Đã xác thực thông tin cá nhân với BTC VNOI CUP

Nếu thí sinh vi phạm quy định, vui lòng không điền form. BTC sẽ kiểm tra lại kết quả thi của các bạn có tên trong danh sách trên trước khi tiến hành gửi áo. Việc điền form đồng nghĩa với việc chấp nhận mọi chế tài xử lý của BTC trong trường hợp vi phạm bao gồm những không giới hạn ở ban vĩnh viễn khỏi VNOI & VNOJ, công khai danh sách những bạn gian lận.

💖 BTC xin gửi lời cảm ơn chân thành tới sự quan tâm của các bạn dành cho VNOI CUP 2025! Nhờ có điều đó, chặng đường VNOI CUP 2025 mùa hè này ngày càng rực cháy hơn nữa cùng tinh thần nhiệt huyết của các bạn.

🔥 Chúng mình sẽ luôn cập nhật những thông tin mới nhất về kỳ thi trên trang page VNOI. Và cuối cùng, hãy cùng chờ đón vòng Chung kết VNOI CUP 2025, diễn ra tại Thủ đô Hà Nội trong thời gian sắp tới nhé!

🎊 Vậy là sau 360 phút thi đấu căng thẳng ở cả hai vòng thi vừa rồi, Vòng loại VNOI CUP 2025 cũng chính thức khép lại. Xin chúc mừng 10 bạn có tên sau đây đã xuất sắc giành quyền tham dự vòng Chung kết VNOI CUP 2025:

• 3 thí sinh dẫn đầu tại bảng xếp hạng vòng loại thứ nhất - LeKienThanh69, minhcool, neko_nyaaaaaaaaaaaaaaaaaaaaaaa.
• 4 thí sinh dẫn đầu tại bảng xếp hạng vòng loại thứ hai - huyhau6a2, BaoJiaoPisu, Pannda, toidaidot2.
• 3 thí sinh có xếp hạng cao nhất tại bảng tổng điểm 2 vòng loại - daoquanglinh2007, duongnc000, huutuan.

📌 Các thí sinh có tên trên vui lòng liên hệ cho page VNOI trước 23h59’, Chủ nhật, ngày 22/6/2025 để xác nhận tham dự vòng Chung kết.

🔍 Như đã thông báo, ngoài danh sách 10 thí sinh được chọn từ 2 vòng loại của cuộc thi, BTC sẽ bổ sung thêm tối đa 3 suất tham dự nhằm khuyến khích một số đối tượng có hoàn cảnh đặc biệt (căn cứ thứ hạng vòng loại). Bên cạnh đó, VNOI CUP 2025 mở rộng đăng ký tham dự chung kết cho Top 40 (chi tiết xem lại thể lệ VNOI CUP 2025 mục 4 và 5).

📃 Bảng tổng điểm 2 vòng loại VNOI CUP 2025

⚠️ Lưu ý: Bảng điểm phía trên chỉ bao gồm thông tin của TOP 60 thí sinh, về thứ hạng chi tiết của các thí sinh khác khi tham dự để tính rating và nhận phần thưởng từ BTC, các bạn có thể xem trực tiếp qua sheet ở tab r1_ranking (hoặc qua Kết quả Vòng loại thứ nhất) và r2_ranking (hoặc qua Kết quả Vòng loại thứ hai).

⚔️ Để đăng ký tham dự bảng chính thức Chung kết VNOI CUP 2025, các bạn trong Top 40 vui lòng liên hệ bằng cách nhắn tin qua page VNOI để xác nhận đăng ký tham gia trước ngày 23h59’, Thứ hai, ngày 23/6/2025.

⚔️ Ngoài ra, để tìm ra những thí sinh xứng đáng nhất, BTC sẽ cân nhắc lựa chọn tối đa 3 suất khuyến khích thông qua ý kiến của các bạn bằng cách đề cử tại form.

⏰ Thời hạn điền điền form: 23h59’, Thứ ba, ngày 24/6/2025.

❤️ BTC rất mong nhận được những đề cử của các bạn với lý do thật ý nghĩa để có thể tìm ra những cái tên xuất sắc tham dự Chung kết. Vậy là VNOI CUP 2025 đã dần đi đến chặng đua cuối cùng để tìm ra chủ nhân của chức vô địch VNOI CUP năm nay, hãy cùng chúng mình theo dõi những thông tin mới nhất trên fanpage VNOI nhé 😉