Блог пользователя Alex7

Автор Alex7, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +108
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I also have the same question!

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Also in top 20 of all times at IMO.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +61 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +14 Проголосовать: не нравится

      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.

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

Link

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +85 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +72 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +51 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    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)
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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