

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

You might close this question or downvote it, but I can't stop myself from asking the experts of mathematics who solve thousands of math problems. I'm a C++/C programmer who wants to improve his coding skills. I learnt many algorithms and several concepts but I believe this is not sufficient. Moreover, in the last few months, I've competed in various coding competitions where I observed a strong relationship between programming and mathematics. People who are good in mathematics are able to solve problems more easily compared to others. I know that it is the mental capability of an individual which allows him to do things in a better way, but, in my opinion, hard work can fill that gap to some extent. I'm ready to do a lot of hard work to become a good programmer but I lack proper guidance. So I'm posting this question expecting someone to come and help me, by giving some advice and suggestions on how to improve my mathematics for coding competitions. What is the best way to do it and are there any good books that can help me?

share|cite|improve this question
I don't think that ability of doing math implies good programming skills. Both are implied by analytical thinking and that can definitely be improved by doing math. Most probably what you are observing is that people who are good at math, can also find the shortcuts quicker since they are relatively more exposed to the methods which allow to see analogies among conceptual structures. – user13838 Oct 7 '11 at 9:17
@percusse : Then what should I do now ? – code_hacker Oct 7 '11 at 10:25
My personal opinion is that you first decide what is feeling right for you and what is not. Some visualize some write it down and plan. But as far as I know nobody became an expert without hard work and head scratching just because they know math or something else. Don't get me wrong, I think what you are trying to do is remarkable and tough but it takes a little bit of vision rather than building up the arsenal of knowledge. If you accept my humble advice, start reading this and try to picture their point of view. – user13838 Oct 7 '11 at 10:49
I don't know too much about it and I am an average programmer. But as you can see, things evolve and change as it has been with Java or any other new idea. Even Knuth himself tries to change the things once in a while . So why shouldn't not you? :) – user13838 Oct 7 '11 at 10:52
@code_hacker:I can understand your problem and possibly relate myself to it,I also faced the same situation few months before, algorithmic programming is a different thing than pure mathematics,it is more in the applied sense.If your mathematics basics is okay, all you need to do practice hard in Topcoder arena and then reading the editorials! (contd) – Quixotic Oct 7 '11 at 11:11
up vote 17 down vote accepted

I would divide the skills required for programming competitions as follows:

  1. The ability to think abstractly.
  2. The ability to employ well-known algorithms and algorithmic techniques.
  3. Knowledge of previous competitions tasks.
  4. Flexibility of point of view which allows to find easy implementations.
  5. General problem solving techniques.

Skill (5) consists of ideas such as "backward reasoning" and "reversing a task" (these are not even specific to exact sciences). Skill (4) is an art which is gained mostly by experience and also by looking at work done by other contestants. Skill (3) is obviously a matter of experience. Skill (2) is attained by thorough preparation including both solving problems and reading algorithms books. Skill (1) is again an art, but this time it is an art which has much in common with other branches of mathematics.

Let me give you some examples from the latest International Olympiad in Informatics (IOI2011,

Task RICEHUB (relatively easy) requires an insight similar to task POST from IOI2000, which is an example of skill (3).

Task RACE (relatively hard) is mostly a matter of applying a known technique. The easiest way to solve this one is to try known techniques one after the other until you realize which one gives an efficient algorithm. I think it's very hard to solve this if you approach it any other way (I'm not giving details of the solution to avoid ruining it for you. There's a solution on the website). So this is an example of skill (2).

Task PARROT (relatively easy, but conceptually new in IOI) can be used as an example of skill (4). The "mathematical" solution is not too hard, but there are implementation issues. Again, in order not to spoil the question, I would just suggest considering task MAGIC SQUARES from IOI1996 and task TWOFIVE from IOI2001 which involve implementation details similar to the ones in PARROT (MAGIC SQUARES is easier than PARROT and TWOFIVE is harder in respect to those implementation issues).

As for skill (1), task CROCODILE from IOI2011 can serve as an example, but I'd rather give you a cleaner one which also serves as an example for skill (5):

Consider the well known egg-droping problem (see

To solve this problem one should first reverse it and ask "what's the highest building I can solve with up to $t$ throws?". To solve the reversed problem, one should employ backward reasoning (reversing and backward reasoning are examples of skill (5) ) and say: Let's try to sketch a solution strategy: The first throw would be from... well.. I don't know where from. So let's denote the floor of the first throw by "t_1" and continue from there. I will not continue describing the solution, but note that "let's denote the floor by a variable and continue" is an example of abstraction. Instead of a number of a formula, we just accept the fact that we don't know what this floor is yet, make up a variable to denote it, and continue.

(you may find tasks from IOI up to IOI2008 in

From my experience with students participating in IOI, I would say that the ones who also participate in IMO (or otherwise very oriented toward mathematics and not just computer science) are:

  • Always on top in regard to skill (1)
  • Tend to be better than others at skill (5)
  • Have a potential to become exceptionally good at skill (4) after some hard training

EDIT: As a final advice: Try solving many tasks. Code any task you solve to make sure you understand all the details. After solving (or trying long enough), always read an official solution or discuss the solution with someone else. In a more advanced stage of your training, read tutorials you can find on the web especially about data structures. You can find some of these on TopCoder's website.

As topics which are traditionally considered as mathematics and not computer science:

  1. Mathematical games can be relevant to programming competitions.
  2. In many computational geometry tasks it may be worthwhile to feel comfortable with convex sets as mathematicians think of them (maybe this is a bit advanced).
  3. General mathematical experience and rigor can help you avoid wrong solutions which intuitively seem correct.

Overall, I'd say that the best way to become better in programming competitions is to train specifically for them while getting general mathematical education. There are not many "traditional math" topics which can help you directly with those competitions.

(probably the best and most relevant way to get general basic math education is to take "Linear Algebra" in university or to learn the same material elsewhere. Again, this is not directly relevant, but eventually your problem solving skills would benefit from the rigor you will learn at such a course).

share|cite|improve this answer
+1,Good answer :) – Quixotic Oct 7 '11 at 11:17
This is really a good answer.Can you suggest me some books which I can refer to strengthen my basics of mathematics? – code_hacker Oct 7 '11 at 13:22
My first book suggestion would be "Introduction to Algorithms, a Create Approach" by Udi Manber. As for more traditional mathematics, I don't know the basic books in English, but I think any first year book about Linear Algebra, Calculus or Discrete Mathematics should be good, as long as they are intended for mathematics students. Discrete Mathematics and Combinatorics are more relevant to computer science, while Calculus will give you the best treatment of mathematical rigor. Linear algebra is somewhere midway in those respects. As for mathematics directly relevant to competitions(contd) – user3533 Oct 7 '11 at 13:45
I would divide it to "mathematics for analysis of algorithms" and "mathematics involved in the contest problems". The former is not very hard and is covered, for example, in CLRS. The relevance of the latter vary between different programming competitions. In IOI, for example, there is only very basic traditional mathematics involved in the tasks (except, maybe, for the computational geometry tasks which are slightly more complex mathematically). What competitions will you attend? What tasks make you think you need to learn more mathematics? – user3533 Oct 7 '11 at 13:48
@code_hacker: Looking at your questions history, I think you could benefit from a book on Enumerative Combinatorics (the one by Charalambides for example). You may also benefit from studying IMO problems in number theory or combinatorics. There are books about IMO problems, but I don't know them well enough to give a recommendation. I would also recommend you to take a look at other kind of programming contest problems which are more about algorithms and less about numbers (this is my favorite genre of tasks. It characterizes IOI, but also appears in TopCoder and others). Good luck! – user3533 Oct 8 '11 at 7:51

As a slight counterpoint, I'll make the claim that if your goal is to become a better programmer, then the math skills you're looking for for contest problems probably aren't what you really want.

Don't get me wrong - I'm a huge fan of 'programmer math' (discrete mathematics, combinatorics, algorithmic analysis, etc) and believe that it's an immensely useful tool to have in your repertoire; and I absolutely adore 'recreational' mathematics and some of the branches of number theory that often wind up a part of programming contests. But those skills have virtually never been a part of my day-to-day work as a programmer (and I'm in one of the fields where they're most likely to come up), and in my opinion my knowledge of them is almost orthogonal to my programmer skills.

There's still ample use, certainly, for some of the basics - being able to simplify a problem first, being able to analyze the algorithms you use, all are handy skills; but the core tenets of programming (organization of code, abstraction, etc.) will IMHO carry you much farther. Programming contests are a lot of fun, and they're certainly encouraged, but they're not really a reflection of 'real-world' programming, in my experience, and I'd be a little leery of putting too much effort into skills that apply primarily to contest problems.

share|cite|improve this answer
I'll keep that in mind. – code_hacker Oct 7 '11 at 16:47

Your Answer


