A grid of size N rows and M columns is filled with numbers, one in each cell. You start at the centre of the cell at the top-left corner (1,1) and your destination is the centre of the cell at the bottom-right corner(N,M). In each step, you are only allowed to move to the centre of the cell to the right or to the centre of the cell to the bottom. There are many paths you can take to reach your destination from your start – however, every path can be uniquely broken down into a series of straight line-segments joined at right-angles. Each straight line-segment in your path is termed a ‘leg’ of your path.
Your task is to choose a subset of the cells along your path in such a way that the sum of the numbers in the chosen cells is maximized. Your choice of cells must be such that exactly one chosen cell is present on each leg of the path. Note that cells at the intersection of two legs belong to both legs. What is the maximum possible sum you can form?
Input Format:
The first line contains one integer T, the number of testcases. The first line of each test case contains two space-separated integers N and M. Each of the next N lines contains M space separated integers, denoting cell values. The jth integer in the ith line denotes the value of the cell (i, j).
Constraints:
1 <= T <= 10
1 <= N, M <= 100
Numbers in each cell will be between -10000 and 10000 inclusive.
Output Format:
For each testcase output a single line containing the maximum sum you can form.
Sample Input:
3
2 2
-1 -2
5 -1
3 4
-1 2 -3 -4
-2 -3 5 -2
-1 -1 -2 3
2 2
3 1
5 3
Sample Output:
5
10
6
Explanation:
In the first test case, you can first move down and then move right. Your path now has 2 legs and you can choose only the cell containing 5. This is valid as it satisfies the condition that you must choose exactly one cell in each leg (because 5 is a part of both legs).
In the second test case, one best path is to walk right, choose 2, go right again and then down to choose 5, go further down and then right to pick up the final 3 (There are also other ways to pick-up the same numbers).
In the third test case, the best path is either (down, right) or (right, down). Note that since you can pick-up only one number in each leg you cannot select the ’5′ in the lower left corner (If you decide to pick-up 5, then you cannot pick up any other number because ’5′ is shared by both legs. We can do better by selecting both 3s).
Time limit: 2 seconds
Memory: 64 MB
ACM International Collegiate Programming Contest, 2010, Asia-Amritapuri Site
Solution ( Source : Team Imperials )

01	/***** Author : Kunal *****/

02	#include <iostream>

03	#include <cmath>

04	#include <cstdio>

05	using namespace std;

06

07	#define REP(a,b) for(int a=0;a<b;a++)

08	#define FOR(a,b,c) for(int a=b;a<c;a++)

09	#define FORD(a,b,c) for(int a=b;a>=c;a--)

10

11	#define S scanf

12	#define P printf

13

14	#define INF 1000000000

15

16	int A[102][102];

17	int rmax[102][102][102];

18	int cmax[102][102][102];

19

int n, m;

20

21	void findRowMax()

22

{

23	REP(i, n ) REP(j, m ) REP(k, m ) rmax[i][j][k] = -INF;

24	REP(i, n )

25

{

26	REP(j, m )

27

{

28	rmax[i][j][j] = A[i][j];

29	FOR(k, j+1, m ) rmax[i][j][k] = max( rmax[i][j][k-1], A[i][k] );

30

}

31

}

32

}

33

34	void findColMax()

35

{

36	REP(i, m ) REP(j, n ) REP(k, n ) cmax[i][j][k] = -INF;

37	REP(i, m )

38

{

39	REP(j, n )

40

{

41	cmax[i][j][j] = A[j][i];

42	FOR(k, j+1, n ) cmax[i][j][k] = max( cmax[i][j][k-1], A[k][i] );

43

}

44

}

45

}

46	int dp[102][102][2][2];

47	int main()

48

{

49	int t; S("%d", &t );

50	while( t-- )

51

{

52	S("%d%d", &n, &m );

53	REP(i, n ) REP(j, m ) S("%d", &A[i][j] );

54	findRowMax(); findColMax();

55	REP(i, n ) REP(j, m ) REP(k,2)  dp[i][j][k][0] = dp[i][j][k][1] = -INF;

56	REP(i, m )

57

{

58	if( i-1 >= 0 ) dp[0][i][0][0]  = rmax[0][0][i-1];

59	dp[0][i][0][1] = A[0][i];

60

}

61	REP(i, n )

62

{

63	if( i-1 >= 0 ) dp[i][0][1][0]  = cmax[0][0][i-1];

64	dp[i][0][1][1] = A[i][0];

65

}

66	FOR(i, 1, n )

67

{

68	FOR(j, 1, m )

69

{

70	REP(k, j )

71

{

72	dp[i][j][0][0] = max( dp[i][j][0][0], dp[i][k][1][0] + rmax[ i][ k+1][ j-1]  );

73	dp[i][j][0][0] = max( dp[i][j][0][0], dp[i][k][1][1] );

74	dp[i][j][0][1] = max( dp[i][j][0][1], dp[i][k][1][0] + A[i][j] );

75

}

76	REP(k, i )

77

{

78	dp[i][j][1][0] = max( dp[i][j][1][0], dp[k][j][0][0] + cmax[ j][ k+1][ i-1]  );

79	dp[i][j][1][0] = max( dp[i][j][1][0], dp[k][j][0][1] );

80	dp[i][j][1][1] = max( dp[i][j][1][1], dp[k][j][0][0] + A[i][j] );

81

}

82

}

83

}

84	int Ans = -INF;

85	REP(i, 2 ) REP(j,2) Ans = max( Ans, dp[n-1][m-1][i][j] );

86	P("%d\n", Ans );

87

}

88

return 0;

89

}

My three-year old has a set of rings of different sizes, each fitting on a wooden peg, with all the pegs arranged in a row. He likes to arrange the rings on the row of pegs in order of increasing size. He likes to arrange the rings on the row of pegs in order of increasing (or decreasing) size. He has exactly the same number of pegs and rings, and has figured out that even if the rings are not in order to begin with, by repeatedly swapping two adjacent rings, suitably selected, he can order them.
Since he is something of a mathematical prodigy, at least in a fond father’s eyes, I gave him a challenge — he is only allowed to swap rings that are a fixed distance K from each other i.e. he gets to pick a ring, then swap it with one K positions before or K positions after. K=1 means the next ring before or after. Of course, this can be done only if there is a peg K positions away.
As I increased the number of rings and pegs in my kid’s toy, I realized that he will throw a tantrum if I give him an unsolvable problem, or one that will take too long to sort. So your task is to tell me how many swap operations are required to sort the rings.
Input:
The first line contains T, the number of test cases. Then, T test cases follow.
The first line of each test case contains 2 integers N and K, N being the number of rings.
The second line contains N integers denoting a1, a2, …., aN, where the a’s are the diameters of the rings. Values may be repeated.
1 <= K, N <= 500
1 <= T <=50
a[i] <= 1,000,000,000
Output:
Output must contain T lines, one per test case.
If it is possible to sort the array, output the minimum number of operations required, otherwise output “-1″.
Sample Input:
3
3 2
3 2 1
3 2
3 1 2
5 2
8 2 5 7 1
Sample Output:
1
-1
3

In the digital world geometric shapes are drawn using pixels. A pixel is a square area of unit dimension. For this problem we say 2 pixels are connected if they share an edge or a vertex between them. This is also called 8-connectivity. Your task is to find the maximum possible area of a closed loop made up of A pixels (these are boundary pixels of the closed loop). Area of a closed loop is the number of pixels which are completely inside the loop or on the loop.

Consider the example below: For A = 4, you can make a close loop as follows -
This has an area of 5 with 4 pixels on the loop and 1 pixel completely inside the loop.
Input:
First line contains an integer N, the number of test cases.
Next N lines contain an integer A for that test case.
N <= 100
A <= 1000
Output:
Print N lines with a single integer stating the maximum area of a closed loop.
Sample Input:
2
4
5
Sample Output:
5
6

Given N1, M1, N2 and M2, find the smallest non-negative integer X such that X % M1 = N1 and X % M2 = N2.

Example Inout
4 7 8 13
4 6 8 12
0 5 0 10 

Output:
60
-1
0

If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1 Example: i/p: 4 5 7 10 12 13 o/p: 1 3 4 9

Given a set of n symbols and a size k write only an ITERATIVE algorithm to print all possible permutations of the given symbols with respect to the size given. For example: Given symbols ={'A','B', 'C'} and size = 2; Solution is {AA,AB,AC,BA,BB,BC,CA,CB,CC} and count = 9.

Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap.

http://books.google.co.in/books?id=7XUSn0IKQEgC&lpg=PA116&ots=z77FSOIV0j&dq=Given+an+array-based+heap+on+n+elements+and+a+real+number+x,+efficiently+determine+whether+the+kth+smallest+element+in+the+heap+is+greater+than+or+equal+to+x.+Your+algorithm+should+be+O%28k%29+in+the+worst-case,+independent+of+the+size+of+the+heap.&pg=PA116&redir_esc=y#v=onepage&q=Given%20an%20array-based%20heap%20on%20n%20elements%20and%20a%20real%20number%20x%2C%20efficiently%20determine%20whether%20the%20kth%20smallest%20element%20in%20the%20heap%20is%20greater%20than%20or%20equal%20to%20x.%20Your%20algorithm%20should%20be%20O%28k%29%20in%20the%20worst-case%2C%20independent%20of%20the%20size%20of%20the%20heap.&f=false

Given an array of unsigned integers which is initially increasing (value of integers)and then decreasing find the maximum value in the array

Subtract The Two Numbers Represented by Nodes on Linked List

Algorithm to Generate the permutations of the array containing number in lexicographical order.

Approach & Description:

Generation in lexicographic order

There are many ways to systematically generate all permutations of a given sequence. One classical algorithm, which is both simple and flexible, is based on finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates the distinct multiset permutations each once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. To use it, one starts by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found.

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

After step 1, one knows that all of the elements strictly after position k form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.

Final Algorithm:

1) From the end, keep decrementing till A[i] < A[i+1]..
2) Now, find the closest element , greater than equal, to A[i] in 

A[i+1 ... n]. Say, the index of the found element is "j".
3) Swap (A[i], A[j])
4) Reverse array A[i+1 .. n]

Example:

Input 14532

output  15234..

1) 4 is the value where A[i] < A[i+1] when scanned from the end.
2) The closest element grater than equal to 4 in the subarray 532 is 5.
3) Swap (4,5) : 14532 -> 15432
4) Now, as we have identified in step 1 the index of i, we need to
reverse the array from A[i+1, n] i.e. in 15(432) (432) needs to be
reversed and hence we will get 15234...

Working Code

#include < iostream>

#include < algorithm>

#include < time.h>

using namespace std;

  

// Swap function

template < class T>

void swap(T *i, T *j)

{

    T temp = *i;

    *i = *j;

    *j = temp;

}

  

// function to reverse a range of values

template < class T>

void reverse(T *start, T *end)

{

    while(start < end)

    {

        swap(start,end);

        start++;

        end--;

    }

}

// array_end does not point to a valid element of the array

// it is beyond the last element

template < class T>

bool permute(T* array_start,T* array_end)

{

    // array does not contain any element

    if(array_start == array_end)

        return false;

     

    // array contains only 1 element

    if(array_start+1 == array_end)

        return false;

         

    T *i,*i1,*j;

     

    // Make the pointers point to last and the second last elements

    i = array_end - 2;

    i1 = array_end - 1;

     

    // find two elements a,b such that a < b and index of a

    // is less than the index of b

    while(true)

    {

        // If such a pair is found, find an element c such that

        // c > a, then swap them and reverse the list from b till

        // the end

        if(*i < *i1)

        {

            j = array_end -1;

                 

            // worst case is that j == i1

            while(!(*i < *j))

                j--;

                 

            // This step implements the lexicographic order by

            // bringing the larger element in the front

            swap(i,j);

             

            // Reverse the list so that we have a weak decreasing

            // order in the remainder of the list

            reverse(i1,array_end-1);

            return true;

        }

         

        // Now the list is in strictly decreasing order

        // no more permutations are possible, return the

        // list as it was originally received

        if(i == array_start)

        {

            reverse(array_start,array_end-1);

            return false;

        }

         

        // decrement the two pointers

        i--;

        i1--;

    }

     

}

template< class T>

void display(T *array,T *end)

{

    T* i = array;

    while(i < end)

    {

        cout << *i << "-";

        i++;

    }

    cout << endl;

}

  

int main()

{

    srand(time(NULL));

     

    // You can declare any type here of any size

    int size = 4;

    char array[size];

     

    cout << "Enter four numbers" << endl;

    for(int i=0;i < size;i++)

        cin>>array[i];

     

    // C++ sort function so that the permutation

    // function receives the elements in the sorted order

    // in order to create a lexicographic order

    sort(array,array+4);  

     

    // First permutation

    display(array,array+4);

    int count=1;

     

    // Call the function while you get valid permutations

    while(permute(array,array+4))

    {

        count++;

        display(array,array+4);

    }

     

    cout << "Total permutations are " << count << endl;

     

    system("pause");

    return 0;

}

Run Here http://ideone.com/sK8JH
The complexity of the approach is O(n*n!)

http://en.wikipedia.org/wiki/Permutation
http://marknelson.us/2002/03/01/next-permutation/