 |
Programming Contest Problem Types |
Hal Burch conducted an analysis over spring break of 1999 and made an amazing discovery: there are only 16 types of programming contest problems! Furthermore, the top several comprise almost 80% of the problems seen at the IOI. Here they are:
- Dynamic Programming
- Greedy
- Complete Search
- Flood Fill
- Shortest Path
- Recursive Search Techniques
- Minimum Spanning Tree
- Knapsack
- Computational Geometry
- Network Flow
- Eulerian Path
- Two-Dimensional Convex Hull
- BigNums
- Heuristic Search
- Approximate Search
- Ad Hoc Problems
The most challenging problems are Combination Problems which involve a loop (combinations, subsets, etc.) around one of the above algorithms - or even a loop of one algorithm with another inside it. These seem extraordinarily tricky to get right, even though conceptually they are "obvious".
If you can master solving just 40% of these problem types, you can almost guarantee a silver medal at the IOI. Mastering 80% moves you into the gold range almost for sure. Of course, `mastery' is a tough nut to crack! We'll be supplying a plethora of problems so that you can hone your skills in the quest for international fame.
- 动态编程（DP）
- 贪婪算法
- 枚举搜索
- 漫水填充算法（Flood Fill）
- 最短路径
- 递归回溯搜索技术
- 最小生成树
- 背包问题
- 计算几何
- 网络流
- 欧拉回路
- 二维凸包问题
- 大数问题
- 启发式搜索
- 近似搜索
- 杂项题
最有挑战性的问题是牵涉了环（组合、子集等）的组合问题，围绕着某个上面的问题，或甚至是一个算法中又有其他算法在里面的环。即使这些问题从概念上看都是“显而易见的”，但它们似乎都非常难以做对。
如果你可以精通40%的上述类型问题的解法，你大概可以保证能在IOI拿银牌。精通80%的话，你几乎可以肯定就是金牌的层次。当然了，“精通”是一件很困难的事情！我们将提供大量的问题，你可以用来磨练你的能力以追求国际奖项。