March 03, 2009

A new discovery of Programming

I was preparing to do excise in USACO about a number of mouths before, but what I do is so few!
Today I went to USACO and then find these words:
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.

I think data structure and algorithm is one of the most important thing to a computer science student. So from now on there will be a tag called "data structure and algorithm". My teacher said it is simple because you only need to know a few definitions and what you need is to have the flexibility to use them.
Want to learn it, follow me!

No comments:

Post a Comment