Computer Science Canada Contest Problem Types |
Author: | Paul [ Sat Nov 26, 2005 4:07 pm ] |
Post subject: | Contest Problem Types |
Eh, didn't know whether to put this in general programming, or contests, but see I've made a decision USACO Training Gateway wrote: 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... |
Author: | Hikaru79 [ Sat Nov 26, 2005 7:31 pm ] |
Post subject: | |
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 *Goes back to USACO* |
Author: | MysticVegeta [ Sat Nov 26, 2005 11:20 pm ] |
Post subject: | |
Those 16 categories could still cover almost infinite possibilities of questions.. |
Author: | Paul [ Sat Nov 26, 2005 11:33 pm ] |
Post subject: | |
Ah, but once you "master" one type, the variations of that type should be easy to adapt to. |
Author: | MysticVegeta [ Sat Nov 26, 2005 11:43 pm ] |
Post subject: | |
Everyone of them seem hard to me but ah... practise here i am come!! |
Author: | thegoose [ Mon Nov 28, 2005 8:18 pm ] |
Post subject: | Re: Contest Problem Types |
USACO Training Gateway wrote: 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. |