Codeforces Ladder(For Beginners)

I've included 400 problems according to rating & solved count. All the problems are very effective to increase your cp knowledge. I've also included possible tags. So that, you can easily understand if the problem can be solved by you or you've study that theory.

Ladder link: https://docs.google.com/spreadsheets/d/1IIgvJyN2Bzu2bsGrJXdiosLOWGb5OzJRCPayRTdK7rw/edit?usp=sharing

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 6: Sieve of Eratosthenes(Details)

About 2300 years ago from today, famous Greek mathematician Euclid proved that there are an infinite number of prime numbers. Since then people have been searching for these prime numbers. In 1849, one of the greatest mathematician of all time, Carl Fredrick Gauss, had identified almost all of the prime numbers within the first 3 hundred thousand whole numbers. In the age of computers, we can find large prime numbers in the blink of an eye. But to do that, we need to know a bit of programming and a 2000 year old algorithm. By the end of this tutorial, you will be able to figure out a solution on your own to Gauss’s problem. What is a Prime Number? A prime number is an integer number that is divisible by 1 and the number itself only. For example, 7 is divisible by 1 and 7 only. But 6 is not a prime number because 6 is be divisible by 2 and 3 as well. It is worth mentioning that 1 itself is not a prime number. Now if you are asked to determine if a number is a prime number, you can...

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 ] == ...

This lifeless coder is welcoming you!

Search This Blog