Tổng hợp các Team VNOI

Vậy là đã 2 tháng kể từ đợt tuyển TNV Gen 5, hãy cùng chúng mình điểm lại những hoạt động để lại nhiều dấu ấn của các bạn TNV trong thời gian qua nhé.

Team Cộng Đồng

Team Cộng Đồng – những người luôn âm thầm đứng sau, chăm chút cho mọi hoạt động truyền thông của VNOI. Trong nhiệm kỳ Gen 5, Team đã có nhiều đóng góp nổi bật trong việc lan tỏa hình ảnh và thành tích của thí sinh Việt Nam trên đấu trường quốc tế, góp phần quảng bá mạnh mẽ bộ môn lập trình thi đấu tới học sinh, sinh viên, giáo viên và phụ huynh trên toàn quốc, đặc biệt là trong công tác truyền thông cho ICPC. Chỉ trong vòng 03 tháng (từ đầu tháng 8 đến tháng 11), fanpage VNOI đã tăng từ 22 000 lên hơn 28 000 lượt theo dõi, đạt hơn 10 triệu lượt xem – minh chứng rõ ràng cho sức lan tỏa và hiệu quả hoạt động của Team Cộng đồng trong nhiệm kỳ này.

Trước thềm các vòng thi ICPC Vòng Miền tại Việt Nam, Team Cộng Đồng đã liên tục đẩy mạnh truyền thông và quảng bá cuộc thi trên nhiều nền tảng mạng xã hội, cũng như các kênh thông tin đại chúng. Nhờ những nỗ lực đó, ICPC Vòng Miền năm nay đã ghi nhận số lượng đội tuyển và thí sinh tham dự cao kỷ lục – phá vỡ những con số thống kê của hơn 10 năm tổ chức trước đó. Trong suốt ba tuần diễn ra kỳ thi, Team Cộng Đồng đóng vai trò là cầu nối uy tín giữa các bạn thí sinh tham gia và những người theo dõi kỳ thi và Ban Tổ chức OLP-ICPC Việt Nam. Các thành viên đã tích cực truyền tải thông tin, hướng dẫn và gửi thông điệp từ BTC đến thí sinh, góp phần đảm bảo kỳ thi được diễn ra minh bạch, công bằng và chuyên nghiệp, đặc biệt trong bối cảnh các vòng loại đang phải đối mặt với vấn đề sử dụng Trí tuệ nhân tạo (AI) trong kỳ thi.

Tại ICPC Quốc gia 2025, ban Truyền thông VNOI đã tích cực phối hợp cùng với các đơn vị truyền thông và các đơn vị đăng cai ICPC Quốc gia 2025 nhằm xây dựng các kế hoạch truyền thông, thiết kế ấn phẩm và sáng tạo nội dung để quảng bá cho kỳ thi tập trung cấp quốc gia lớn nhất năm 2025 của cộng đồng lập trình thi đấu Việt Nam.

Vào đầu tháng 11/2025, Team Cộng Đồng đã tham gia tháp tùng các đội thi và thí sinh Việt Nam tham dự The 2025 ICPC Asia Bangkok Regional, liên tục đưa tin và cập nhật hình ảnh, thành tích của các đội Việt Nam và quốc tế tại đấu trường khu vực Asia Pacific đầu tiên của mùa giải 2025-2026.

Team Wiki

Song song với hoạt động truyền thông sôi nổi của Team Cộng đồng, Team Wiki trong năm 2025 tiếp tục giữ vai trò quan trọng trong việc xây dựng và hoàn thiện kho tri thức học thuật của VNOI – nơi cung cấp nguồn tài liệu chất lượng, dễ tiếp cận cho các bạn yêu thích lập trình thi đấu.

Từ đầu Gen 5 đến nay, Team Wiki đã xuất bản bài viết đầu tiên – “Phi hàm Euler”, đánh dấu cột mốc khởi đầu cho chuỗi nội dung học thuật được biên soạn và chuẩn hóa. Bên cạnh đó, bài "Giải quyết bài toán LCA bằng DSU" cũng đang trong giai đoạn hoàn thiện và sẽ sớm được ra mắt trên Tạp chí VNOI trong thời gian tới.

Hiện nay, Team đang có tổng cộng 6 bài viết đang được 'chăm chút' để chờ xuất bản đến độc giả , bao gồm:

• 5 bài cho Wiki: Tham lam, Sắp xếp, Bao hàm – Loại trừ, Sinh test (Kỹ năng phòng thi OI), DP Knapsack
• 1 bài cho Tạp chí: DP Knapsack on Tree

Trong nửa đầu Gen 5.0, định hướng của Team Wiki là tập trung hoàn thiện toàn bộ các chủ đề cơ bản còn thiếu hoặc các bài viết cũ chưa đạt chất lượng mong muốn. Với mong muốn xây dựng một nguồn tài liệu lý thuyết có chất lượng tham khảo cao, dễ hiểu và nhất quán, giúp những bạn mới bắt đầu với lập trình thi đấu (CP) có thể học tập hiệu quả hơn. Sau khi hoàn thiện các mảng kiến thức nền tảng, Team sẽ mở rộng sang những chủ đề chuyên sâu và bài viết có độ khó cao hơn, phục vụ nhóm độc giả đã theo đuổi CP lâu năm. Giai đoạn này cũng hứa hẹn sẽ mang đến những nội dung phân tích sâu sắc, mang đậm dấu ấn học thuật của Gen 5.

Team Contest

Ngoài ra, Team Contest trong nhiệm kỳ Gen 5 mang tới cho cộng đồng lập trình nhiều contest vô cùng bổ ích, trong đó, Team đã tổ chức thành công hai contest lớn:

• Educational DP Advanced Contest Part 2
• Regular Contest 22

Không những thế, Team còn chuẩn bị và lên kế hoạch xuất bản ba contest thuộc chuỗi Coding Challenge, tiếp tục tạo sân chơi học thuật cho cộng đồng. Hiện tại, Team Contest đang có những định hướng mới dành cho các contest phục vụ cho VOI sắp tới, hướng tới mô hình tổ chức tối ưu và đem lại trải nghiệm luyện tập hiệu quả hơn. Song song với các kỳ thi mới, Team dự kiến sẽ phối hợp cùng Team Cộng đồng để quảng bá trở lại những contest Educational trước đây, vốn rất phù hợp với nhóm học sinh đang ôn luyện kiến thức ở mức VOI. Ngoài ra, Team sẽ tiếp tục duy trì tần suất tổ chức các contest Bedao Regular thường xuyên, nhằm duy trì sự sôi động và tính liên tục cho hoạt động luyện tập của cộng đồng.

Team Tech

Và cuối cùng, không thể không nhắc đến Team Tech – những người âm thầm đứng sau, vận hành toàn bộ hệ thống kỹ thuật của VNOI. Từ nền tảng Wiki, Contest cho đến hệ thống quản lý nội dung, Team Tech luôn đảm bảo mọi hoạt động của các Team khác diễn ra trơn tru, ổn định và an toàn. Đặc biệt trong Gen 5, Team Tech đã ghi dấu ấn mạnh mẽ với những con số ấn tượng trong các kỳ thi ICPC: 9870 lượt nộp bài tại ICPC Miền Trung 2025 và 4881 lượt nộp bài tại ICPC Miền Bắc 2025. Những con số này không chỉ thể hiện khối lượng công việc khổng lồ mà Team đã xử lý, mà còn minh chứng cho năng lực vận hành vượt trội và sự tin cậy của hệ thống kỹ thuật VNOI, vốn đã được cải thiện vượt bậc so với các mùa thi trước. Không dừng lại đó, Team Tech còn mở rộng hỗ trợ trong nhiều kỳ thi về AI như Viettel AI Race 2025 (của Tập đoàn Công nghiệp - Viễn thông Quân đội (Viettel)) hay cuộc thi Olympic Trí tuệ nhân tạo sinh viên Việt Nam.

Các tình nguyện viên Gen 5 còn có cơ hội tham gia kỳ thi ICPC với vai trò Thanh tra - Giám sát tại 13 điểm thi tập trung toàn quốc theo yêu cầu từ BTC OLP-ICPC Việt Nam để đảm bảo một môi trường thi đấu lành mạnh, trong sạch, công bằng của hơn 491 đội thi và 1473 thí sinh.

Từ truyền thông, học thuật đến tổ chức và kỹ thuật, bốn Team của VNOI Gen 5 đã cùng nhau tạo nên một bức tranh toàn diện – nơi đam mê, sáng tạo và tinh thần cống hiến hòa làm một. Đằng sau mỗi bài viết, mỗi sự kiện, mỗi dòng code là nhiệt huyết và lòng tận tâm của các tình nguyện viên – những người trẻ luôn nỗ lực vì một cộng đồng lập trình thi đấu lớn mạnh hơn từng ngày. Gen 5 không chỉ là thể hiện cho một nhiệm kỳ TNV, mà là một hành trình trưởng thành của cả tập thể VNOI nói chung, nơi mỗi người góp một phần nhỏ để cùng hướng đến mục tiêu lớn: "Xây dựng một cộng đồng Tin học Việt Nam năng động, đoàn kết và cùng phát triển"

Quy hoạch động cái túi trên cây

Người viết:

• Nguyễn Tấn Minh - Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.

Reviewer:

• Nguyễn Quang Minh - Michigan State University.
• Võ Khắc Triệu - National University of Singapore.

Mở đầu

Đối với nhiều người theo đuổi Lập trình thi đấu, hai lớp bài toán quy hoạch động cái túi và quy hoạch động trên cây chắc hẳn là hai lớp bài toán vô cùng quen thuộc.

Bên cạnh đó, ta còn có dạng bài toán kết hợp ý tưởng quy hoạch động cái túi lên cấu trúc cây, cho ra đời lớp bài toán quy hoạch động cái túi trên cây. Đây tưởng chừng như một dạng bài tập rất hóc búa và đòi hỏi các thuật toán phức tạp. Tuy nhiên, chỉ với một vài lập luận tương đối đơn giản thì ta đã thấy được rằng, chỉ cần duyệt cây một cách khéo léo, ta đã có thể giải quyết bài toán quy hoạch động cái túi trên cây đơn giản hơn nhiều.

Trong mục Kỹ thuật thú vị của Tạp chí VNOI lần này, chúng ta sẽ cùng điểm qua các phân tích liên quan đến lớp bài toán quy hoạch động cái túi này.

Trường hợp chính

Bài toán: CEOI 2017 - Museum

Cho cây gồm ~n~ đỉnh (~1 \leq n \leq 10^4~), ~n - 1~ cạnh có trọng số cho biết thời gian di chuyển qua cạnh đó, và hai số nguyên ~k, x~. Tìm lộ trình tốn ít thời gian nhất để di chuyển từ ~x~ qua ~k~ đỉnh khác nhau kể cả ~x~ (kết thúc tại đỉnh bất kỳ).

Phân tích bài toán

Để đơn giản hóa bài toán, ta tạm thời biến đổi ràng buộc bài toán thành lộ trình xuất phát từ ~x~ phải quay về đỉnh ~x~.

Đặt gốc cây tại ~x~. Ta thấy rằng với mỗi cây con ~v_{x, i}~ của ~x~, ta cần thăm ~s_{x, i}~ đỉnh sao cho ~s_{x, 1} + s_{x, 2} + \dots + s_{x, t} = k - 1~. Hơn nữa, tập các đỉnh được thăm tạo thành một thành phần liên thông.

Từ đó, ta có ý tưởng đặt trạng thái quy hoạch động ~\texttt{dp}(u, j)~ là tổng thời gian để thăm ~j~ đỉnh của cây con gốc ~u~ và quay lại đỉnh ~u~. Dễ thấy ~j \leq \texttt{sz}[u]~ với ~\texttt{sz}[u]~ là kích thước của cây con gốc ~u~. Gọi ~v_1, v_2, \dots, v_t~ và ~w_1, w_2, \dots, w_t~ lần lượt là các đỉnh con của ~u~ và trọng số các cạnh nối tới chúng. Khi đó, ta có công thức truy hồi:

$$ \texttt{dp}(u, j) = \min_{s_1 + s_2 + \dots + s_t = j - 1} \left( \sum_{1 \leq i \leq t} \texttt{dp}(v_i, s_i) + [s_i \geq 1] \cdot 2w_i \right) $$

Nếu xem một cây con ~v_i~ là "một loại món đồ" và cây con ~u~ là "cái túi", ta có thể biến đổi chúng thành một bài toán quy hoạch động cái túi: Với mỗi loại món đồ, ta có thể chọn ~s_i~ cái với chi phí ~\texttt{dp}(v_i, s_i) + [s_i \geq 1] \cdot 2w_i~, cần chọn các món đồ sao cho tổng số lượng được chọn là ~j - 1~. Ở đây ~[X]~ là ký hiệu của Inverson bracket, mang giá trị ~1~ khi mệnh đề ~X~ đúng và ~0~ nếu ngược lại.

Để xử lý bài toán con trên, ta gọi ~\texttt{knap}(i, j)~ là tổng chi phí tối thiểu nếu chọn ~j~ món đồ ở ~i~ loại món đồ đầu tiên. Ta có công thức truy hồi

$$ \texttt{knap}(i, j) = \min_{0 \leq c \leq \texttt{sz}[v_i]} (\texttt{knap}(i - 1, j - c) + \texttt{dp}(v_i, c) + [c \geq 1] \cdot 2w_i) $$

Để tính mọi trạng thái ~(i, j)~, độ phức tạp của hàm quy hoạch động cái túi này là ~\mathcal{O}(\texttt{sz}[u]^2)~, dẫn đến độ phức tạp chung của bài toán lên đến ~\mathcal{O}(n^3)~. Tuy nhiên, nếu chỉ duyệt những trạng thái "có nghĩa" một cách khéo léo, độ phức tạp của thuật toán đã có thể giảm xuống ~\mathcal{O}(n^2)~!

Cải tiến & Phân tích độ phức tạp

Để ý rằng khi duyệt đến ~i~ cây con đầu tiên, ~v_1, v_2, v_3, \dots, v_i~, chỉ có các trạng thái ~\texttt{knap}(i, j)~ thỏa ~j \leq \texttt{sz}[v_1] + \texttt{sz}[v_2] + \dots + \texttt{sz}[v_i]~ mới có giá trị xác định, còn lại là các giá trị vô cực, không đóng góp vào công thức truy hồi. Do đó, để tiết kiệm tối đa số lần duyệt, ta có thể cài đặt quy hoạch động trên cây như sau:

int knap[2020], dp[2020][2020];

void dfs (int u, int p) {
    // khởi tạo mảng knap[...]
    // ...

    int knapSize = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int preTake = knapSize; preTake >= 0; preTake--)
            for (int curTake = 0; curTake <= sz[v]; curTake++)
                // tính knap[preTake + curTake] dựa trên
                // knap[preTake] và dp[v][take]
        knapSize += sz[v];
    }
    sz[u] = 1 + knapSize;

    // cập nhật dp[u][...] dựa trên knap[...]
    // ...
}

Để phân tích độ phức tạp, ta có thể mô hình hóa quá trình duyệt các cặp ~(\texttt{preTake}, \texttt{curTake})~ thành duyệt các cặp đỉnh ~(s_1, s_2)~ với ~s_1~ thuộc một trong các cây con trước đó ~v_1, v_2, \dots, v_{i-1}~ hoặc ~s_1 = u~, và ~s_2~ thuộc cây con hiện tại ~v_i~. Đặc biệt, các cặp ~(s_1, v_i)~ sẽ được tính 2 lần.

Cả hai mô hình duyệt đều có đúng ~(\texttt{knapSize} + 1) \cdot (\texttt{sz}[v] + 1)~ bước duyệt.

Ví dụ, ở hình trên, tại bước duyệt cây con ~v_i~, ta có thể hình dung việc duyệt các cặp ~(\texttt{preTake}, \texttt{curTake})~ giống như việc duyệt các cặp ~(s_1, s_2)~ sao cho ~s_1~ thuộc nhóm màu xanh/tím và ~s_2~ thuộc nhóm màu đỏ.

Một nhận xét quan trọng là hai đỉnh ~s_1, s_2~ chỉ sẽ được bắt cặp tại lượt DFS của đỉnh ~u~ thỏa ~\texttt{lca}(s_1, s_2) = u~. Do đó, với hai đỉnh ~z_1 < z_2~, dễ thấy tổng số lần duyệt của cặp ~(z_1, z_2)~ và ~(z_2, z_1)~ chỉ là tối đa ~2~ lần.

Tổng kết lại, số lần duyệt tối đa của cách cài đặt quy hoạch động như trên là:

$$ 2 \cdot C_n^2 = n \cdot (n - 1) = \mathcal{O}(n^2) $$

Có thể thấy, số lần duyệt tối đa thậm chí còn chưa đến ~n^2~!

Thuật toán

Quay lại bài toán ban đầu, ta gọi ~\texttt{dp}_0(u, j)~ và ~\texttt{dp}_1(u, j)~ lần lượt là tổng thời gian để thăm ~j~ đỉnh thuộc cây con ~u~ rồi quay về ~u~ (trạng thái 0) hoặc kết thúc ở một đỉnh bất kỳ là con của ~u~ (trạng thái 1). Khi đó, ta điều chỉnh công thức truy hồi thành:

$$ \begin{align*} \texttt{dp}_0(u, j) &= \min_{s_1 + s_2 + \dots + s_t = j - 1} \left( \sum_{1 \leq i \leq t} \texttt{dp}_0(v_i, s_i) + [s_i \geq 1] \cdot 2 w_i \right) \\ \texttt{dp}_1(u, j) &= \min_{\substack{s_1 + s_2 + \dots + s_t = j - 1 \\ b_1 + b_2 + \dots + b_t = 1}} \left( \sum_{1 \leq i \leq t} \texttt{dp}_{b_i}(v_i, s_i) + [s_i \geq 1] \cdot (2 - b_i) \cdot w_i \right) \end{align*} $$

Nói cách khác, với ~\texttt{dp}_0(u, j)~, mọi cây con sẽ được thăm rồi quay về ~u~. Với ~\texttt{dp}_1(u, j)~, ta chọn một cây con để kết thúc hành trình, các cây con còn lại sẽ được thăm rồi quay về ~u~. Việc thực hiện quy hoạch động cái túi sẽ diễn ra tương tự phần phân tích như trên. Như vậy, ta có lời giải quy hoạch động trong ~\mathcal{O}(n^2)~.

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

const int mn = 1e4 + 1;
int dp[2][mn][mn], knap[2][mn], sz[mn], n, k, x;
vector<pii> adj[mn];

void dfs (int u, int p) {
    // gọi DFS và tính kích thước cây con (sz[u])
    sz[u] = 1;
    for (auto [v, w] : adj[u])
        if (v != p) dfs(v, u), sz[u] += sz[v];

    // khởi tảo mảng knap[...]
    knap[0][0] = knap[1][0] = 0;
    for (int i = 1; i <= sz[u]; i++)
        knap[0][i] = knap[1][i] = INT_MAX;

    // chạy DP Knapsack trên các cây con v[1], v[2], v[3],..., v[t]
    int knapSize = 0;
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        for (int preTake = knapSize; preTake >= 0; preTake--) {
            for (int curTake = 1; curTake <= sz[v]; curTake++) {
                int sum = preTake + curTake;
                knap[0][sum] = min(knap[0][sum], knap[0][preTake] + dp[0][v][curTake] + 2 * w);
                knap[1][sum] = min(knap[1][sum], knap[0][preTake] + dp[1][v][curTake] + w);
                knap[1][sum] = min(knap[1][sum], knap[1][preTake] + dp[0][v][curTake] + 2 * w);
            }
        }
        knapSize += sz[v];
    }

    // trả các giá trị từ hàm knap[...] sang dp[...]
    for (int i = 0; i < sz[u]; i++)
        dp[0][u][i + 1] = knap[0][i], dp[1][u][i + 1] = knap[1][i];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k, x; cin >> n >> k >> x;
    for (int i = 1; i < n; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }
    dfs(x, -1);
    cout << dp[1][x][k] << "\n";

    return 0;
}

Trường hợp có cận trên cố định

Bài toán: VNOJ - Bài toán cái túi trên cây

Cho cây gồm ~n~ đỉnh (~1 \leq n \leq 10^5~) và một số nguyên ~k~ (~1 \leq k \leq 200~). Các đỉnh trên cây được gán một trọng số được cho bởi dãy ~a_1, a_2, a_3, \dots, a_n~ (~-10^9 \leq a_i \leq 10^9~).

Tìm một thành phần liên thông gồm đúng ~k~ đỉnh trên cây sao cho tổng trọng số của các đỉnh thuộc thành phần liên thông đó là lớn nhất.

Phân tích bài toán

Tương tự với bài toán ở trên, ta cũng định nghĩa hàm quy hoạch động ~\texttt{dp}(u, j)~ là tổng trọng số tối đa của thành phần liên thông gồm đỉnh ~u~ và các nút con của ~u~. Công thức truy hồi của quy hoạch động là:

$$ \texttt{dp}(u, j) = \max_{s_1 + s_2 + \dots + s_t = j - 1} \left( \sum_{1 \leq i \leq t} \texttt{dp}(v_i, s_i) \right) + a_u $$

Ta cũng coi các cây con ~v_1, v_2, \dots, v_t~ như những "món đồ" trong bài toán quy hoạch động cái túi và tính hàm ~\texttt{knap}(i, j)~ như sau:

$$ \texttt{knap}(i, j) = \max_{0 \leq c \leq \min(k, \texttt{sz}[v_i])} ( \texttt{knap}(i - 1, j - c) + \texttt{dp}(v_i, c)) $$

Thoạt nhìn như thuật toán có độ phức tạp ~\mathcal{O}(nk^2)~ hay ~\mathcal{O}(n^2)~. Nhưng cũng tương tự trường hợp như trên, nếu duyệt một cách khéo léo, ta có thể giảm độ phức tạp xuống ~\mathcal{O}(nk)~!

Cải tiến & Giảm độ phức tạp

Khi duyệt để tính hàm ~\texttt{knap}(i, j)~, ta giới hạn các giá trị ~\texttt{preTake}~ bởi ~\min(\texttt{knapSize}, k)~ và các giá trị ~\texttt{curTake}~ bởi ~\min(\texttt{sz}[v_i], k - \texttt{preTake})~. Nói cách khác, ta có thể cài đặt quy hoạch động như sau:

long long knap[202], dp[100'002][202];
int k;

void dfs (int u, int p) {
    // khởi tạo mảng knap[...]
    // ...

    int knapSize = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int preTake = min(knapSize, k); preTake >= 0; preTake--)
            for (int curTake = 0; curTake <= min(sz[v], preTake); curTake++)
                // tính knap[preTake + curTake] dựa trên
                // knap[preTake] và dp[v][take]
        knapSize += sz[v];
    }
    sz[u] = 1 + knapSize;

    // cập nhật dp[u][...] dựa trên knap[...]
    // ...
}

Để phân tích độ phức tạp, ta lại sử dụng ý tưởng biến đổi mô hình for như trên thành duyệt các cặp đỉnh ~(s_1, s_2)~ có ~\texttt{lca}(s_1, s_2) = u~. Tuy nhiên, trong trường hợp số lượng đỉnh có thể chọn làm ~s_1~ hoặc ~s_2~ là nhiều hơn ~k + 1~, ta sẽ ưu tiên chọn ~s_1~ có thứ tự thăm DFS muộn nhất và ~s_2~ có thứ tự thăm DFS sớm nhất. Tương tự với phân tích ở phần trước, nếu đã chọn đủ ~\texttt{sz}[v_i]~ đỉnh làm ~s_2~, ta quay về chọn ~v_i~ làm đỉnh thứ ~\texttt{sz}[v_i] + 1~.

Ví dụ, với trường hợp trên, khi duyệt đến ~u = 1~ và ~v_i = 9~, với ~k = 2~, ta chỉ chọn các đỉnh ~6, 7, 8~ làm ~s_1~ và ~9, 10, 11~ làm ~s_2~. Để dễ phân tích, các đỉnh đã được đánh số theo thứ tự DFS.

Một nhận xét vô cùng quan trọng đó là khoảng cách của ~s_1, s_2~ trên dãy thứ tự DFS với cách chọn này sẽ là không quá ~2k + 1~. Trên thực tế, với điều kiện ~\texttt{preTake} + \texttt{curTake} \leq k~, ta còn có thể kết luận rằng khoảng cách thực sự là không quá ~k~.

Từ đó, ta cũng lập luận được rằng một cặp ~(s_1, s_2)~ xuất hiện không quá ~2~ lần, cộng với việc khoảng cách của ~s_1, s_2~ trên dãy thứ tự DFS là không quá ~k~, ta có thể kết luận rằng với mọi ~s_1~, ta chỉ có tối đa ~2k~ đỉnh có thể chọn làm ~s_2~.

Nói cách khác, số lần duyệt tối đa trong hàm quy hoạch động như trên là:

$$ 2nk = \mathcal{O}(nk) $$

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
ll knap[202], dp[mn][202];
int a[mn], sz[mn], n, k;
vector<int> adj[mn];

void dfs (int u, int p) {
    // tiền xử lý và khởi tạo mảng knap[...]
    sz[u] = 1;
    for (int v : adj[u])
        if (v != p) dfs(v, u), sz[u] += sz[v];

    for (int i = 1; i <= min(sz[u], k); i++) knap[i] = LLONG_MIN;
    knap[0] = 0;

    // thực hiện QHĐ cái túi trên các cây con của u
    int knapSize = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        for (int preTake = min(k, knapSize); preTake >= 0; preTake--)
            for (int curTake = 0; curTake <= min(k - preTake, sz[v]); curTake++)
                knap[preTake + curTake] = max(knap[preTake + curTake], knap[preTake] + dp[v][curTake]);
        knapSize += sz[v];
    }

    // cập nhật dp[u][...] dựa trên knap[...]
    for (int i = 0; i < min(sz[u], k); i++) dp[u][i + 1] = a[u] + knap[i];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, -1);

    ll ans = LLONG_MIN;
    for (int i = 1; i <= n; i++)
        if (sz[i] >= k) ans = max(ans, dp[i][k]);
    cout << ans << "\n";

    return 0;
}

Công thức biến thể

Bên cạnh đó, nếu công thức quy hoạch động cái túi có dạng:

$$ \texttt{dp}(u, j) = \min_{\substack{s_1 \neq s_2 \\ j_1 + j_2 = j}} (\texttt{dp}(s_1, j_1) + \texttt{dp}(s_2, j_2)) $$

Ta cũng có thể thực hiện quy hoạch động trong ~\mathcal{O}(n^2)~ (không có cận trên cố định) và ~\mathcal{O}(nk)~ (có cận trên ~k~ cố định). Phần chứng minh có thể được tìm thấy tại đây và tại đây.

Bài tập áp dụng

• CEOI 2017, Museum
• COCI 2019, Dzumbus
• Codeforces Round 419, C, Karen and Supermarket
• Codeforces Testting Round 10, D, Berland Federalization
• AtCoder Beginner Contest 207, F, Tree Patrolling
• Codefroces Round 607, D, Miss Punyverse

Đóng góp từ cộng đồng

📌 Các bạn cũng có thể đóng góp bằng cách gửi bài viết và câu hỏi cho VNOI qua: Form

📌 Phần thưởng dành cho những đóng góp xuất sắc từ cộng đồng: lựa chọn một bộ merch độc quyền của VNOI gồm sổ, bút và sticker, hoặc nhận tiền nhuận bút. Ngoài ra, các bạn có nhiều đóng góp sẽ được nhận thêm áo VNOI.

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

Giải quyết bài toán LCA bằng DSU

Tác giả:

• Võ Đức Đoàn - THPT Chuyên Nguyễn Tất Thành, Quãng Ngãi.

Reviewer:

• Nguyễn Tiến Mạnh - Đại học Bách khoa Hà Nội.
• Nguyễn Tấn Minh - Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
• Nguyễn Minh Hiển - Trường Đại học Công nghệ, ĐHQGHN.

Bài toán lowest common ancestor (gọi tắt là LCA) là một bài toán kinh điển, yêu cầu ta tìm tổ tiên chung gần nhất của hai đỉnh trên một cây. Các bạn có thể đã quen thuộc với các phương pháp giải quyết bài toán LCA như sử dụng nâng nhị phân hoặc RMQ.

Các phương pháp trên tuy rất tối ưu trong những trường hợp cụ thể, nhưng nếu số lượng đỉnh trên cây (~n~) và số lượng truy vấn (~m~) rất lớn thì sẽ không hiệu quả.

Để giải quyết những trường hợp trên, ta sử dụng thuật toán offline tìm LCA của Tarjan. Đây là một ứng dụng của cấu trúc dữ liệu (gọi tắt là CTDL) DSU, có thể giải quyết bài toán LCA với độ phức tạp rất nhanh: ~\mathcal{O}(n + m)~.

Thuật toán offline tìm LCA của Tarjan

Thuật toán offline tìm LCA của Tarjan, đúng như tên gọi của nó, là một thuật toán offline, tức là thuật toán phải biết trước được rằng nó sẽ phải tìm LCA của các cặp đỉnh nào.

Trước tiên, thuật toán sẽ tạo ~n~ tập hợp, mỗi tập hợp sẽ chứa một đỉnh trên cây. Sau đó, thuật toán duyệt cây bằng DFS. Với mỗi đỉnh ~u~, ta đánh dấu đỉnh ~u~ là đã được duyệt qua. Sau đó, ta thực hiện ~2~ quy trình chính:

• Duyệt cây: với mỗi đỉnh con ~v~ của ~u~, ta duyệt cây con gốc ~v~ và thực hiện hợp hai tập hợp chứa hai đỉnh ~u, v~. Lưu ý rằng phần tử đại diện của tập hợp chứa đỉnh ~u~ bất kì là đỉnh gần đỉnh gốc nhất.
• Xử lí truy vấn: với mỗi truy vấn ~(u, v)~ chứa đỉnh ~u~, nếu đỉnh ~v~ đã được duyệt qua, ta tính được LCA của truy vấn là phần tử đại diện của tập hợp chứa đỉnh ~v~.

Giả sử ta có cây sau, và ta cần tìm LCA của hai cặp đỉnh ~(4, 5)~ và ~(5, 6)~.

)

Khi duyệt DFS đến đỉnh ~5~, cây sẽ có dạng sau: các đỉnh màu xanh dương là các đỉnh chưa được duyệt còn các đỉnh màu xanh lục là các đỉnh đã thăm duyệt, các đỉnh nằm trong mỗi ô có đường màu đỏ là các đỉnh thuộc cùng một tập hợp.

Ta có phần tử đại diện của tập hợp chứa đỉnh ~4~ là đỉnh ~2~ nên LCA của ~(4,5)~ sẽ là đỉnh ~2~.

Cũng với lập luận tương tự, khi duyệt tới đỉnh ~6~, ta có LCA của ~(5, 6)~ sẽ là đỉnh ~1~.

Thông thường, các cách cài đặt DSU ở trên sẽ không đảm bảo việc sau khi hợp hai tập hợp, phần tử đại diện của tập hợp chứa đỉnh ~u~ sẽ là đỉnh gần gốc nhất. Để khắc phục điều này, ta cần một biến ancestor để khắc phục điều này. ancestor của một đỉnh ~u~ là đỉnh gần gốc nhất trong tất cả các đỉnh nằm trong tập hợp chứa đỉnh ~u~. Ở phần duyệt các cây con của ~u~, sau khi hợp hai tập hợp, Ta sẽ gán ancestor của đỉnh đại diện là đỉnh gần gốc nhất, ở đây là đỉnh ~u~. Đoạn code dưới đây thực hiện điều này có dạng: ancestor[dsu.find(u)] = u.

// CTDL DSU
struct UnionFind{ 
    vector<int> p;
    UnionFind(int n) : p(n, -1) { }
    int find(int u) { return p[u] < 0 ? u : p[u] = find(p[u]); }             
    bool isSameSet(int u, int v) { return find(u) == find(v); }   
    bool Union(int u, int v) {                                    
        u = find(u);                                              
        v = find(v);                                              
        if (u == v) return 0;
        if(p[u] > p[v]) swap(u, v);
        p[u] += p[v];
        p[v] = u;
        return 1;
    }
} dsu(N);
vector<int> adj[N]; // cây
vector<pair<int, int>> queries; // các truy vấn
int ancestor[N]; // đỉnh gần gốc nhất trong tập hợp chứa đỉnh u
vector<int> qry[N]; // truy vấn sau tiền xử lí
bitset<N> vst; // đỉnh đã được duyệt hay chưa

void OLCA(int u, int p){
    vst[u] = 1; // đã thăm đỉnh u
    ancestor[u] = u;

    // duyệt cây
    for(int v : adj[u]){
        if(v == p) continue;
        OLCA(v, u); // xử lí cây con
        dsu.Union(u, v); // Union tập hợp chứa đỉnh cha và tập hợp chứa đỉnh con
        ancestor[dsu.find(u)] = u;
    }

    // xử lí truy vấn
    for(int v : qry[u]){
        if(vst[v]){
            cout << "LCA(" << u << ", " << v << "): " << ancestor[dsu.find(v)] << '\n';
        }
    }
}

void lca(){
    // tiền xử lí các truy vấn
    for (auto [u, v] : queries){
        qry[u].push_back(v);    
        qry[v].push_back(u);    
    }

    // các đỉnh được đánh số từ 0 đến n - 1
    OLCA(0, -1);
}

Phân tích thuật toán

Có lẽ điều làm bạn lăn tăn nhất về thuật toán này chính là phần in ra LCA của cặp đỉnh ~(u, v)~.

Giả sử ~LCA(u, v) = w~, ta có thể thấy: Khi ta duyệt đỉnh ~w~, hai đỉnh ~u~, ~v~ sẽ nằm trong hai cây con khác nhau của đỉnh ~w~.

Sau khi duyệt cây con của ~w~ chứa đỉnh ~u~ (giả sử cây con chứa đỉnh ~u~ được duyệt trước), toàn bộ các đỉnh của cây con sẽ chỉ đến đỉnh ~w~ là đỉnh đại diện của tập hợp chứa các đỉnh ấy cho tới khi chương trình duyệt xong đỉnh ~w~. Khi này, lúc duyệt sang cây con chứa đỉnh ~v~, đỉnh đại diện của tập hợp chứa đỉnh ~u~ (tức là đỉnh ~w~) sẽ là LCA của cặp đỉnh ~(u, v)~.

Sử dụng lập luận trên, ta cũng có thể kết luận được rằng việc in ~LCA(u, v)~ của truy vấn ~(u, v)~ chỉ xảy ra đúng một lần mặc dù cặp truy vấn sẽ được xét ~2~ lần trong thuật toán.

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

Quá trình duyệt cây có độ phức tạp ~\mathcal{O}(n)~. Với mỗi đỉnh, ta duyệt các truy vấn tổng cộng là ~2m~ lần nên có độ phức tạp ~\mathcal{O}(m)~. Độ phức tạp của DSU rất nhỏ (~\alpha(n)~ cho các thao tác find, union với kĩ thuật nén đường đi và union theo thứ hạng/kích thước) nên ta cho nó bằng ~\mathcal{O}(1)~.

Độ phức tạp của thuật toán bằng ~\mathcal{O}(n + m)~.

So sánh với các thuật toán khác

Thuật toán offline tìm LCA của Tarjan có thể nói là thuật toán tìm LCA nhanh nhất khi so với các thuật toán ta thường sử dụng trong lập trình thi đấu.

Tuy nhiên, trên thực tế, nếu dữ liệu nhập không đủ lớn, thuật toán của Tarjan sẽ chậm hơn do những hạn chế về việc cài đặt thuật toán như việc gọi các hàm đệ quy liên lục như hàm OLCA và hàm dsu.find.

Tổng kết

Thuật toán offline tìm LCA của Tarjan là một thuật toán giúp ta giải quyết bài toán tìm LCA một cách nhanh chóng và hiệu quả. Thuật toán cũng là một ứng dụng của CTDL DSU mà nhiều người không hề hay biết.

Luyện tập

• Fast Lowest Common Ancestor
• LCA
• Làm quen bạn mới

Đóng góp từ cộng đồng

📌 Các bạn cũng có thể đóng góp bằng cách gửi bài viết và câu hỏi cho VNOI qua: Form

📌 Phần thưởng dành cho những đóng góp xuất sắc từ cộng đồng: lựa chọn một bộ merch độc quyền của VNOI gồm sổ, bút và sticker, hoặc nhận tiền nhuận bút. Ngoài ra, các bạn có nhiều đóng góp sẽ được nhận thêm áo VNOI.

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!

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!

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.