Lộ trình ôn thi Olympic tin học & ACM-ICPC

Lộ trình ôn thi Olympic tin học & ACM-ICPC

Lộ trình này được xây dựng để chuẩn bị cho việc ôn thi Olympic tin học SV & ACM-ICPC, nhưng bạn cũng có thể sử dụng để:

• Các kỳ thi lập trình khác
• chuẩn bị cho các bài thi phỏng vấn
• Nâng cao kỹ năng thuật toán
• Phục vụ các môn tại trường học
• Đam mê

Yêu cầu với người học:

• Biết ít nhất một ngôn ngữ lập trình(Bạn phải có khả năng lập trình với ngôn ngữ đó)
• Có kiến thức & hiểu biết cơ bản về các Cấu trúc dữ liệu cơ bản(Mảng, Stack, Queue,…)(Nếu bạn không biết một trong số đó, hãy học nó khi cần sử dụng trong lộ trình này)

PS: Tôi có nói “Bất kỳ ngôn ngữ nào”, nhưng trong lộ trình này hầu hết sử dụng C, C++ và một chút Java, bạn vẫn có thể follow lộ trình này mà không nhất định phải biết các ngôn ngữ đó

Trong lộ trình ôn thi Olympic tin học & ACM này chúng tôi sẽ chia sẻ link tới các tài nguyên, chúng tôi khi viết lại những gì đã có. Chúng tôi chỉ sưu tập các tài nguyên hữu ích lại một chỗ, và bạn có thể dễ dàng follow để học. Lộ trình này cũng bao gồm các thuật toán và cấu trúc dữ liệu. Bạn nên follow lộ trình này theo từng tuần đã được chúng tôi chỉ định.

Hướng dẫn dành cho bạn

1. Đi tới nguồn tài nguyên cần học
2. Tập trung suy nghĩ, cố gắng code và đừng xem lời giải
3. Khi bạn gặp khó khắn(bạn đã cố gắng hết sức) hoặc đã hoàn thành nhiệm vụ, hãy xem lời giải, so sánh với lời giải của bạn và xem đâu là lời giải tốt nhất cho bài toán đó. Bạn có thể sẽ tìm được những thứ hay ho từ lời giải của người khác.
4. Khi bạn cảm thấy hài lòng với kiến thức có được, hãy nhớ giải quyết các bài toán của phần kiến thức đó.
5. Khi bạn hoàn thành hay gặp rắc rối, xem xét các lời giải khác và tìm xem bạn gặp lỗi gì và thấy được một lời giải tốt hơn.

Một số website ôn luyện

Trong lộ trình ôn thi Olympic tin học & ACM này chúng tôi sẽ sử dụng một số tài nguyên cho việc luyện tập. Như đã nói ở trên, các bài toán đã có sẵn, chúng tôi chỉ giúp bạn thấy chúng dễ dàng hơn. Đây là các website/công cụ chúng tôi sử dụng trong suốt lộ trình:

• Luyện Code
• Leetcode
• Spoj
• Hackerrank
• Topcoder
• Codeforces
• Lightoj
• ACM-Timus

Tôi cung cấp tên của chúng bởi vì có thể bạn sẽ không thể nộp lời giải của bạn hoặc xem bài toán. Vấn đề sẽ tốt hơn nếu bạn tạo cho mình một tài khoản trên đó.

Các kiến thức cần học

Đây là danh sách các chủ đề có trong lộ trình này..

Cấu trúc dữ liệu(DS)

• Stacks
• Queues
• Priority queue
• Hashmap
• Linked List
• Trees
• Heaps
• Advanced Trees
  • Tries
  • Segment trees
  • Fenwick tree or Binary indexed trees
  • RMQ
• SQRT Decomposition
• Disjoint Data Structure
• C++ STL (optional)

Giải thuật(Algo)

• Number Theory
  • Prime Numbers (Sieve of Eratosthenes)
  • GCD and LCM Euclid’s Algorithm
  • Modular Exponentiation
  • Long arithmetic (Multi, Add)
  • Efficient Prime Factorization
• Combinatorics(Probability-Combinations-Permutations-Matrix..)
• Computational geometry
  • Primitive Operations
    • Intuition
    • Polygon Inside, Outside
    • Implementing CCW
    • Immutable Point ADT
  • Convex Hull
  • Closest pair problem
  • Line intersection
• Sorting
  • QuickSort
  • Counting Sort
  • Merge Sort
• Searching
  • Binary Search
  • Ternary Search
• Graph Theory
  • Depth First Search (DFS)
  • Breadth First Search (BFS)
  • Dijkstra’s Shortest Path
  • Minimum Spanning Tree
  • Ford Bellman
  • Floyd Warshall
  • LCA (Lowest Common Ancestor)
  • Max Flow / Min Cut
• Dynamic programming
  • Knapsack
  • Matrix chain multiplication
  • Coin Change
  • Kadane
  • Longest increasing Subsequence (with RMQ)
• Strings
  • Z algorithm
  • Suffix Trees/Arrays
  • Knuth-Morris-Pratt Algorithm (KMP)
  • Rabin-Karp Algorithm
  • Hash
• Bit Manipulation
• Game theory
  • Nim game
  • Grundy numbers
  • Sprague-Grundy theorem
• Optional Advanced Algorithms
  • AVL Trees
  • Graph Coloring
  • Mo’s Algorithm
  • Palindromic Tree
  • Heavy Light Decomposition
  • Dynamic Programming by Profile
  • Rod Cutting
  • Topological Sorting
  • DP with Bitmask – Dynamic Programming
  • Diobhantine Equation – Math
  • Flood Fill – Graph

Lộ trình học tham khảo

Dưới đây là lộ trình ôn thi Olympic tin học & ACM-ICPC các bạn tham khảo. Mình có để link dẫn tới hướng dẫn chi tiết hơn cho mỗi tuần tại cột Week. Các bạn chỉ việc tiếp tục follow nội dung chi tiết bạn trong đó.

Tài liệu tham khảo

1. Diễn đàn VNOI
2. Lưu trữ tài liệu, đề thi của Olympic ACM-ICPC
3. Đề thi OLP-ACM qua các năm
4. Thi trực tuyến Regional 2017: https://hochiminh17.kattis.com/problems
5. Thi trực tuyến Regional 2018: https://hanoi18.kattis.com/problems
6. Lời giải ACM các năm: https://github.com/acmicpc-vietnam/acmicpc-vietnam.github.io
7. Algorithms used in Competitive Programming
8. How to prepare for ACM – ICPC

Chúc các bạn sinh viên có một mùa thi Olympic & ACM-ICPC thành công!