The Theory behind Programming Contests

Classical Problems:

Graph Theory-These are the easier problems in a programming contest.The challenge lies in the ability to manage time and memory with choice and implementation of appropriate Data Structure.

Number Theory-These are generally elementary but the toughest of all problems in any programming contest.By elementary what I mean is that the theory behind them is understandable even for a layman but are very difficult to reason out. They range from elementary gcd-lcm,factorization-primality,rationality-irrationality, divisibility-modularity to critical analysis of Diophantine equations.

Group Theory-Group Theory is the language of modern mathematicians and Computer Scientists.Tough to comprehend but has revolutionary range of applications and one of the most powerful weapons of a programmer. Group Theory along with Graph Theory forms the basis of solution to most of the tough Combinatorics problems.

Game Theory-Problems in game theory can range from easy to super tough ones.The hurdle is to identify the underlying problem from the complicated storyline or its application field’s description in the problem statement.

Computational Geometry-Techniques(mostly polynomial time) devised to tackle problems which are not solvable in constant time i.e using classical geometry solely.Prerequisite is to have a good understanding of High School Geometry and their manipulation techniques in Cartesian and polar co-ordinate system and a bit of elementary trigonometry as well.Computational Geometry is an area where programmers are mostly found to lag in.

Challenge Problems:

These are basically Optimization problems for which no particular correct algorithm exits(or has not been discovered till date).These problems generally do not form a part of any on-spot programming contest.They are mainly for contests which span over a longer period of time.These problems can be from any active research areas.
Sound knowledge of Calculus,Numerical Analysis, Probability ,Statistics, Fuzzy Logic,Neural Network and Artificial Intelligence comes in handy.

Advertisement