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

Автор Ashita_no_Kikai, история, 4 года назад, По-английски

Some A,B,C,D from div. 2-3, Educationals have a math nature. So if recognize the math essence, the solution will be written fast, because as I analyses archive these implementation are not hard enough.

That's why the question is what the math core for competitive programming and how to improve level in this one for completely newbie.

I think it's possible to divide the question to two parts. What are recommended literature (можно и на русском) and what resources are good for train exactly mathematics for CP and CF in particular.

Look forward to your advice.

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

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

you can try these ...
FIRST
SECOND
You can check it too..... Third

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

    NICE INFO!

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

There are many material on Maths. I can share some that I know.

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

    Maths problems in Div2 A, B or C are largely dominated by constructive, invariant-finding, number-theory, induction etc.

    Reading Materials:

    1. Arthur-Engel- Problem Solving Stratergies -- I read two chapters from this book and this the best thing I have read till now.
    2. Mathematical Circles — Russian Experience
    3. AOPS Materials
    4. AlgoMuse Reading the solutions after trying hard are quite effective.
    5. CodeNCode Number Theory Playlist
    6. Trev Tutor (Discrete Maths Playlist)
    7. MIT Proofs Course.

    Practice Materials :

    1. We finally have MathForces .
    2. AlgoMuse is also a great way.
    3. AOPS Questions.
    4. Project Euler
»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Of course some basic number theory and combinatorics are necessary, but more important than any specific math topic is mathematical fluency and maturity in general. How good are you with proving? How good is your number sense? How good are you at making insights and observations?

It's not Project Euler over here. Most Div2-3 problems are solvable without much theory. Even a lot of more difficult items only need a handful of standard algorithms. If I were to compose a list of this "standard stuff" off the top of my head, I would mention

  • Modular arithmetic
  • Sum and Product rule (in combinatorics)
  • $$$\mathcal{O}(\sqrt{n})$$$ factorization and primality testing
  • Sieve of Eratosthenes for generating primes
  • $$$\mathcal{O}(\log n)$$$ exponentiation (also maybe matrix exponentiation)
  • Euclidean Algorithm for GCD
  • Methods of computing binomial coefficients
  • DP, in general, for combinatorics