Adding water to stack of glasses

Question

I always wanted to know if there is any real-world application of Pascal's triangle than just coefficients of the binomial expansion.

I tried to solve this problem:

But, What if I am adding K units of water and wants to find a glass which has the least water in it:

Where, Glass will be found as: c-th glass in r-th row

And I believe. If we could find this then it will not be difficult for us to find amount of water in any glass for which {i<r and j<c}

• Problem:

  Input Water added- K units and capacity of each glass as 1- unit

  Output Expected : c th glass in r th row having least water in it.

I tried to solve problem by keeping note of capacity of each row when it starts overflow: and wants to know how to keep going with this method.

      1       max = 1, cap = 1
     1 1      max = 1, sum(coefficients)=2**1 = 2, cap = 2/1 
    1 2 1     max = 2, sum = 2**2, cap = 4/2 = 2 units 
   1 3 3 1    max = 3, sum = 2**3, cap = 8/3 units
  1 4 6 4 1   max = 6, sum = 2**4, cap = 16/6 units 

#Not sure but this is how it seems to me for the rate @which water is being added.

                 1
              1/2   1/2
           1/4   2/4  1/4
        1/8   3/8    3/8   1/8
     1/16  4/16  6/16   4/16  1/16  

Should I use 2-D list and define as :

Δ1, Δ2 = 0, 0
if g(n-1, k)>1 and k <= n-1:
    Δ1 = g(n-1, k) -1 
if g(n-1, k-1)>1 and k-1 <= n-1:
    Δ2 = g(n-1, k-1) - 1
g(n, k) = Δ1/2 + Δ2/2

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

g = [[0]*(i+1) for i in range(11)]
def f(g, K):
    g[1][1] += 1
    K = K-1
    d1, d2 = 0, 0
    for n in range(2, 10):
        for k in range(1, n+1):
            if k ==1:
                g[n][k] = g[n-1][k]/2
            if k == n:
                g[n][k] = g[n-1][k-1]/2
            else:
                if g[n-1][k-1]>1:
                    d1 = g[n-1][k-1] -1
                if g[n-1][k] > 1:
                    d2 = g[n-1][k] -1
                g[n][k] = d1/2 + d2/2        
    return g, K
k = int(input())
while k:
    g, k = f(g, k)
for x in g:
    print(x)

I don't know what is missing?

Answer 1

For such small K constraint simple row-by-row filling is enough (we can store only two rows, here 2D list is used for simplicity)

def fillGlasses(k, row, col):
    gl = [[k]]
    level = 1
    overflow_occured = True
    while overflow_occured:   # also can stop when at needed row
        print(gl[level-1])  #before overflow
        level += 1
        overflow_occured = False
        gl.append([0]*level)
        for i in range(level - 1):
            t = gl[level-2][i] - 1
            if t > 0:
                gl[level-1][i] += t/2
                gl[level-1][i+1] += t/2
                gl[level-2][i] = 1
                overflow_occured = True
    #print(gl)  #after all
    return gl[row-1][col-1]

print(fillGlasses(21,8,4))

[21]
[10.0, 10.0]
[4.5, 9.0, 4.5]
[1.75, 5.75, 5.75, 1.75]
[0.375, 2.75, 4.75, 2.75, 0.375]
[0, 0.875, 2.75, 2.75, 0.875, 0]
[0, 0, 0.875, 1.75, 0.875, 0, 0]
[0, 0, 0, 0.375, 0.375, 0, 0, 0]
0.375

Answer 2

I presumed you are asking this exact online judge question, or a very similar one: https://practice.geeksforgeeks.org/problems/champagne-overflow2636/1

If so, actually the constraints for R and C is only 500 and any simulation could work. One little catch is that there maybe water in a row even previous row is not fully filled. You may consider small test cases and simulate to find out, for example K = 6, the glasses will look like:

1
1, 1
0.75, 1, 0.75
0, 0.25, 0.25, 0 
// Notice previous row is not fully filled, makes sense as "middle" glasses will overflow faster

I think for implementation-wise it is similar for top-down and bottom-up approach. Here is my top-down accepted code which simply simulate the water pouring and overflow process, with C++, same algorithm can be implemented in any language:

class Solution {
    public:
    double cups[505][505];

    void pourWaterAt(double K, int R, int C, int targetR){
        if(R > targetR) return;
        cups[R][C] += K;
    
        if(cups[R][C] > 1){
            double overflow = cups[R][C] - 1;
            cups[R][C] = 1;
            pourWaterAt(overflow/2.0f, R+1, C, targetR);
            pourWaterAt(overflow/2.0f, R+1, C+1, targetR);
        }
    }

    double waterOverflow(int K, int R, int C) {
        memset(cups, 0, sizeof(cups));
        pourWaterAt(K, 1, 1, R);
        return cups[R][C];
    }
};

After the simulation, you can just scan through cups[R][C] and find the smallest positive one (and its index) to get the answer.