CareerCup

what is the index here? their index in their row or is it index starting from the topmost cup?
PLease post google questions with more clarity, they deserve it

http ://careercup.appspot.com/question?id=12217186

Triangle of Yang...
1
1 2 1
1 3 3 1
1 4 6 4 1
so the answer is obvious: extra * (1/C(h-1,i-1))

Triangle of Yang...
1
1 2 1
1 3 3 1
1 4 6 4 1
so the answer is obvious: extra * (1/C(h-1,i-1))

sorry ,it's extra * (C(h-1,i-1)/(2^(h-1)))... Am I Wrong

sorry ,it's extra * (C(h-1,i-1)/(2^(h-1)))... Am I Wrong

Every node has to have two children.. why does the figure show otherwise? :O

Please find it below address:

careercup.com/question?id=12217186

Here's an easy solution that lazily enumerates the amount in each cup in level order:

def cascade(total, limit):
    row = [float(total)]
    while 1:
        new_row = (len(row) + 1) * [0.0]
        for i, amount in enumerate(row):
            excess = max(0, amount - limit)
            yield amount - excess
            if excess:
                overflow = 0.5 * excess
                new_row[i] += overflow
                new_row[i+1] += overflow
        row = new_row

With this algorithm, finding the amount in the n first cups takes O(n) time and O(sqrt(n)) space. It also generalizes easily in various directions. One generalization is to arbitrary cascades represented as directed acyclic graphs. Another generalization is allowing arbitrary limits per cup rather than a fixed limit.

This is effectively a breadth-first traversal. The related question that googlybhai linked to contains a linear-time and log-space solution which is essentially the same algorithm using instead a depth-first traversal. However, that assumes that the cascade structure is presented to us explicitly as a tree and that we can cache values on the nodes. Without that assumption, creating the tree would require O(n) space, which is obviously worse than the O(sqrt(n)) space used in my algorithm.

public List<double> PourWater(int water)
        {
            List<double> result = new List<double>(){0};
            while (water > 0)
            {
                PourWater(result, 1, 0, 0);
                water--;
            }

            return result;
        }

        public void PourWater(List<double> cups, double water, int h, int i)
        {
            int index = h * (h + 1) /2 + i ;

            if (cups[index] + water > 1)
            {
                if (cups.Count <= index + h + 1)
                {
                    cups.AddRange(new double[h + 2]);
                }

                cups[index] += water - 1;
                PourWater(cups, 0.5, h + 1, i);
                PourWater(cups, 0.5, h + 1, i + 1);
            }
            else
            {
                cups[index] += water;
            }
        }

are the cups arranged exactly as shown in the diagram or are they in the shape of a tree? does evey cup has a left and a right child ? as per the diagram all the cups in the left column have no left child, so would their half of the spill will go waste?

I guess I have a good solution to this problem!
income liquid to each cup is sum up the overflow of two cups above. let's say cup(h,k) =o(cup(h-1, k-1)) + o(cup(h-1, k)) , here o(x) means overflow cup x.
so we have :

f(h, k) = 0 for k<0 ,
              f(h-1, k-1)+f(h-1,k) for  k>=0, k<=h ,
              0 for k>h

now we can easily write a recursive relation and resolve the problem based on a recursive program. The run time would be just O(log n)

float max(float a, float b)   { 	return (a<b)?b:a; }
float d(int h, int k)
{
	if(k<0 || k>h)
		return 0;
	if(h<=0) 
		return N;
	else if(h==1)
		return max((N-capacity)/2, 0);
	float income = max( (d(h-1, k-1)-capacity)/2, 0) +
                                 max((d(h-1, k)-capacity)/2, 0);
	return income;
}

suppose we have two global float variables, capacity and N, as capacity of each cup and total liquid

I would appreciate any comment or suggestion.