How much does pure mathematics help in competitive programming?
Will an IMO medalist get familiar with programming faster than a normal person?
What are the downsides for having a mathematical background in terms of coding and efficiency ( if there exists any )?
Competitive Programming is my first real authentic approach to science, (Yeah, our education system is that bad), so my mathematics is next to zero, what are the mathematical subjects that could help someone directly or indirectly in Programming in general?
Also, in ACM-ICPC style competitions, how does a mathematician contribute to the team exactly?
It would be very interesting to hear about real life examples and so-on :D.
I also have the same question!
the only person I was thinking about while reading this is rng_58, legend of codeforces
Also in top 20 of all times at IMO.
TeaPot is another example how great mathematician (2x gold medal on IMO) can become a top-30 great coder (according to Codeforces rating) in less than two years. He started participating in programming contests when his teammates GlebsHP and meshanya invited him to join their team for ACM ICPC in 2013 and now he is 2-times vice-champion of ICPC World Finals. Also they overperformed rng_58 team this year =)
Speaking of top-30 users, peter50216 was well-known for his mathematical abilities (3x IMO silver) before he switched to programming contests.
surwdkgo with 2500+ rating, had 1 gold metal each in IMO, IOI, and IPhO.
He currently studies in MIT.
Basically him and peter50216 were the 2 whom we considered legends at the time.
If you haven't read this comment already, this might be interesting to you!
Link
I was just about to link the same comment :D
You need strong mathematical skills to take good care of your frog and flower.
Explains why they died on me
Because you don't repeat them, that's why
I've never been to IMO, but my last two years in school I was in top-5 on All-Russian Math Olympiad.
I started participating in programming contests about three years ago and I think that I would never reach my level without math skills.
In ACM ICPC style contests there are often 2-3 problems which require some math skills. And it is very convinient when there is a man in your team who can solve such problems quickly.
I think that math "upgrades" your brain. It was easy for me to understand some algorithms, especially graph and dp.
Sorry for my poor English
I have the same problem (since I live in the same country) and I have tried to handle it recently. The topics I feel that we need to master mostly relate to algebra. I usually see myself unable to decompose some problems or even find the disjunction of their states. Moreover, things like probabilities and combinatorics usually drive me crazy because I always feel like I have deduced the right formula, and at last it turns out that I didn't, and I usually cannot know the reason without looking at the correct solution. I see some of those topics as the next step for me, so I hope this will help you. BTW, I recently bought a book about linear algebra, and I don't know why.
advanced linear algebra doesn't help much in competitive programming in my opinion.
you only need matrix multiplication for quickly computing linear recurrences which doesn't really need to buy a full book to learn it.
Yes, mathematics definitely helps much in competitive programming. And by that I don't mean that mathematic backgrounds allows to solve some tough number theory questions which are probably less than 1% of problems present here, but for me "mathematics" means the same as "logical thinking". People able to do well in mathematical competitions do perform well and have a big boost when it comes to competitive programming not because of their knowledge of specific theorems, but because they are able of conducting logical and precise reasoning. Math in a sense we are talking about now is a state of a mind/style of thinking not knowledge of few theorems from number theory.
From my experience I can say that people competing in POI can be partitioned into two sets. People who were doing math and they heard about POI and decided to learn programming and people who where programming and they heard about POI and decided to learn some algorithmics (of course not exactly, but allow me use that simplification). Do I have to tell you that there is a high correlation between being from the first group and performing well :P? Maybe on POI that difference is not that significant, because some math guys don't know how to code well (I didn't in high school, in my opinion I improved myself a lot in that matter), but they are those people who are more likely to continue competitive programming with some successes.
What is moral for those, who are reading this and want to fix their lack of math? I don't know, I suppose that at this moment, doing algo problem seems much more reasonable than doing math problems :P.
You said my words. I do respect these people a lot! I'm twin, I study computer and my brother (Lost) studies mathematics, this year I got gold medal in national informatic Olympiad and my brother got gold medal in national math Olympiad, we have been together as 2-member team a lot, and I saw him solving problems faster than me many times (actually theory of problem, cause I was the coder at all) , to be honest, sometimes I was jealous about him, how can he solve programming problems faster than me when I am the one who studies computer, and I am too weak on math problems :D
BTW , this year he decided to enter informatic and I decided to enter math, I try my best to help him to surpass any other participants this year! And he should just pray for me to pass the entrance exam :D
UPD: He's now in our IMO team :-)
Here is our childhood pic (I'm the one on the right):
"what are the mathematical subjects that could help someone directly or indirectly in Programming in general?"
it would be really great if someone listed a number of topics in details (not just "combinatorics" or "algebra"), what topics under these two should be understood ?
Off the top of my head, here are some mathematical topics I encountered in programming competitions:
"Will an IMO medalist get familiar with programming faster than a normal person?" Yes,antontrygubO_o
Yes, zscoder.