Scribd
Upload
11 views1 page

Programming Contest Problem Types

There are only 16 types of programming contest problems according to an analysis in 1999. The top types comprise almost 80% of problems seen at international competitions. These include dynamic programming, greedy algorithms, complete search, shortest paths, and more. The most challenging problems involve combinations of algorithms in loops. Mastering 40% of the problem types can earn a silver medal, and mastering 80% puts one in the gold range. Practice is needed to truly master the techniques.

Uploaded by

kabhijit04
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views1 page

Programming Contest Problem Types

There are only 16 types of programming contest problems according to an analysis in 1999. The top types comprise almost 80% of problems seen at international competitions. These include dynamic programming, greedy algorithms, complete search, shortest paths, and more. The most challenging problems involve combinations of algorithms in loops. Mastering 40% of the problem types can earn a silver medal, and mastering 80% puts one in the gold range. Practice is needed to truly master the techniques.

Uploaded by

kabhijit04
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

6/20/2015

ProgrammingContestProblemTypes

ProgrammingContestProblemTypes

HalBurchconductedananalysisoverspringbreakof1999andmadeanamazing
discovery:thereareonly16typesofprogrammingcontestproblems!Furthermore,the
topseveralcomprisealmost80%[Link]:
DynamicProgramming
Greedy
CompleteSearch
FloodFill
ShortestPath
RecursiveSearchTechniques
MinimumSpanningTree
Knapsack
ComputationalGeometry
NetworkFlow
EulerianPath
TwoDimensionalConvexHull
BigNums
HeuristicSearch
ApproximateSearch
AdHocProblems
ThemostchallengingproblemsareCombinationProblemswhichinvolvealoop
(combinations,subsets,etc.)aroundoneoftheabovealgorithmsorevenaloopofone
[Link],even
thoughconceptuallytheyare``obvious''.
Ifyoucanmastersolvingjust40%oftheseproblemtypes,youcanalmostguaranteea
silvermedalattheIOI.Mastering80%movesyouintothegoldrangealmostforsure.
Ofcourse,`mastery'isatoughnuttocrack!We'llbesupplyingaplethoraofproblems
sothatyoucanhoneyourskillsinthequestforinternationalfame.

USACOGateway|CommentorQuestion

[Link]

1/1

You might also like