Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Ashita_no_Kikai's blog

Necessary math
By Ashita_no_Kikai, history, 4 years ago, In English

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.

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

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

    NICE INFO!

    → Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

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

    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
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      resources 1,2 and 3 that you listed are really awesome. I remember them from MO's.

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

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
→ Reply