-----------------------------------

Paul

Sat Nov 26, 2005 4:07 pm


Contest Problem Types

-----------------------------------

Eh, didn't know whether to put this in general programming, or contests, but see I've made a decision :P

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.



Would anyone like to contribute any tips/hints/ideas regarding this topic? I'm currently working through some USACO problems whenever I have time...


-----------------------------------

Hikaru79

Sat Nov 26, 2005 7:31 pm



-----------------------------------

The USACO Training Gateway simply rocks. While I think that what they wrote there is a bit of an oversimplification (I hope), they say enough GOOD stuff on that site to excuse themselves :P

*Goes back to USACO*


-----------------------------------

MysticVegeta

Sat Nov 26, 2005 11:20 pm



-----------------------------------

Those 16 categories could still cover almost infinite possibilities of questions..


-----------------------------------

Paul

Sat Nov 26, 2005 11:33 pm



-----------------------------------

Ah, but once you "master" one type, the variations of that type should be easy to adapt to.


-----------------------------------

MysticVegeta

Sat Nov 26, 2005 11:43 pm



-----------------------------------

Everyone of them seem hard to me but ah... practise here i am come!!  8-)


-----------------------------------

thegoose

Mon Nov 28, 2005 8:18 pm


Re: 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

Notice the list was made in 1999, a time while the programming competitions were still tame.
Things have completely gone over the top since then, with new problem types such as (just to list a few here):
  2-Satisfibility
  String Manipulation
  Data Structures (Red-Black Trees)
  Interactive
  Output Only on NPC problems
  Functional Analysis
  General Mathematical Combinatorics (e.g. sign representation)
  Matrice operations
The most insane part of these CS problems are problems drawn straight from research papers and put onto contests. Examples of this have occured in the POI (polish Olympiad), CTSC (Chinese team selection) and IOI.
Also, there are so many variations within some of these categories such as Dynamic Programming that harder problems keep on being created.