algoadvance

We are given a champagne tower with an infinite number of rows, where the first row has 1 glass, the second row has 2 glasses, the third row has 3 glasses, and so on. We pour poured amount of champagne into the top glass. When a glass becomes full (it cannot hold more than 1 unit of champagne), the excess champagne spills equally to the two glasses immediately below it.

We need to find how much champagne is in the glass located at the query_row and query_glass.

Clarifying Questions

  1. What is the range of poured, query_row, and query_glass?
    • Generally, these are within reasonable bounds as per typical competitive programming constraints, usually poured can be up to 10^9, and query_row, query_glass up to 99 or similar.
  2. Will there always be enough champagne to reach the given query_row and query_glass?
    • It is possible that not enough champagne is there to reach the row. If so, we’ll simply return 0.
  3. What is the expected output if the glass is spilled but not full?
    • The output should be the specific amount in that glass, which could be less than 1.

Strategy

  1. Use a list to simulate the glasses in the tower. Each entry in the list will represent a glass on a specific row.
  2. Start by initializing the first glass with the number of poured champagne.
  3. Iterate through each row, cascading the excess champagne to the glasses in the next row.
  4. Stop when we reach the query_row.
  5. The final value in the query_glass will be the minimum of 1 and the amount (since a glass can’t have more than 1 unit of champagne).

We simulate the pouring process until we reach the desired row and glass position.

Code

def champagneTower(poured: int, query_row: int, query_glass: int) -> float:
    # Initialize the first element with the poured champagne
    towers = [[0] * (r + 1) for r in range(query_row + 1)]
    towers[0][0] = poured
    
    for r in range(query_row):
        for c in range(r + 1):
            overflow = (towers[r][c] - 1.0) / 2.0
            if overflow > 0:
                towers[r + 1][c] += overflow
                towers[r + 1][c + 1] += overflow
    
    return min(1, towers[query_row][query_glass])

# Example usage:
poured = 25
query_row = 6
query_glass = 1
print(champagneTower(poured, query_row, query_glass))  # Expected output depends on the simulation

Time Complexity

Thus, the overall time complexity is (O(R^2)), which is efficient for input constraints typical of this problem (e.g., (R \leq 99)).

Try our interview co-pilot at AlgoAdvance.com