Learn to Code

How do I Learn to Code? This is probably the most nagging question at the back of your mind, once you have decided that you want to learn programming. Like learning anything else, there is no standard process for learning to code. Of course there are guidelines, there are courses, there are ideologies and there are set traditions, but there is no one single correct way.

One school of thought which is very popular and fairly simple to begin with is Competitive Programming. Getting started with it is quite easy and if one devotes sufficient amount of time and effort, you can develop a very strong grasp of programming logic in relatively short amount of time.

---

Here are some steps to get started and be good at it.

• Get comfortable writing code in either of one of these languages C, C++ or Java. Why only C, C++ or Java? Because these are the standard languages allowed in any programming competition.
• If you are already good at C, it is suggested to learn C++. It is the most popular language among competitive programmers because of its speed and an excellent library in the form of STL (Standard Template Library).
• Pick an online judge. Recommended ones are Topcoder and Codeforces. These sites have high quality of problems and also allow you to see other’s code post contest completion. These also categorize problems based on the topic. Some other popular judges include SPOJ, CodeChef (powered by SPOJ) andHackerEarth.
• To begin with, start with simple problems that typically require transforming English to code and does not require any knowledge on algorithms. Solving Div 2 250 (Division 2, 250 points) in Topcoder or Div 2 Problem A in Codeforces is a good start.
• At the early stages of programming one tends to write long pieces of code, which is actually not required. Try to keep codes short and simple.
• Practice these problems until you become comfortable that you can submit it for 240 odd points on any day.
• Start implementing basic(or standard) algorithms. It is suggested to read them from Topcoder tutorials orIntroduction to algorithms.

---

Some basic concepts that you should learn are

1. Graph algorithms: Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.
2. Dynamic programming: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.
3. Number theory: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.
4. Greedy: Standard problems such as Activity selection.
5. Search techniques: Binary search, Ternary search and Meet in the middle.
6. Data structures (Basic): Stacks, Queues, Trees and Heaps.
7. Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.
8. Strings: Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.
9. Computational geometry: Graham-Scan for convex hull, Line sweep.
10. Game theory: Basic principles of Nim game, Grundy numbers, Sprague-Grundy theorem.

The list is not complete but these are the ones that you encounter very frequently in the contests. There are other algorithms but are required very rarely in the contests.

You can find description and implementation of standard algorithms here.

• Once you have sufficient knowledge of popular algorithms, you can start solving the medium level problems. That is Div 2 all problems in Topcoder and Codeforces. It is advisable not to go for Div 1 500 at this point.
• Learning to code is all about practicing. Participate regularly in the programming contests. Solve the ones that you cannot solve in the contest, after the contest. Apart from Topcoder and Codeforces you can also look at HackerEarth Challenges or Codechef contests.
• Read the codes of high rated programmers. Compare your solution with them. You can observe that it is simple and shorter than your solution. Analyse how they have approached and improve your implementation skills.
• Read the editorials after the contest. You can learn how to solve the problems that you were not able to solve in the contest and learn alternative ways to solve the problems which you could solve.
• Always practice the problems that you could solve in the contest. Suppose if you are able to solve Div 2 250 and 500 in the contest but not Div 2 1000 then practice as many Div 2 1000 problems as as you can.
• Do not spend too much time if you are not getting the solution or are stuck somewhere.
• After you feel that you have spent enough time, look at the editorials. Understand the algorithm and code it. Do not look at the actual solution before you have attempted to write the code on your own.
• Programming is a very practical and hands on skill. You have to continuously do it to be good at it. It’s not enough to solve the problem theoretically, you have to code it and get the solution accepted. Knowing which algorithm/logic to use and implementing it are two different things. It takes both to be good at programming.
• Programming learning phase is going to take a lot of time and the key is practicing regularly. It takes some time before you can attempt Div 1 500 and other tough problems. Do not give up on reading the editorials and implementing them, even if it takes many hours/days. Remember everything requires practice to master it.

It takes considerable amount of time before you get good at it. You have to keep yourself motivated throughout. Forming a team and practicing is a good choice. Not giving up is the key here.

All about Programming Club

Hi all,

In this blog, I would cover what are the core values of the club and what are our short term targets and the culture that we want to establish at our college.

Core Idea that we practice:

Involve more and more people with Programming

To get the first thing clear, we want to create an atmosphere where more and more students are drawn towards programming right from their first year of college. We believe that if we are to be software engineers for the rest of our lives, why not start loving it from the first year. For achieving this, we want to create enthusiasm among students to start solving problems on their own.

Problems that we face:

1. Not much people take programming seriously, but we make efforts to keep the programming spirits high with regular contests.

People normally are not participating in the programming contests regularly because of lack of time, they don’t think they are good enough or because they have had some bad experiences earlier.

To help with all these issues, we have had two types of contests:

a. Basic Questions contest for beginners: This is for those students who want to start competitive programming, so we create questions that will boost their learning and also encourage them to move forward.

b. Tough Questions to prepare for interviews: In this contest we have questions asked in popular companies and questions that require some logical thinking.

The contests that we create are for learning purposes and we always encourage people to look forward to editorials of the questions asked which are posted in the blog.

2. Female Participation

In the last year, we had five girls representatives to motivate girls to participate in the contests. The move wasn’t much effective and we are still finding some good solution to increasing female participation. It would be a good task for anyone looking forward to being a part of programming club to come up with a good idea to increase female participation in the contests.

3. We don’t have many popular events

Yes we had Interwing programming competition and we started the long programming contest, but still we lack the lime light when it comes to events. We require that there should be some events that people look forward to participate in, maybe have some hackathons or some nice event during Synapse. 

Our Goals:

1. We would like to have our own Judge on Intranet

This would really increase competition among peers and people will look forward to having a good rank at our local intranet website. The downside of this is that some people might take advantage of it if they already have solved such questions earlier or their friend has helped them, but having our contests on the intranet would really help.

2. Improve the blogs, IRC, android application

The blogs would have interview experiences from our Alumnis at DA-IICT, how to prepare for GSoC, learning some new technology, regular editorials of the contest etc.  We must think about how to really involve more people into reading these things.

3. Having contests based on some topic

Suppose if we have some contest only on “Graph Theory”, it would have questions in increasing level of difficulty and have resources for people to learn from. The main aim of any contest is to learn and this would really help as the questions would be of the same topic and in increasing level of difficulty.

4. Have people from 2nd, 3rd and 4th year involved in the club

Last year, we had 3 volunteers from 2nd year and 2 mentors from 4th year apart from the club members of the programming club. Also to increase female participation, we had 5 girls representatives.

There must be people from all the batches as it increases the overall vision of the club and helps in assigning the tasks.

Best Part about the club

The best part for me was that I got to learn a lot from my seniors. All the seniors are quite good at their programming skills and they always help you with things like interviews, exams, increasing your skills etc.

I also believe that when you explain things to other people, your concepts get clear. I guess this has what has helped me during the last two years while being a part of programming club. I feel more confident and have a pretty simple thought process developed due to regular contests and discussion about solutions.

The last thing which I really love is that when you are once a part of programming club, you stay part of programming club forever. I was part of programming club during my 3rd year but I am still involved with the club. I like flaunting the programming club t-shirt and wander wearing the hoodie.

Finally, I look forward to having more inputs from your side as to how we can improve programming club and create the programming culture at DA-IICT.

Write all the suggestions in the comments section.

Link for algorithm of the week

http://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-using-stl-in-c/

Editorial : Coyote & roads

kandarprjoshi

Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/mr-pompom-and-make-tunnel

Explanation :

If you make a graph such that all points on the 2d plane are connected to all other points and find the minimum spanning tree then you will get a valid answer but you can not store (10^5)^2 edges in adjacency list  so you have to think about reducing the edges. There is a trick in a cost function.You want to find at least one edge for every vertex and it is minimum so we just need to consider  four possibilities. First you have to sort all the points with according to  x coordinate and add the edge between all the consecutive points then sort all the points according to  y coordinate and add the edge between all the consecutive points.Then apply typical minimum spanning tree approach on this graph. In sorting make sure that your compare method have  symmetric relation.

View original post

Editorial : Coyote & ACME Bombs

Problem : Removing minimum element from every subarray and count all such subarrays whose sum is divisible by K.

Think over another simple problem of similar kind, without removing any element. That is count how many subarrays’ sum is divisible by K. Then only move forward!

Considering some subarray from some index L to some index R where L < R (strictly less). Suppose minimum element of this subarray is at index M where L <= M and M <= R . It is easy to observe that for the left subarray ([L,M-1]) and the right subarray ([M+1,R ]) will have their own minimum element independent of index M. Thus after solving the problem for any subarray, we have to divide the problem in 2 different independent parts. This will be done with the help of recursion (Divide & Conquer).

Now the issue is how to solve the problem for a particular subarray. In a subarray $[L,R]$ with minimum at index $M$, we have to consider these subarrays:-

1. Subarrays starting at index M and going towards R
2. Subarrays starting at index M and going towards L
3. Subarrays starting at some index x less than M and completing at some index y greater than M. That is L<=x<M<y<=R.

Lets solve them one by one :-

1. Remove the element at index M (bcoz v have to discard element at index M), that is start with element at index M+1 and traverse towards R adding elements one by one and checking at each step whether the sum is divisible by K or not. (can be done using modulo % operator).
2. Similarly, Remove the element at index M, that is start with element at index M-1 and traverse towards L adding elements one by one and checking at each step whether the sum is divisible by K or not. (can be done using modulo % operator).
3. This one is interesting. For finding these kind of subarrays, we could take help from the above two subarrays. Lets assume that there are u subarrays starting at index M and going towards index L having reminder r (when divided with K). Also say there are v subarrays starting at index M and going towards index R having reminder K-r. Each pair of these subarray also forms a subarray eligible to be counted. (Why ? If you merge two subarrays having reminder $2$ and $K-2$, the merged subarray will have reminder 0). Thus the answer would be u*v.

After solving for a subarray, one has to call two recursion calls. The time complexity of this problem would be like Quicksort where u divide the subrray into 2 segments and the extra time other than recursion is O(n) (bcoz u have to traverse each segment to save reminders into some map).

U will have to read the solution now after understanding these key points!

The link to the solution is

http://ideone.com/S5fPvC

If u have any queries or doubts, feel free to comment or contact our team!

Editorial Fitness Freak Coyote

Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote

In this question there are two types of query.

1. Add number in your data structure
2. Return number whose rank is floor of n/3

And both query come at any instance of time.

So we can use Balanced Binary Search Tree. But that take O(log n) time complexity in both query.

The better approach is use two heaps.

Create a min heap of size n/3 and create max heap of size 2n/3

So for the second query we give minimum element from the min heap whose rank is floor of n/3

which takes time O(1).

For the first query there can be four cases occur.

-If size of min heap is less than floor of n/3 this is due to increase in n.

in this case we will add that number in the min heap and than compare min of min heap and max of max heap

If max of max heap is greater than min of min heap than we will swap this two elements.

-If size of min heap is equal to floor of n/3

In this case just add it in the max heap.

So the time complexity of this is  O(log n)

Java implementation code

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote/submissions/code/3618642

Editorial : Coyote and SuperVyas

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-supervyas

Explanation :

Let’s start from a slow solution first.

Coming to think about it, you are asked to place X1 in 2nd free cell of your answer, then to place X2 in 3rd free cell of your answer while starting counting from position where you had placed X1 (and starting from the beginning if you reached end of array), then to place X3 in 4th free cell, and so on. It is quite easy to understand why it works – rotating deck around your pointer and rotating pointer around deck in opposite direction is basically same thing.

Now add one more optimization. At every moment you know how many free cells are in your array now. Assume you are at position X now, need to move 20 free cells forward, and you know that at given moment there are 2 free cells before X and 4 free cells after X. It means that you need to find 22nd free cell starting from beginning of array, which is same as going full circle 3 times and then taking 4th free cell. As you can see, we moved to a problem “find i-th zero in array”.

Naive solution is still O(N^2), but it is fast enough to pass and still have a very easy implementation!

However, you can speed it up.

Problem “find k-th 0 in array” is well-known. N*log(N) solution with segment tree: for every vertex store number of 0’s in given range. Start from root and move down to a leaf; at every vertex you know where you should go by looking at number of 0’s in left and right subtree. Suppose you need 5th 0 in range, and there are 8 of them in left subtree and 7 of them in right subtree. It is obvious that you need to move into left subtree and look for 5th 0 there. And what if you need 12th 0? In such case you have to move into the right subtree – but don’t forget that you’ll be interested in 4th 0 there, not in 12th (because of 8 more 0’s in left subtree).

N*log^2(N) solution with small hidden constant using Fenwick tree: use binary search to find minimum X such that there are at least Y 0’s among first X elements, it will give you position of Y’th 0 in given array.

You can also use BIT to store the number of free spaces on the left and right of every index.

Setter’s Code : http://ideone.com/9GKD4F

Editorial : Coyote and his balls

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-balls-p

Required Knowledge : naive logic

Explanation : There are 2 possible solutions to this problem but the logic in both is the same. Consider we have been given n balls. Now we do 1 comparison using weighing pan. Here we divide the balls into 3 parts which are approx 1/3rd of n.                For  3n balls – n,n,n ; for 3n+1 balls – n+1,n,n ;  for 3n+2 balls- n,n+1,n+1 . We compare the last 2 parts using weighing pan. If they are equal, then the non-identical ball lies in the 1st part. If they are not equal, the non-identical ball lies in the pan which was lighter of the two. So effectively we reduced the problem into 1/3rd its size. So if we go on doing this, we will require log n(base 3 ) – ceiling comparisons. This is one possible solution.                                                                                                                         The second possible solution is a recursive method. Let ans() be the recursive method. The two base cases are n=1 and n<=3 for which the answers are 0 and 1 respectively. For n%3==0 , we divide into 3 parts each having n/3 balls. Therefore we return  ans(n/3) + 1 . If n%3 !=0 in worst case we will have to look at (n/3)+1 balls. Hence we return ans(n/3 +1 ) +1 and not ans (n/3 ) +1.

Setter’s  solution: http://ideone.com/e.js/lgvYbc        (This one uses recursive method)

Tester’s Solution: https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-balls-p/submissions/code/3630098                                          (This one uses log to base 3 method)

For any doubts feel free to contact me on 201401114@daiict.ac.in.

 

Editorial : Coyote and his enemy Daddu ji – 2

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-enemy-daddu-ji-2

Required Knowledge : Segment Tree(https://en.wikipedia.org/wiki/Segment_tree), Binary Search(https://en.wikipedia.org/wiki/Binary_search_algorithm).

Explanation : 

You are given n numbers and an integer k, you are asked to find the length of minimum sub-array whose gcd is k. If any number is k then the answer should be 1 as that sub-array will have gcd k and length 1 which is the minimum. Now what to do if no number is equal to k. We need to find all the sub-arrays whose gcd is k. Let us now declare a minimum variable whose value is more than n. Now start with index 1, we will now find the gcd of sub-array 1 to (n/2)index using segment tree. If gcd is = k we, we store the minimum of the length of the found sub-array and the original value of minimum in minimum. minimum = min(minimum, length of found sub-array). If gcd is greater than k then we will get the sub-array with gcd k further as moving back will give gcd more than k. So now binary search b/w n/2 and n. Similarly if gcd is less than k, we will either get gcd k b/w index 1 and n/2 or we will not get any sub-array with gcd k. So now finding gcd of a sub-array will have time complexity of O(logn) and binary search will also happen in log(n). Therefore for each index total complexity of O(logn*logn). Since there are n index we need to find for all, therefore the required complexity of the solution is O(n*(logn)^2).

Now if value of minimum is equal to the assigned value in the beginning, print -1 else print minimum.

Some useful links on segment tree :

http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

http://www.cse.iitk.ac.in/users/aca/lop12/slides/06.pdf

https://proclubdaiict.wordpress.com/2015/01/25/segment-trees/

Setter’s Solution : http://ideone.com/wqVgEI

For any doubts you can contact me at 201301151@daiict.ac.in or message me on Facebook (https://www.facebook.com/nikhil.tekwani.18).

Editorial : Coyote and his enemy daddu ji

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-his-enemy-daddu-ji1

Knowledge Required : Finding a^b in time complexity of O(logb) rather than O(b).

Explanation : 

A = a*m;

Therefore A is multiple of m and A%m = 0;

Similarly, after carefully looking B and C. They are the multiple of m as well. Therefore the equation f(i) = (i^i + Ai^4 + Bi! + C((i^i)^i))*(f(i−1)) reduces to f(i) = (i^i)*f(i-1) on finding f(i)%m as A%m, B%m and C%m = 0. So now the question is to find f(i) = (i^i)*f(i-1).

if(n>=m) the ans is 0 because while running loop upto n we will have to compute m^m whose modulo with m comes out to be 0, thus making the entire function 0 as 0*something is 0.

Therefore we have to run the loop maximum upto m-1 if n is less than m.

For each i the time required is log(i) and the loop will run upto n. Therefore time complexity O(nlogn).

The editorial to find a^b in logb can be found here http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/.

Setter’s solution : http://ideone.com/8iPMcf

For any doubts you can contact me at 201301151@daiict.ac.in or message me on Facebook (https://www.facebook.com/nikhil.tekwani.18).

Editorial : Corote And Queries

Coyote And Queries:

Problem Link: https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-queries-2

Problem In Short: Give an array, you have to answer many queries on it. For each query, you need to output the number of distinct integers whose frequency from L to R >= ceil((R –L+1)/3).

Offline Approach: Simple application of Mo’s Algorithm. You create another count array such that count[c] stores number of integers which frequency >= c. Refer to any solution which has got 100 points in Coyote And Queries 1 for this.

Online Approach:  For Coyote And Queries 2, online solution was needed.

First we would create one frequency array, such that freq[i] stores number of intgeres in array equal to i.

Let us define a term heavy element.

For each 1 <= I <= 10^5, if freq[i] >= SquareRoot(N), then i is a heavy element.

Total Number of heavy elements must be <= SquareRoot(N). Think about why this!

Each query can be categorized in two parts.

1. R – L + 1 >= 3 * squareRoot(N)
2. R – L + 1 < 3 * squareRoot(N)

Queries of type (b) can be solved in O(R – L + 1) = O(squareRoot(N)) using brute force. However creating a map, would increase the complexity by one log factor, which would not be enough to get 100 points. But because A[i] <= 10^5, you can create a single 10^5 size global array and use it for each query of this type. For details, look at the reference solution.

For queries of type (a) , R – L + 1 >= 3 * squareRoot(N) implies C = ceil(S/3) >= squareRoot(N). But only heavy elements have frequency >= squareRoot(N). Hence, you only need to check heavy elements. AS said earlier, total number of heavy elements is <= squareRoot(N). So for each element , you check its frequency from L to R and if frequency >= C, ans++. However, again using some sort of binary search or segment tree data structure to calculate frequency for each heavy element would increase complexity by a log factor. But because there are no updates, you can create a prefix array for each heavy element.

Prefix[i][j] = number of times heavyElement[i] occurs in [1,j].

So , for each heavy element, frequency in [L,R] = prefix[i][R] – prefix[i][L-1].

Hence, O(SquareRoot(N)) per query.

P.S. There was a hacky 100 points AC solution with segment tree but it’s not correct, so don’t refer to it.

Hence, total Complexity = O(N * sqrt(n) + Q * sqrt(n))

Make sure you look at the reference solution to learn few tricks on reducing one log factor.

Reference Solution: https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-queries-2/submissions/code/3671816