CareerCup

Question is not clear. Suppose rocks are numbered: 1,2,3

is

3
1 2

different from

3 
2 1

?

Do sizes of the rocks matter? (you can't place a bigger rock on a smaller rock)?

Recursive solution in python below:

def rockstacking(amt):
	if amt == 0:
		return 0
	if amt < 3:
		return 1
	else:

		#this here is the tricky part
		if amt%2 == 0:
			result = 0 
		else:
			result = 1
		

		for i in xrange(amt/2+1):
			result = result + rockstacking(i)
	return result

Basically just think of it as a stack of dominos with each layer less then the layer below it.

The maximum amount of rocks that can go above the base layer is roughly equal to N/2.

Start off counting with all the rocks in the base layer and 0 rocks above it (+1 to the count). Then subtract 1 from the base layer and count the number of ways you can recursively make the structure with one rock; add that to the count. Subtract 2 rocks from the base layer and Count the amount of ways you can make the structure with 2 rocks; add that to the count... then 3 then 4... until you reach N/2.

This is the basic concept behind the solution, however it is not completely correct.

The tricky part is to know that when you have an even number of rocks you have to subtract One from your overall solution. Why? Lets take a look at an example:

Assume N=8. Everything works fine until the algorithm reaches N/2 or in this case Four rocks in the base layer. With Four rocks in the base layer that means the recursive algorithm will count the amount of ways you can create the structure above it with the other remaining 4 rocks.

To illustrate:
Total 8 rocks

At N/2
Base layer has four rocks and looks like this when the rocks are represented by underscores:
 _ _ _ _ 

The two possible structures on top of the base layer look like this:

_
_ _ _

and:

_ _ _ _     <<<This is wrong, you can't lay four rocks on top of four rocks.

You will see that the recursive call is off by 1 because you can't overlay four rocks on four rocks when the problem clearly states that each layer is less then the layer below it. The algorithm will always count incorrectly in the same way illustrated above whenever N is even. Thus when the amount of rocks is even just subtract 1 from the overall solution.

I only found a solution by generating all the combinations and then count them. :-(

For k= 1..11, the answer should be {1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12 }.

public static int getPossibleCombination(int k)
	{
		List<List<Integer>> solutionList= getCandidates(k,k+1);  // 2nd number should be > k
		int i= 0;
		for (List<Integer> solution: solutionList) {
			System.out.println("solution[" + i + "]= " + solution);
			i++;
		}
		return(solutionList.size());
	}
	
        // generate the candidate only if the first element is < limit
	public static List<List<Integer>> getCandidates(int i,int limit)
	{
		List<List<Integer>> result= new ArrayList<>();
		if (i <= 2) {			
			if (i < limit) {
				List<Integer> tmp= new ArrayList<>();
				tmp.add(i);
				result.add(tmp);
			}
			return(result);
		}
		for (int j= 0; j<i; j++) {
			int first= i-j;
			int second= j;
			if (first >= limit) {
				continue;
			}
			List<List<Integer>> secondPossible= getCandidates(second,first);
			for (List<Integer> possible: secondPossible) {
				possible.add(0,first);  // add to beginning
				result.add(possible);
			}
		}
		return(result);
	}
	
	public static void main(String[] args) {
		int k= 10;
		System.out.println("possibleCombination(" + k + ")= " + getPossibleCombination(k));
	}

I believe it is a simple recursion problem. You are required to place all rocks in single stack. You have to meet the requirement to build the rock stack(lower layer > upper layer).

{{public static int stackRock(int total,int prev){
int count =0;

if (total==0)
return 1;

if (total<=prev)
return 0;



for (int i=prev+1;i<=total;i++){
count+=stackRock(total-i,i);
}

return count;
}}}

The problem can be abstracted into divide n into an ascending sequence.
(1)suppose we have remaining S to divide and previous is P
(2)then in this level a valid choice X must be within [P+1, S]
(3)and when S - X <= X, which means no another level can be built, then all S must be used in this level
Following is a solution in C:

int next(int pre, int remain)
{
    int sum = 0, i;
    for(i = pre+1; i <= remain; ++i){
        if(remain - i > i) sum += next(i, remain-i);
        else{
            ++sum;
            break;
        }
    }
    return sum;
}

int main()
{
    int n = 20;
    printf("%d has %d ways\n", n, next(0, n));

    return 0;
}

I will try to create a min heap whose key will be the size of stone.

I think this is a dynamic programming problem and is same as coin change problem. You have say 3 coins 1,2,3 and you've to reach sum 5. All possible ways? 11111, 1112, 122, 23

Above problem can be translated to current problem - you have 5 rocks (N=5) and you have 4 coins (N-1) 1,2,3,4. Count number of ways to reach sum 5. 11111, 1112, ....

Solution for coin change problem - geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Based on my understanding,
Expected answer for n=11 are
* 1 10
* 1 2 8
* 1 2 3 5
* 1 3 7
* 1 4 6
* 2 9
* 2 3 6
* 2 4 5
* 3 8
* 4 7
* 5 6
So count = 11
Following is my code using recursion. I've tried solutions provided above but none of them gave me proper answer... Chk the following code..
Initial Call: myMethod(0,11)

public static int myMethod(int a, int b)
    {
        int count = 0;
        if(a<b)
        {
            int tmp = 0;
            for(int i= (++a); ;i++)
            {
                tmp = b-i;
                if(tmp>i)
                {
                    count = count+1+myMethod(i,tmp);
                }
                else
                {
                    break;
                }
            }
            return count;
        }
        else
            return 0;
    }

Since there's no right solution yet posted, I'm posting a C++ solution. Please notice that the question says nothing about the rock size or weight, it just counts the rocks on the layers.

Code:

#include <iostream>

void arrange_rocks_recursive(int k, int n, int& nways) {
	for (int i = k; i <= n; i++) {
		int j = n - i;
		if (j <= i) {
			continue;
		}
		
		//std::cout << "n = " << n << ", i=" << i << ", j=" << j << std::endl;
		arrange_rocks_recursive(i+1, n-1, ++nways);
	}
}

int arrange_rocks(int n) {
	if (n == 0)
		return 0;
	if (n < 0)
		return -1;
		
	int nways = 0;
	arrange_rocks_recursive(1, n, nways);
	return nways;
}

/**
 * A child is arranging rocks in layers. He can arrange the rocks, in such way
 * that, any layer has lesser rocks than its base layer. Given n rocks, In how
 * many ways can the child arrange the rocks.
 */
int main() {
	std::cout << arrange_rocks(7) << std::endl;
}

DP problem:
DP[i,j] means the number of ways arrarging j rocks such that the base layer has i rocks.
DP[i,j] = 0 if i>j;
= 1 if i=j;
= sum_{1<=p<i }(DP[p,j-i])

int rocks(int n){
    if(n<=1) return 1;
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    for(int i=1; i<=n; ++i)
        for(int j=i; j<=n; ++j){
            if(j==i)
                dp[i][j]=1;
            else{
                for(int k=1; k<i; ++k)
                    dp[i][j]+=dp[k][j-i];
            }
        }
    int sum = 0;
    for(int i=1; i<=n; ++i)
        sum+=dp[i][n];
    return sum;
}