Competitive Programming #2
The beginner’s guide for competitive programming part2
This is in the continuation of first part https://medium.com/@rushabhdaxini/competitive-programming-c0de24674c24 (Just introduction to the CP and some language, verdicts etc)
Now, in this blog I will dive in some depth because after all talk is cheap, let’s speak in code now. Basically, it all stars with array when it comes to first code (after cout<<”Hello World!”;)On the other note, I will be using CPP all the time so be prepared to talk in CPP now.
Arrays:
I assume we all know array, very simple! It is nothing but collection and array is limited by some predefined size in cpp it is declared as,
__datatype __nameofarray[__size];
But let’s come to the point array is limited by size(again!). So as a coder, you don’t want to take care of size always. Specially when it comes to codeforeces 2hour contest, we need speed. So it would be better if you use all your brain to make logic rather than counting maximum size of the array.
So, from now we will use vector (in JAVA it is called ArrayList) which is dynamic kind of array where you are not required to predefine the size of the array, just declare it and use it as needed! for example int vector would be declared as,
vector<int> a;
There are many various things that can be added along wih vector like it can be in pair or pair of pair or so on it can have any datatype within (also new defined datatype as well)
vector<pair<int,string>>v; v.push_back(make_pair(1,”Rushabh”));
Stack and Queues:
CPP is having both of them defined in STL so it can be used directly and very easy to use also,
for demonstration of queue, letme first introduce a common algorithm used many times in CP, BFS(Breadth First Search) it uses queue.
Get Rushabh Daxini’s stories in your inbox
Join Medium for free to get updates from this writer.
A sample problem is, given a binary maze(0/1 matrix of size NxM) and we want to traverse from [1,1] to [N,M] using only [1,1]. Output whether path is possible or not(very easy level problem!) we can move right or down only in the given maze.
The solution is not verified as it is written in hurry but it follows BFS algorithm and traverse each possible path from current node and if current node is same as destination node, break the code and print path is possible else not possible!
Binary Search:
Very easy in terms of explanation but it is used hell lot of times in CP to reduce time complexity of the code. Binary search is very easy to understand but it becomes very difficult to think how to use it in your code to make it more optimized. Few lines for binary search,
To find particular element from the array we can use linear search (traverse whole array and compare all the elements with X =>O(N)). On the other hand binary search can do this stuff in O(logN) by searching it and reducing size of search area by 2 each time.
Importance of binary search is demonstrated with my solution on codechef for problem CCIRCLES .
There are N circles in a plane. Circle i and circle j form a good pair if it is possible to choose a point P1 on the perimeter of circle i and a point P2 on the perimeter of circle j such that the Euclidean distance between P1 and P2 is exactly K. (Note that P1 and P2 do not need to have integer coordinates.) You should answer Q queries. In each query, you are given the required distance K. Chef is interested in finding the number of good pairs of distinct circles for each query. Please help him.
My solution: https://www.codechef.com/viewsolution/20960220 do let me know if solution isn’t clear enough!
