Basic CP Resources

Getting Started:

Programming Language:

To get start with competitive programming you must be comfortable with at least one programming language. We prefer C++ because it’s more beginner’s friendly and also more useful for programming contests. Here are few topics you must learn before you start programming contest.

Input/Output
Data types
Loop/Nested Loop
If else
Functions
Structure
String processing

Checkout this websites for resource on C++:

Create an account in vjudge:

https://vjudge.net/

Try this easy problems to get used to problem solving:

Comments

NT Part 1:GCD, LCM, Euclidean Algorithm

The definitions of GCD and LCM are well-known, (and taught in middle school I think) I will skip the definitions. Also, since , calculating GCD is equivalent to calculating LCM. Now, how do we calculate the GCD of two numbers? A naive solution would be iterating over all positive integers no more than . This will get the GCD in , very very slow. We can calculate the GCD of in using Euclidean Algorithm. This algorithm uses the easy-to-prove fact , where is the remainder when is divided by , or just a%b. We can now use the following code. #include <iostream> using namespace std ; int gcd ( int u, int v ) { return u % v == 0 ? v : gcd ( v,u % v ) ; } int main ( void ) { int x, y ; cin >> x >> y ; cout << gcd ( x,y ) ; } How do we prove that this algorithm is ? Well, let's suppose that we started with . Then...

NT Part 4: Mobius Function Part 1. The Introduction

What is mobius function? This function is notated as . This function has lots of definitions. However, the main definition is the following. is if or is square-free and has even number of prime divisors. is if is square-free and has odd number of prime divisors. is if is not square-free. also has a lot of interesting properties that make so important. for all , and is multiplicative. (A function is multiplicative if for all . ) How do we calculate fast? Again, we can tweak the Eratosthenes's Sieve a little bit. void preprocess ( void ) { int i, j ; for ( i = 1 ; i <= 111100 ; i ++ ) { mu [ i ] = 1 ; primechk [ i ] = 1 ; } primechk [ 1 ] = 0 ; for ( i = 2 ; i <= 111100 ; i ++ ) { if ( primechk [ i ] == ...

NT Part 5: Mobius Function Part 2. Mobius Inversion, Dirichlet Convolution

Theorem. Let be arithmetic function such that . Then, . Proof. using for all and . The Dirichlet Convolution of two function is the following. Denote as the constant function, . is a function which satisfies and for . is the identity function, The mobius inversion formula and the basic property of mobius functions give , and Okay. So what? How can we use this formula to improve our lives solve problems? We can, change our "sum" or our answer using mobius inversion and mobius functions to calculate them fast. I will give 3 examples which changes the desired sum by using number theory (like mobius function) to calculate them fast. Example Problems Problem 1. http://www.spoj.com/problems/LCMSUM/ Let be the answer when . Precalculate , and add to every . ...

This lifeless coder is welcoming you!

Search This Blog