Need easy to understand tutorials on some mathematical concepts used in competitive programming

tutorial
, , ,
1

Hi friends. My name is Abhinav, I’m currently a 9th grade student at Bal Vidya Mandir Highschool. The maths that we had till now was relatively very simple/easy and I couldn’t figure out what type of maths is being used in competitive programming. So far I know some basic algorithmic concepts like DP, segment trees, etc. I am facing problem when we need to have knowledge of some mathematical concepts (like FFT, convex hull, etc). The geometry we have in school is only based on minor concepts like circle, polygons, etc and contains some basic theorems related to them. I see there are many problems related to such mathematical concepts coming up in contests. The only option I am left with is to google those concepts and try searching for the basics but most of the times I end up with only the definition in my hand and not its very explanation. For example, few days ago I was finding some problem to solve and I found out that many had the tag “FFT” to it. I searched it and I looked at many sites for what it is for and its explanation, the only thing I found was it is used to calculate the multiplication of polynomials. It was very hard understanding the working of the algorithm (I even looked up the CLRS book explanation but it was very descriptive and I simply couldn’t understand it). Similar happened with convex hull when I searched it on web.

I request if there are some good tutorials available through which I can understand these concepts very well and they are simple to understand, please mention them. Also, please mention which mathematical concepts I would mainly require for such contests.

@chemthan always have something “mathematical” in his problems. If he answers this, it would be very helpful.

P.S. Please ignore grammatical or spelling mistakes, I’m not that good with English.

7 Likes
2

You are too young :). So don’t be disappointed if you can’t understand them. I started CP when I was 23 :(.

Actually, I haven’t read complete proof of FFT yet! :slight_smile:

I think you should learn what they (that algorithms) will do and how to use them (that I did)! Then when you reach a high level in CP, you go back to understand mathematics behind them.

10 Likes
3

@chemthan I partially agree with you. But @abhishalya is not too young, I would say a bit old :slight_smile: @gennady.korotkevich started at the age of 6. If I am not wrong, his parents were really good teachers and in his 2nd grade, he had 2nd diploma over 9th grade students. At the school, he participated in math Olympiads too. @yutaka1999 won IMO and IOI in 2017, @rng_58 won IMO too.

@abhishalya if you want to be good in math for CP, I strongly recommend you to take part in math olympiads, try to solve problems from old math olympiads. +Practice, practice and one more practice in CP + upsolving.

Tutorials, not everything in the world is easy to understand :frowning:

Google math olympiads and topics related to them

For instance, there is some competitive math contests - http://mathmash.org/ :slight_smile:

7 Likes
4

Hey buddy,
join this slack community to discuss, learn and grow.

https://blancode.wordpress.com/slack-form

Just fill up here to be a part of the discussion. We’re looking forward to it.
NOTE: Unofficial DIV2 May Challenge(2018) Editorials are available on the website right now.

5

Hey @abhishalya this is off topic but how did you come up with this short solution for STMINCUT?
Your code: solution

Can you please explain your solution with proofs?

Anyone is welcome to shed their light on above solution if they got it.

6

Felt good after reading your question. You are a 9th grade student and you already know DP and segment trees and want to learn very advance mathematical ideas like calculus. You also search Google to understand these concepts. You are already ahead of many programmers. I would suggest you to keep searching Google and getting your doubts cleared that way. It would help build the critical life skill of finding answers to problems rather than finding that magical one place solution for every problem. Best wishes. India is improving.

3 Likes
7

You can find a lot of good tutorials on Codeforces.

8

Can you mention some links here? @xrisk

9

@bhushan_ Yes that would be great @xrisk. Also thank you @utkalsinha I will try my best!

10

If u want tutorial for fft,i think this the best to understand:

Whenever u want any tutorial,try finding codeforces,topcoder,codechef related blog,my first preference would be codeforces blogs.

Wished if i Knew about competitive programming at your age :slight_smile:

11 
 But @abhishalya is not too young, I would say a bit old :)

I saw this reply coming eons and eons before this question was born XD XD.

Also, let me give everybody thinking of reading Concrete Mathematics a huge warning. I am personally reading the book, and I must say, do not…I repeat, DO NOT open this book near your exams. It is highly addictive and wont let you focus on your other boring subjects XD.

It made me want to read it so bad despite my exams, my sleep schdule went from 4 hrs to straight 1.5 hrs.

1 Like
12

@vivek_1998299 Thanks for the link. You’re doing great anyways!

13

It was great to hear from you. Would that mean that I just need to give more time then and things would automatically work out?

14

Thanks @mgch. We were not having a computer until I was in 7th Grade :frowning: But I still got a lot more motivation from my brother @bhushan_. He is helping me with some of the problems. I will definitely try out previous IMO problems. Thanks for the info!

15

This is the shortest ever soln I saw for such a question… cool @abhishalya… your code is neat… u r doing really well…