Alex7's blog

Mathematics
By Alex7, 9 years ago, In English

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.

  • Vote: I like it
  • +108
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I also have the same question!

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

the only person I was thinking about while reading this is rng_58, legend of codeforces

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Also in top 20 of all times at IMO.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    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 =)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Speaking of top-30 users, peter50216 was well-known for his mathematical abilities (3x IMO silver) before he switched to programming contests.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it +14 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

If you haven't read this comment already, this might be interesting to you!

Link

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was just about to link the same comment :D

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +85 Vote: I do not like it

You need strong mathematical skills to take good care of your frog and flower.

→ Reply
»
9 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +72 Vote: I do not like 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.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +51 Vote: I do not like it

    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):

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

"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 ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    Off the top of my head, here are some mathematical topics I encountered in programming competitions:

    • Modular arithmetic, extended Euclid, Euler's totient function, Moebius function, Binomical coefficients, Bernoulli numbers, linear diophantine equations
    • Matrices, Gauss algorithm
    • Discrete probabilities, linearity of expectation, probability of conjunction of independent variables, distribution of order statistics.
    • Combinatorics, rule of sum/product, inclusion/exclusion principle, Burnside lemma, Gray code, Catalan numbers
    • Simple analitycal geometry (line intersection, line/circle intersection, inscribed circle), convex hull.
    • Recurrence relations, linear recurrences
    • Polynomials, fast Fourier transform
    • Hall's marriage theorem, Menger's theorem (graph problems in general tend to be math-heavy)
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"Will an IMO medalist get familiar with programming faster than a normal person?" Yes,antontrygubO_o

→ Reply