Lộ trình ôn thi Olympic tin học và hướng dẫn ôn thi ACM-ICPC – Chick Golden

Bạn đang đọc: Lộ trình ôn thi Olympic tin học và hướng dẫn ôn thi 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 và ACM này chúng tôi sẽ san sẻ link tới những 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 những tài nguyên có ích lại một chỗ, và bạn trọn vẹn hoàn toàn có thể thuận tiện follow để học. Lộ trình này cũng gồm có những thuật toán và cấu trúc tài 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:

Tôi đáp ứng tên của chúng chính do trọn vẹn hoàn toàn có thể bạn sẽ không hề nộp giải thuật 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 thông tin thông tin tài khoản trên đó .

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

Đây là list những 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

Chúc những bạn sinh viên có một mùa thi Olympic và ACM-ICPC thành công xuất sắc !

Source: https://laodongdongnai.vn
Category: Tin Tức