MetB's blog

By MetB, history, 4 years ago, In English

Hi! I know you are already preparing yourself to downvote for questions like "Does math and CP correlate?" or "Why are there math problems on CF lately?" but I wanted to ask something more specific.

My path in competitive programming is built almost entirely with practice problems without relying on things like training camps, virtual contest training and any proper mathematical background. Will, for your opinion, starting math problemsolving almost from the scratch on my level be timewasting/useful/necessary? What is your opinion about practicing MO-type of problems for the sake of competitive programming and if you occasionally have good ways to start mathematical problemsolving (yet I believe it's not about solving problems right off the bat but I might be wrong), please share them.

Thank you all for the answers. Happy New Year!

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

»
4 years ago, # |
  Vote: I like it +38 Vote: I do not like it

I would argue that training on MO problems is probably not the most efficient way to practice. A few thoughts on this:

First, I do think it's fair to say that the level of mathematical knowledge competitive programming expects is substantially higher than the level at which most other topics are tested. A likely reason for this is that many competitive programmers got there start in math olympiads--I spent five years preparing for math contests before I ever heard of programming contests, for example, and continued to do so for four more years before finally switching over to programming competitions entirely earlier this year.

That said, competitive programming generally relies on a relatively small subset of the material tested on math olympiads. For example, olympiad-style geometry almost never comes up, and functional equations are generally irrelevant to programming contests. Most topics in algebra also aren't generally tested at the olympiad level. Combinatorics and number theory are heavily emphasized in programming contests, though even then the problem style is generally different from the type of problems that come up in math olympiads. (As an aside, AtCoder provides the main exceptions to this rule--I recall they've had some synthetic geometry problems in the past, and I remember a recent ABC involving a problem on polynomial interpolation.)

As a result, I think that if you're going to practice problems, you'll probably get more mileage out of practicing math problems from programming competitions than from math olympiads. (This also makes intuitive sense--these will be closer to what you'll see on actual programming contests.) However, it may be that if you don't have much mathematical background, you'll want to find resources to explicitly learn more mathematical theory.

I personally recommend Intermediate Counting and Probability as a source on combinatorics. Number Theory problems generally don't involve much background in the competitive programming context and typically devolve into modular arithmetic bashes, but the sections up to 3.2 (plus, perhaps, 5.1) in this book may be useful. The problems included are probably a little more challenging than the sort of NT that comes up on programming contests.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    But what about such mysterious (for me) and deep thing as general logic skill? I see math people busting competitive programming arena without that much programming knowledge by the "power" of observing, constructing mathematical models, analytically thinking and math intuition. I'm not sure how big this synergy of these topics is but I don't think people are making it so fast and efficiently just by some kind of talent. So I was hoping math preparation would help people gain skill in, say, ad-hoc/observational problems even better more efficient than actually solving such problems, however stupid it can sound. Because, for example, if a football player doesn't have the stamina or strong enough legs, trainers won't usually tell them to just play more football I believe.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I think training general problem solving ability trough math contests is not more efficient than training it through programming contests. Sure, past experience in math olympiads helps to solve programming problems, but it is also the other way around.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      I'll say the cliche, the mysterious problem solving skill comes with just practice, no matter what it is your practicing. The reason these math people can come into competitive programming and use mathematical intuition to help them improve faster is because they have many hours of practice in math. Take Geothermal for instance, who said he practiced 5 years before starting competitive programming. I could be wrong, but if you practiced for 5 years of any competition style problem solving (physics, chem, etc.) I would bet you would gain the "magical intuition" that helps you improve fast and see ad-hoc constructions. All the olympiads, despite being quite different, have similar styles of thinking, so I would think switching from any to any other would be easier than starting one from scratch as you already have the analytical thinking and intuition from practice.

      That said, practicing different variations of competition problem solving style thinking probably does help, but it is likely less efficient unless you are hoping to do well in those contest as well. Maybe just look for problems very similar to the particular style of problems in CP but just going through a list of MO problems for the sake of gaining intuition seems quite inefficient.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can learn ways of thinking and proving stuff. As far as specific knowledge for programming contests goes, I don't think you'd get much out of it since math is much more theoretical. You can learn the math behind a thing you're using, but you can't learn how to use something by studying the theory.