Problem Solving Category- an amazing discovery

Author Topic: Problem Solving Category- an amazing discovery  (Read 2539 times)

Offline mnsalim

  • Jr. Member
  • **
  • Posts: 78
  • Enjoy your time by learning
    • View Profile
    • Learning Review
Problem Solving Category- an amazing discovery
« on: April 20, 2017, 06:57:43 PM »
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''.
Md. Nazmul Hoq