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.

Advertisements

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!

How to solve competitive programming questions with ‘Queries’?

Many questions in competitive programming are based on update and find queries.

For e.g. given an array of N elements and Q queries. Each query has L and R and you need to print the minimum array element from a[L] to a[R]. N = 10^5, Q = 10^5, 1 <= L <= R <= N. If you do it naïve it way, it would take O(N*Q) which would give TLE.

Basically, there are two types of approaches for solving such type of questions.

Online approach:

You just print the answer for each query instantaneously in the order they appear in input.

Offline approach:

You input and store all queries, sort them according to some comparison function, solve all in sorted order, output answer for all queries in order they appear in input.

Online approaches:

  • PreOrder Array:

Create another array pre[] , where pre[i] stores information about [0,i]

For eg, you need range sum from L to R in each query quickly.

Solution: Create preorder array, where pre[i] = sum from 0 to i = pre[i-1] + a[i]

So, for each query, answer = pre[R] – pre[L-1].

But this is a static structure and it doesn’t work when you need to update array elements.

  • Segment Tree: This is the most useful data structure for this type of questions.

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://en.wikipedia.org/wiki/Segment_tree

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

Segment Tree with lazy propagation: (For range update queries)

https://discuss.codechef.com/questions/38770/lazy-propagation

http://stackoverflow.com/questions/11765838/how-to-implement-segment-trees-with-lazy-propagation/30622980#30622980

  • Binary Indexed Tree/Fenwick tree :

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

http://www.sanfoundry.com/java-program-implement-fenwick-tree/

http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

  • Square Root Decomposition :

http://www.quora.com/How-does-the-technique-of-sqrt-N-decomposition-work-and-in-what-kind-of-problems-is-it-useful

  • Disjoint Set Union :

https://proclubdaiict.wordpress.com/2015/06/11/disjoint-set-data-structure/

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Offline Approaches:

  • Reverse Process Queries:

Process queries in from last to first. For example, if query is to delete something, solving queries in reverse order, it becomes insert instead of delete. This approach helps when inverse operation is easier to process then normal query operation.

https://www.codechef.com/MARCH15/problems/MTRWY (Do read editorial for it.)

  • Sorting queries based on their ‘R’. R = right end of range query (L,R)

Question: http://www.spoj.com/problems/DQUERY/

Solution: http://codeforces.com/blog/entry/8962

  • Mo’s Algorithm:

http://blog.anudeep2011.com/mos-algorithm/

Editorial : Mr. Pompom goes Bizarre!

Problem in short: Given a 2-D grid of size r*c which has some obstacles, one exit point and few enemies. For each query, you start from a different starting point and you have to output minimum number of enemies which you meet in the way if you choose your path optimally (not necessarily shortest path). Also after each step you take, all the enemies also take 1 step. Steps are only in horizontal and vertical direction and you cant step on obstacle. You leave the grid if you step on the exit point. Also enemies know the path you are going to take in advance so they will make their moves accordingly.

Problem Link: https://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-goes-bizarre

Lemma 1: If some enemy meets you in between the path from starting point to exit point, then he will also meet you at the exit point.

Proof: Let’s say the some enemy meets you at some cell on your path from starting path to exit point. Then he will take moves with you till the exit point and so he will surely meet you at the exit point as well.

Lemma 2: You always take shortest path to exit point.

Proof: If he can reach before you on the shortest path and meet you there, then he can also reach before you on the exit point as well. So if you take any longer path, he will wait at the exit point for you to come. Hence, you will surely meet him at the exit point as well.

Lemma 3: All enemies also always take shortest path to exit point.

Proof: If enemy can meet you at any path other than shortest path, then he can take shortest path and wait at exit point till you come and meet you there.

Assertion: Using these three lemmas, you can state that you only need to count the number of enemies which reach before you to the exit point in each query, if everyone takes shortest path.

How to find shortest path? If you find shortest path in each query, then your complexity would be O(q*r*c) because finding shortest path takes O(r*c) time. This would give only 25% points when q = 1.

Observation: For each of the shortest path, exit point is fixed. So you can find shortest path from exit point to all other cells in the grid and store them in 2-D array using single source shortest path algorithms (here BFS would also work as edges don’t have weight). For that you can imagine the grid as a graph with r*c vertices with edge from (a,b) to (c,d) if they are horizontally/vertically connected and grid(a,b) != obstacle and grid(c,d) != obstacle.

Now for each query you can do a O(max Enemies = 20) loop, and find how many enemies have shortest path then shortest path from starting point to exit point. That would be the answer.

Setter’s Solutionhttps://www.hackerrank.com/contests/da-iict-ipc-01/challenges/mr-pompom-goes-bizarre/submissions/code/3489972

Challenge Question: What if the number of no. of max enemies <= r*c instead of max enemies <= 20? Comment below if you find solution for this :).

Disjoint Set Data Structure

There are 10 individuals a, b, c, d, e, f, g, h, i, j. Now the task is to find whether individual x is a friend of individual y (direct or indirect friend), given a list of friends

a->b

b->d

c->f

c->i

j->e

g->j

Therefore now we have 4 groups:

G1 = {a, b, d}

G2 = {c, f, i}

G3 = {e, g, j}

G4 = {h}

Task is to find whether individual x and y belong to same group or not.

We will solve this problem by partioning the individuals into different sets according to the groups in which they fall. The above method is known as disjoint set data structure which maintains collection of disjoint sets and each set is represented by its representative which is one of its members.

Initially every individual belongs to different sets and is representative of its own set. After working on the given relation the member with the biggest index becomes the representative and the other sets are resolved (Eg: Initially ‘a’ and ‘b’ belong to different sets but later on b belongs to set a and the set b is resolved).

Now you must be wondering that how you can check if 2 persons are in the same group. This is where the use of representative comes into place. For example: If we want to check whether ‘b’ and ‘d’ are friends, we will check the representative of both ‘b’ and ‘d’ which is ‘a’ and ‘a’ respectively which is equal, therefore ‘b’ and ‘d’ are friends. On the other hand if we wanted to check whether ‘b’ and ‘g’ are friends, we will note down their representatives which are ‘a’ and ‘e’ respectively which is not equal, therefore ‘b’ and ‘g’ are not friends.

In its simplest form, the data structure is just an array of integers, called parent. If we are dealing with n items, then parent is an array of size n, and the ith element of the array represents the ith item. More precisely, the ith element of the array is the parent of the ith item. These relationships create one, or more, virtual trees.

Each tree is a disjoint set. If two elements are in the same tree, then they are in the same disjoint set. The root node (or the topmost node) of each tree is called the representative of the set. There is always a single unique representative of each set. As you can see, if i is the representative of a set, then parent[i]=i. If i is not the representative of his set, then it can be found by traveling up the tree until we find the representative.

Find operation of the Disjoint-set data structure, and can be implemented with the following recursive code.

// Finds the representative of the set that i is an element of

public int Find(int i) {

    // If i is the parent of itself

    if (Parent[i] == i) {

        // Then i is the representative of this set

        return i;

    }

    else { // Else if i is not the parent of itself

        // Then i is not the representative of his set,

// so we recursively call Find on its parent

        return Find(Parent[i]);

    }

}

 

Now that we’ve implemented the Find operation, the Union operation is simple to implement. It takes, as input, two elements, finds the representatives of their sets using the Find operation, and finally puts either one of the trees (representing the set) under the root node of the other tree, effectively merging the trees and the sets.

Implementation of Union operation:

// Unites the set that includes i and the set that includes j

public void Union(int i, int j) {

    // Find the representatives (or the root nodes) for the set that includes i

    int irep = this.Find(i),

        // And do the same for the set that includes j

        jrep = this.Find(j);

    // Make the parent of i’s representative be j’s representative

// (effectively moving all of i’s set into j’s set)

    this.Parent[irep] = jrep;

}

 

There are still a couple of things we can do to greatly improve the efficiency of the data structure. The efficiency depends heavily on the height of the tree. Let’s have a look at two methods to minimize the height of tree in order improve the efficiency.

Path Compression

Our first improvement is very simple, but also very effective. It’s called Path Compression, and speeds up the data structure by compressing the height of the trees on the fly. That can be achieved by inserting a small caching mechanism into the Find operation. Take a look at the code for more details:

// Finds the representative of the set that i is an element of

public int Find(int i) {

    // If i is the parent of itself

    if (Parent[i] == i) {

        // Then i is the representative of his set

        return i;

    }

    else { // Else if i is not the parent of itself

        // Then i is not the representative of his set,

// so we recursively call Find on it’s parent, and save it in our result variable

        int result = Find(Parent[i]);

        // We then cache the result by moving i’s node directly under the representative of this set

        Parent[i] = result;

        // And then we return the result

        return result;

    }

}

 

Our previous improvement changed the Find operation to make the heights of the trees smaller. This improvement, called Union by Rank, changes the Union operation to also make the heights of the trees smaller. First of all, we need a new array of integers called rank of the same size as the parent array. Then, if i is a representative of a set, rank[i] is the height of the tree representing the set.

Now recall that, in the Union operation, it doesn’t matter which of the two trees is moved under the other (see last two image examples above). Now what we want to do is minimize the height of the resulting tree. If we are uniting two trees (or sets), let’s call them left and right, then it all depends on the rank of left and the rank of right. If the rank of left is less than the rank of right, then it’s best to move left under right, because that won’t change affect the rank of right (while moving right under left would). In the same way, if the rank of right is less than the rank of left, then we should move right under left. If the ranks are equal, it doesn’t matter which tree goes under the other, but the rank of the result will always be one greater than the rank of the trees.

Modified union operation code:

// Unites the set that includes i and the set that includes j

public void Union(int i, int j) {

    // Find the representatives (or the root nodes) for the set that includes i

    int irep = this.Find(i),

        // And do the same for the set that includes j

        jrep = this.Find(j),

        // Get the rank of i’s tree

        irank = Rank[irep],

        // Get the rank of j’s tree

        jrank = Rank[jrep];

    // Elements are in the same set, no need to unite anything.

    if (irep == jrep)

        return; 

    // If i’s rank is less than j’s rank

    if (irank < jrank) {

        // Then move i under j

        this.Parent[irep] = jrep;

    } // Else if j’s rank is less than i’s rank

    else if (jrank < irank) {

        // Then move j under i

        this.Parent[jrep] = irep;

    } // Else if their ranks are the same

    else {

        // Then move i under j (doesn’t matter which one goes where)

        this.Parent[irep] = jrep;

        // And increment the the result tree’s rank by 1

        Rank[jrep]++;

    }

}

 

I have made the entire disjoint set data structure class at http://ideone.com/gW4iO9.

Try to solve the problem http://www.codechef.com/problems/CD1IT5 and check how much you learnt and do comment on the complexity of the given question.

You can also visit http://en.wikipedia.org/wiki/Disjoint-set_data_structure if you want to learn more in detail.

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