Champagne Tower

Problem Statement

Imagine a setup where glasses are arranged in the form of a pyramid. The first row of this pyramid has a single glass, while each subsequent row has one more glass than the previous one, continuing this pattern up to the 100th row. Each glass in this setup can contain exactly one cup of champagne.

When champagne is poured into the topmost glass, it fills up to its capacity of one cup. Any additional champagne will then overflow equally into the two adjacent glasses directly below it. This overflow continues down the levels of the pyramid: each glass passes on excess champagne equally to the two glasses below it until the extra champagne either fills up the glasses or spills over at the edges of the pyramid to the floor.

The objective is to determine the volume of champagne in a specific glass, addressed by its row number i and position j within that row, after pouring a specified amount of champagne into the top glass.

Examples

Example 1

Input:

poured = 1, query_row = 1, query_glass = 1

Output:

0.00000

Explanation:

We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2

Input:

poured = 2, query_row = 1, query_glass = 1

Output:

0.50000

Explanation:

We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Example 3

Input:

poured = 100000009, query_row = 33, query_glass = 17

Output:

1.00000

Constraints

• 0 <= poured <= 109
• 0 <= query_glass <= query_row < 100

Approach and Intuition

To solve this problem, we need an efficient way to simulate the pouring and overflow of champagne through the hierarchical structure of the glasses:

1. Start by recognizing that we need to track the amount of champagne in each glass. An array can be used where each element represents a glass in a specific row of the pyramid.

2. Initially, all glasses except the topmost one (the root of our pyramid) are empty. Champagne is first poured into the root glass.

3. As we pour champagne, any glass that receives more than one cup of champagne will overflow. The excess (amount in the glass - 1 cup) must be distributed equally to the two glasses immediately below it in the pyramid.

4. This distribution will result in subsequent overflow events in the glasses below, necessitating the application of the above logic iteratively from the top of the pyramid to the bottom, or until excess champagne is spilled on the floor from the last row.

5. The end condition for each glass needs to be whether it contains less than or equal to one cup of champagne. If yes, then the glass does not overflow and its current state is ready to be queried.

6. Once the pouring simulation is completed, querying the champagne amount in a specific glass j of row i is straightforward as the simulation ensures that all glasses have the correct amount of champagne based on the input conditions and the inherent overflow mechanism.

This method utilizes a practical application of recursive overflows in a tree-like structure, albeit represented in a linear array simulating each row's glass distributions continually influenced by the row above it.

Solutions

class Solution {
    public double champagneTower(int pouredAmount, int targetRow, int targetGlass) {
        double[][] tower = new double[102][102];
        tower[0][0] = (double) pouredAmount;
        for (int row = 0; row <= targetRow; ++row) {
            for (int glass = 0; glass <= row; ++glass) {
                double quantity = (tower[row][glass] - 1.0) / 2.0;
                if (quantity > 0) {
                    tower[row+1][glass] += quantity;
                    tower[row+1][glass+1] += quantity;
                }
            }
        }

        return Math.min(1, tower[targetRow][targetGlass]);
    }
}