Programming Contest Problem Types

时间:2022-10-11 06:55:31
Programming Contest Problem Types     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.

 
译文:
程序设计竞赛的问题类型
Hal Burch 在 1999 年的春假做了一次分析并获得了一个令人惊讶的发现:程序设计竞赛的问题中只有 16 种类型!
此外,在 IOI 出现过的问题中,前面几种占了大概 80% 。它们分别是:
  • 动态编程(DP)
  • 贪婪算法
  • 枚举搜索
  • 漫水填充算法(Flood Fill)
  • 最短路径
  • 递归回溯搜索技术
  • 最小生成树
  • 背包问题
  • 计算几何
  • 网络流
  • 欧拉回路
  • 二维凸包问题
  • 大数问题
  • 启发式搜索
  • 近似搜索
  • 杂项题

最有挑战性的问题是牵涉了环(组合、子集等)的组合问题,围绕着某个上面的问题,或甚至是一个算法中又有其他算法在里面的环。即使这些问题从概念上看都是“显而易见的”,但它们似乎都非常难以做对。

如果你可以精通40%的上述类型问题的解法,你大概可以保证能在IOI拿银牌。精通80%的话,你几乎可以肯定就是金牌的层次。当然了,“精通”是一件很困难的事情!我们将提供大量的问题,你可以用来磨练你的能力以追求国际奖项。