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?
[Math] How to improve mathematics for Programming Contests
contest-mathlearningsoft-question
Related Solutions
Well as a former math contestant I wanted to share my thoughts on this question.
First and foremost you have to understand that the competition and the result you'll achieve are by no means a measurement of your mathematical ability. A very nice example is a friend of mine. In my life I've participated in about 40 math contests (regional, county, national, international and even IMO). Since my friend was the same age as me, he also participated in all this contests and he was simply dominant. I mean of the 40 or so contests I've participated in he was better ranked in all of them, as far as I can remember. Actually there were around 10 instances when I was second only to him (few times we were tied, simply because both of us had perfect scores). So you would say that he was a better mathematician than me. Well, I believe that's not the case. We both chased a math degree on university and he had problems with topics that were not required for math competitions, such as calculus, differential equations... So at the end he decided to give up on math and he started studying computer science. So because of this I believe that he was the better math competitor of the two, but not the better mathematician. So the math competitions certainly help you to develop your math genius, but your success (or failure) there doesn't necessary translates to your further math career.
Since I come from a relatively small country, I noticed that we failed miserably at almost every international competition (both on individual and team scale). So I tried to investigate and find out why this is happening. Certainly the fact that the talent pool in my country is small plays a big role. On every international contest there are countries that have 100 to 500 times more population than my country, so I guess there is a greater probability that a math genius will be born in let say USA or China than in my country. But this wasn't the only reason. Compared to countries as big as mine, we still had very bad results. So I talked to other contestants and I asked them what's their formula to success. What I found out was astonishing.
Since our country is small, we believe that we have a deficit of talents, so we try to make up for it by practicing and practicing. So we learn a lot of theory and techniques. Actually when I asked some of the guys that won a gold or silver medal at the IMO, they had little or no clue about some techniques. That suprised me. But unlike in my country, where there are only 4 contests per year(regional, county, national and selection test), other countries have 15-20 contests or at least "friendly" contest (where students solve problems in an IMO athmosphere, but they receive no awards for the results). So I concluded that although I (simularly as every contestant in my country) had much more theoretical knowledges I failed to put it in practice or to implement it in a solution. But with the expereince they had others don't have this problem. So I would say that experience is as important as practice. So maybe the reason why you couldn't solve a Olympiad problem is because you didn't participate in math contest as a youngster.
Also what I found out is that most of the successful math contestant have a "competition mindset", i.e. they go on compeitions and they do their work for 4.5 hours. So as a competitor I wasn't able to establish this mindset in me, so what usualy was happening to me is that I was great on preparations camps or when I was practising and I was able to solve some tough IMO problems by myself. But when I was at the IMO I wasn't able to recreate the same success and I believe that was because of the pressure that I was feeling and of course the time constraint.
So since now occasionally I'm working with young math talents in the first few classes I teach them about this mental thing and I want them to get this "competition mindset", before the procede to learning techniques and "tricks" if they want to be successful on math contests.
I am in my 30s and about to get my B.S. with high honors and currently applying to PhD programs.
I am not good at math, it is very challenging to me and that is also why I enjoy it so much. Like you I have asked this question many times, and waited years thinking I was too old.
There will be moments of doubt as you will be surrounded by incredibly talented people younger than you are... For the rest of your life, you will always feel that you might be "too old" or "not smart enough." Do not fall for this common feeling and trap. Do what you wish and do it with integrity and honesty. Otherwise, you will live with regret, which is far worse than failure.
No one here can advice you whether Math is right or wrong for you, and I understand this fear all too well. You must decide for yourself.
Best Answer
I would divide the skills required for programming competitions as follows:
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, http://www.ioi2011.or.th/tasks):
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 http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml).
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 http://ioinformatics.org/history.shtml).
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:
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:
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).