Friend Circle - Hackerrank

Problem Reference - Hackerrank

Problem

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends.
You are given a N×N−matrix M which consists of characters Y or N. If M[i][j]=Y, then ith and jth students are friends with each other, otherwise not. You have to print the total number of friend circles in the class.
Input Format
First line of the input contains an integer N - (size of the matrix), followed by N lines each having N characters.
Output Format
Print the maximum number of friend circles.
Constraints
1≤N≤300
Each element of matrix friends will be Y or N.
Number of rows and columns will be equal in the matrix.
M[i][i]=Y, where 0≤i<N
M[i][j] = M[j][i], where 0≤i<j<N

Here is the code

Thanks

Read More

Lazy Caterer's sequence

Problem
Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that.

Solution

The solution to this is very simple, if you know mathematics. :P

Number of pieces p

p = ( n^2+n+2)/2
p = C(n+1,2) + 1

 
More on wikipedia - http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence.

Proof
When a circle is cut n times to produce the maximum number of pieces, represented as p = ƒ(n), the nth cut must be considered; the number of pieces before the last cut is ƒ(n − 1), while the number of pieces added by the last cut is n.
To obtain the maximum number of pieces, the nth cut line should cross all the other previous cut lines inside the circle, but not cross any intersection of previous cut lines. Thus, the nth line itself is cut in n − 1 places, and into n line segments. Each segment divides one piece of the (n − 1)-cut pancake into 2 parts, adding exactly n to the number of pieces. The new line can't have any more segments since it can only cross each previous line once. A cut line can always cross over all previous cut lines, as rotating the knife at a small angle around a point that is not an existing intersection will, if the angle is small enough, intersect all the previous lines including the last one added.
Thus, the total number of pieces after n cuts is

f(n) = n + f(n-1)

This recurrence relation can be solved. If ƒ(n − 1) is expanded one term the relation becomes
f(n) = n + n-1 + f(n-2)

Expansion of the term ƒ(n − 2) can continue until the last term is reduced to ƒ(0), thus,
f(n) = n + n-1 + n-2 ..... + 1 + f(0)

But f(0) = 1 , because there is one piece before any cuts are made, this can be rewritten as

f(n) = 1 + (1+2+3 + .... n)

This can be simplified, using the formula for the sum of an arithmetic progression:

 f(n) = 1+ n*(n+1)/2 = ( n^2+n+2)/2

Read More

Lego Blocks Problem

Problem statement - https://www.hackerrank.com/challenges/lego-blocks
solution - http://stackoverflow.com/questions/15424945/lego-blocks-dynamic-programming
http://stackoverflow.com/questions/913566/has-anyone-seen-a-programming-puzzle-similar-to-this

Code -

Thanks.

Read More