Skip to main content

Competitive Programming

By

Competitive programming is a mind sport usually held over the Internet or a local network, involving participants trying to program according to provided specifications. Contestants are referred to as sport programmers. Competitive Programming mainly focuses on our ability to find efficient solutions to well-defined problems.

Usually, a question arises - Why Competitive Programming?

Many of the top tech companies like Google, Facebook hire people through a test which includes competitive programming. Also, participation in the ACM International Collegiate Programming Contest (ACM-ICPC) is a great opportunity to be seen by Apple, Facebook, Google, IBM and many other authorities in the IT sphere. These major companies are constantly keeping track of the participants to find talented employees.
Having experience in competitive programming shows employers you can work in a team, solve complicated problems, work in stressful situations, manage time and deadlines and minimize errors. It also shows you are a disciplined, focused and fast, which are all indispensable skills.

It is also useful in College Intern/Placement test, which includes a few questions on Basic Data Structures and Algorithms

If you are interested in Competitive Programming and confused about how to start and how to proceed, you can have a look here.


Prerequisites

  • Be very comfortable with any one of the programming languages (preferably C, CPP, Java or Python). However CPP is more preferred for competitive programming due to its faster execution time and many inbuilt data structures.
  • Understand the concept of Algorithmic Complexity and study Bit Manipulation Techniques.


How to begin??


Register on some programming websites like HackerEarth, HackerRank, Codeforces, SPOJ, TopCoder etc.., start with basic programming questions to get a hang of competitive programming environment and then proceed to various data structures and algorithms.

Competitive programming is basically divided into three main categories:
  1. Data Structures
  2. Algorithms
  3. Mathematics

Basic Data Structures:

1. Arrays
6. Hash tables
2. Stacks
7. Heaps
3. Queue
8. Priority Queue
4. Linked Lists
9. Graphs
5. Trees
10. Disjoint Data Structure

Resources:




Basic Algorithms:


1. Searching
5. Divide and Conquer
2. Sorting Algorithms
6. Backtracking
3. Greedy Algorithms
7. Dynamic Programming
4.Graph Algorithms   (DFS,BFS,Dijkstra)

Resources:




Basic Mathematics:

1. Modular Arithmetic
5. Sieve of Eratosthenes
2. Modular Exponentiation
6. Extended Euclidean Algorithm
3. Modular Multiplicative Inverse
7. Prime factorisation in O(sqrt(N))
4. GCD/LCM in O(LogN)

8.Bases

Resources:





Practice Websites


Apart from these, Codeforces conducts frequent contests, HackerEarth conducts 3 monthly contests namely Easy, HourStorm and Circuits and Codechef also conducts 3 monthly challenges namely Long, Cook-Off and Lunchtime. Try competing in those contests and upsolve the unsolved problems at the end of contest.

The resources listed below contains books, courses, blogs for all the advanced algorithms, data structures and math concepts.



Some Common Advanced Data Structure and Algorithms include

1. Segment Tree
11. DP + Bitmasks
2. Binary Indexed Tree
12. Strongly Connected  Components
3. Sparse Table
13. Bipartite matching
4. Trie
14. Network flow
5. Suffix Arrays
15. Combinatorics
6. Suffix Trees
16. Line Intersection
7. Treap
17. Convex Hull
8. String Algorithms
18. Geometry
9. Heavy-light decomposition
19. Inclusion- Exclusion Principle
10. MO’s Algorithm
20. FFT

Labels:

Comments

Post a Comment

Popular posts from this blog

Git : Todo and not Todo : Part-2

By
Hello there! This is the second part to introduction to git. If you have not read the first part then please first go through that first, as proceeding along here without that introductory knowledge will not be really helpful.Here is a link TL;DR All the git commands that we will be talking about, now and later-: git init git clone git add git commit git status git remote git push git pull git fetch git branch git reset So, lately we learnt about Version Control Systems also abbreviated as VCS and got to know about git and how it is completely different from github and other VCS hosting websites. In this part we will be looking on the more practical part of using this wonderful tool and also why we should learn it very first in our development career. Later, I will also help you understand that git is just a small part of the entire development career that you aspire to make and why it should not be considered just more than a medium to share your code with...
2 comments
Read more

A beginners guide to NumPy

By
The previous post took you through the basics of machine learning using python with scikit-learn and tensorflow, this post will give you a brief introduction to Numpy. NumPy is a python package which stands for "Numeric Python". It enables you to do mathematical computations easily and effectively hence making coding simpler. http://www.numpy.org/ Installing via pip: After having python3 and pip installed, installing packages can be done using the following command on windows cmd. >>> python - m pip install -- user numpy scipy matplotlib ipython jupyter pandas --user   makes pip install packages in your home directory instead, which doesn't require any special privileges. Import Numpy: >>> import numpy as np Now we use np as a reference to numpy in the code. Numpy arrays: Create a numpy array of type np.ndarray: >>> A = np.array([[1,2,3],[4,5,6],[7,8,9]]) Create a numpy array containing ones/...
Post a Comment
Read more

Git : To do and Not To do: Part- 1

By
Git is a version control system that helps to maintain versions of your work over time. The above line may seem a bit overwhelming to read at first, as there are words which most of us not really understand as of now. Just read along and I will help you in getting some idea of why git is a resource every developer has to be sound with and why it is a integral part of every developer's everyday life. A version control system :- We all have heard the saying that Rome was not built in a day and believe me, if it is not your college assignments , no great app was ever built in a day or at least without using a VCS( version control system). Every app has multiple sections. Every section require some skills that is used to develop it. A skill may come under a set of skill that a contributor has.  When we work alone or in a group with other developers, making any single project, it tends to happen that people take up sections that they are good at, as they believe that they can contri...
Post a Comment
Read more