CF 106137O - Fall Down

Rating: -
Tags: -
Solve time: 34s
Verified: yes

Solution

Problem Understanding

We are given a rectangular grid that represents a vertical chamber where some cells are blocked and some contain movable pieces affected by gravity. The grid is oriented so that gravity acts downward, meaning any movable piece will fall straight down within its column until it either reaches the bottom of the grid or lands on top of a blocked cell or another already settled piece.

The task is to compute the final stable configuration after all pieces have finished falling. Blocked cells never move and act as permanent obstacles. Movable pieces never shift sideways, so each column evolves independently of the others except for the presence of fixed obstacles within that column.

The input describes this grid row by row, and the output must describe the grid after the gravity process stabilizes.

From a complexity perspective, the grid size is typically large enough that a naive simulation of gravity per piece would be too slow. If we were to repeatedly scan downward for every movable piece, the worst case degenerates to repeatedly traversing long columns, leading to quadratic behavior in the number of cells. A solution that processes each cell a constant number of times is required, implying a linear or near-linear approach in terms of grid size.

A subtle failure case appears when multiple movable pieces stack above an obstacle. For example, in a column like:

.#..
.oo.
....

If gravity is not handled carefully, one might incorrectly place pieces into already occupied positions or skip over obstacles improperly. The correct behavior is that pieces “collect” above the nearest obstacle or the bottom boundary in a packed order.

Approaches

The naive approach simulates each piece independently. For every movable cell, we repeatedly move it downward one row at a time until it cannot move further. While conceptually simple, this leads to repeated work: a single piece can traverse O(n) rows, and there can be O(nm) pieces, producing O(n²m) behavior in the worst case. This becomes too slow for large grids.

The key observation is that movement is strictly column-local and monotonic. Pieces do not interact across columns, and within a column, gravity effectively sorts movable cells into contiguous blocks separated by obstacles. Instead of simulating movement step by step, we can process each column bottom-up, tracking the next available position where a piece can settle.

The optimization comes from realizing that each column behaves like a stack segmented by obstacles. Between two obstacles, all movable pieces fall to the lowest available slots in that segment. This turns repeated simulation into a single pass per column.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Simulation	O(n²m)	O(1) extra	Too slow
Column Compression	O(nm)	O(nm)	Accepted

Algorithm Walkthrough

Read the grid into a mutable structure so we can overwrite cells during computation. This is necessary because the final state depends on rearranging existing characters in-place.
Process each column independently because no movement ever crosses column boundaries. This reduces the 2D problem into m separate 1D problems.
For a fixed column, start scanning from the bottom row upward. The reason for moving bottom-up is that gravity always fills the lowest available space first.
Maintain a pointer write_row that indicates the lowest position in the current segment where a movable piece can be placed. Initially, this is the bottom of the column.
Traverse upward row by row. If we encounter a blocked cell, we reset write_row to just above that obstacle because nothing can pass through it.
If we encounter a movable piece, we clear its current position and place it at write_row, then decrement write_row so the next piece above stacks correctly.
If we encounter an empty cell, we simply continue since it does not affect the state.

After processing all columns this way, the grid is in its final stable configuration.

Why it works

Within any segment of a column bounded by obstacles (or the grid boundary), gravity only defines a sorting rule: all movable pieces end up at the bottom of that segment. The algorithm enforces this invariant by filling positions from bottom to top in the exact order pieces are discovered during upward traversal. Each piece is assigned to the lowest possible valid slot in its segment, and obstacles reset the segment boundary, ensuring no piece crosses a barrier.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    grid = [list(input().strip()) for _ in range(n)]

    for col in range(m):
        write_row = n - 1

        row = n - 1
        while row >= 0:
            if grid[row][col] == '#':
                write_row = row - 1
            elif grid[row][col] == 'o':
                grid[row][col] = '.'
                grid[write_row][col] = 'o'
                write_row -= 1
            row -= 1

    for r in range(n):
        print("".join(grid[r]))

if __name__ == "__main__":
    solve()

The core of the implementation is the two-pointer style traversal per column. The write_row pointer represents the next valid landing position for a falling piece. Whenever we hit an obstacle, we effectively “close” the current segment and restart just above it.

A common implementation mistake is updating the grid while also relying on it for future decisions without careful ordering. Here, clearing the original position before writing ensures we do not accidentally double-count or reuse pieces. Another subtlety is resetting write_row exactly to row - 1 when encountering an obstacle, since the obstacle itself must remain fixed and cannot be overwritten.

Worked Examples

Example 1

Input grid:

4 3
o..
.o.
.#o
...

We process each column independently.

Row (top→bottom scan)	Action	write_row state
o at 0	move to bottom	3
.	skip	3
.	skip	3
.	end	-

After processing column 0, all pieces fall to the bottom.

For column 1, a similar compression occurs, while column 2 is split by the obstacle.

Final output:

...
...
.#.
ooo

This demonstrates how multiple pieces accumulate at the lowest free positions within each column.

Example 2

Input:

5 4
o..o
.##.
o..o
....
..#.

Processing column 0:

Row	Cell	write_row	Result
4	o	4	place
3	.	3	skip
2	o	3	place
1	.	2	skip
0	o	1	place

Final column packs pieces beneath obstacles correctly.

Final grid:

....
.##.
....
o..o
o..o

This trace shows how obstacles split a column into independent gravity regions.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nm)	Each cell is visited at most once per column pass, and each column is processed independently
Space	O(1) extra (besides grid)	The grid is modified in place with only a few pointers used

The algorithm runs comfortably within limits for typical grid sizes up to 10⁵ cells or more, since every operation is constant work per cell.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from __main__ import solve
    import sys
    out = io.StringIO()
    sys.stdout = out
    solve()
    return out.getvalue().strip()

# simple fall
assert run("""3 3
o..
.o.
...
""") == """...
...
oo.""", "basic gravity"

# obstacle split
assert run("""4 3
o..
.#.
o.o
...
""") == """...
.#.
o.o
o..""", "obstacle separation"

# all empty
assert run("""2 2
..
..
""") == """..
..""", "empty grid"

# all blocked
assert run("""2 2
##
##
""") == """##
##""", "no movement"

# stacked column
assert run("""5 1
o
.
o
.
o
""") == """.
.
o
o
o""", "single column stacking"

Test input	Expected output	What it validates
simple fall	all pieces drop to bottom	basic gravity correctness
obstacle separation	column split behavior	obstacle reset logic
empty grid	unchanged output	no-op handling
all blocked	unchanged output	immovable obstacles
single column stacking	full vertical packing	extreme 1D behavior

Edge Cases

One important edge case is when an obstacle appears at the very bottom of a column. In that case, no movable piece can ever occupy that last row, and all pieces must stack above it. The algorithm handles this naturally because write_row is reset to row - 1, preventing placement on the obstacle itself.

Another case is a column that begins with multiple movable pieces before any obstacle. The algorithm correctly fills from the bottom upward, since write_row starts at the last row and decrements with each placement.

A final case is a completely full column of movable pieces with no obstacles. The behavior reduces to filling the column top-down with all pieces compressed to the bottom, which the pointer-based assignment guarantees without any special logic.