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:
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:
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:
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á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:
Bình luận