Editorials - C For Code 03 - Coding Club - ISM Dhanbad

Fear of Three for Ross

It was a cake walk problem. Just keep three variables A, B and C for storing the three maximum numbers. Initially all of them should be 0. Then for every number X, do this:

If X is greater than or equal to A { C=B; B=A; A=X; }

Else if X is greater than or equal to B { C=B; B=X; }

Else if X is greater than C { C=X; }

Here is the solution to this problem:

http://www.codechef.com/viewplaintext/2426781

Joey is Confused

Prerequisite: Combinatorics, Dynamic Programming

Let C(n,k) denotes the number of combinations of k elements that we can get from n elements.

Then,

C(n,k) = C(n-1,k) + C(n-1,k-1)

So, take a 2-D array (say “arr”) of size 1000 X 1000, initialize the cases with n=0 or k=0, and then for all the remaining values, used this Dynamic Programming Formula:

arr[i][j] = ( arr[i-1][j] + arr[i-1][j-1] ) % MOD

Here is the solution to this problem:

http://www.codechef.com/viewplaintext/2426794

Joey the President:

Prerequisite: Union Find Algorithm

Please read the following link to read about the Union Find Algorithm:

http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

This algorithm is really powerful when we want to group elements into some disjoint sets based on a property. It connects the elements that are in the same group in the form of a tree. So each group has a unique root, with the property

Parent[i] = i

So we count the number of nodes with this property, i.e, parent[i]=i

Counting this gives the number of different connected components in the graph.

Here is the solution to this problem:

http://www.codechef.com/viewplaintext/2426861